To make the kingdom more prosperous, Pisces decides to ally with the elves living in the forest. However, the elven elders want to test Pisces, so they give him a simple question. Given a DAG with \(n\) nodes and \(m\) edges, the elven elders want to know the value of \(\sum^n_{i=1}\sum^n_{j=1}count(i,j)\cdot a_i\cdot b_j\) mod \(1e9 + 7\), where \(count(x,y)\) is defined by the number of different paths from \(x\) to \(y\) and \(count(x,x)\) = 0, and \(a\), \(b\) are \(2\) given arrays. It is too hard for Pisces to answer this question, so he turns to you for help.

The first line contains an integer \(T\) \((1\leq T \leq 10)\), which denotes the number of test cases.

For each test case, the first line contains \(2\) integers \(n\) and \(m\) \((1 \leq n, m \leq 10^5)\) — the number of nodes and the number of edges, respectively. Each of the next \(n\) lines contains \(2\) integers \(a_i\) and \(b_i\). And for the next \(m\) lines, each line contains \(2\) integers \(u\) and \(v\) denoting a directed edge going from node \(u\) to node \(v\) \((1\leq u,v \leq  n)\).

For each test case, print the answer.