Bobo has a directed acyclic graph (DAG) with $n$ vertices and $m$ edges (i.e., for any vertex $v$, there is no path starting and ending at $v$).

For convenience, the vertices are labeled $1, 2, \dots, n$. Let $\mathrm{count}(x, y)$ denote the number of distinct paths from vertex $x$ to vertex $y$ (with the convention that $\mathrm{count}(x, x) = 0$). Bobo wants to know the value of $$\sum_{i = 1}^n\sum_{j = 1}^n \mathrm{count}(i, j) \cdot a_i \cdot b_j$$ modulo $(10^9+7)$.

Here, $a_i$ and $b_j$ are given sequences.

Input

The input contains no more than $15$ test cases.

The first line of each test case contains two integers $n, m$ ($1 \leq n, m \leq 10^5$).

The next $n$ lines, the $i$-th line contains two integers $a_i, b_i$ ($0 \leq a_i, b_i \leq 10^9$).

The last $m$ lines, the $i$-th line contains two integers $u_i, v_i$, representing a directed edge from vertex $u_i$ to $v_i$ ($1 \leq u_i, v_i \leq n$).

Output

For each test case, output a single integer representing the required value.

Examples

Input 1

3 3
1 1
1 1
1 1
1 2
1 3
2 3
2 2
1 0
0 2
1 2
1 2
2 1
500000000 0
0 500000000
1 2

Output 1

4
4
250000014