CSG-CPC
Online Judge

1135 : 有向无环图

         Time Limit: 2 Sec     Memory Limit: 128 Mb     Submitted: 39     Solved: 14    

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} $$

除以 (109 + 7) 的余数。其中, ai, bj 是给定的数列。

Input

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

接下来 n 行的第 i 行包含两个整数 ai, bi(0 ≤ ai, bi ≤ 109).

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

Output

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

Sample

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

Hint

Author

ftiasch