Description

Bobo 有一个 n 个点，m 条边的有向无环图（即对于任意点 v，不存在从点 v 开始、点 v 结束的路径）。 为了方便，点用 1,2,…,n 编号。 设 count(x,y) 表示点 x 到点 y 不同的路径数量（规定 count(x,x)=0），Bobo 想知道

$$ \sum_{i=1}^{n}\sum_{j=1}^{n}count(i,j)\cdot a_{i} \cdot b_{j} $$

除以 (10⁹ + 7) 的余数。其中， a_i, b_j 是给定的数列。

Input

输入包含不超过 15 组数据。 每组数据的第一行包含两个整数 n, m(1 ≤ n, m ≤ 10⁵).

接下来 n 行的第 i 行包含两个整数 a_i, b_i(0 ≤ a_i, b_i ≤ 10⁹).

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

Output

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

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