Bobo 有一个 $n$ 个点，$m$ 条边的有向无环图（即对于任意点 $v$，不存在从点 $v$ 开始、点 $v$ 结束的路径）。

为了方便，点用 $1, 2, \dots, n$ 编号。 设 $\mathrm{count}(x, y)$ 表示点 $x$ 到点 $y$ 不同的路径数量（规定 $\mathrm{count}(x, x) = 0$），Bobo 想知道 $$\sum_{i = 1}^n\sum_{j = 1}^n \mathrm{count}(i, j) \cdot a_i \cdot b_j$$ 除以 $(10^9+7)$ 的余数。

其中，$a_i, b_j$ 是给定的数列。

输入

输入包含不超过 $15$ 组数据。

每组数据的第一行包含两个整数 $n, m$ ($1 \leq n, m \leq 10^5$).

接下来 $n$ 行的第 $i$ 行包含两个整数 $a_i, b_i$ ($0 \leq a_i, b_i \leq 10^9$).

最后 $m$ 行的第 $i$ 行包含两个整数 $u_i, v_i$，代表一条从点 $u_i$ 到 $v_i$ 的边 ($1 \leq u_i, v_i \leq n$)。

输出

对于每组数据，输出一个整数表示要求的值。

样例输入

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

样例输出

4
4
250000014