C is at an empty field with $k$ dimensions, each dimension has size of $w_i$, meaning that all positions in the field should satisfy the condition $1\le a_i\le w_i$ $(1\le i\le k)$.

C is planning to walk for the next $P=w_1\times w_2\times \cdots \times w_k$ days, starting from a new position every day. In other words, he will walk from every position in the field. Every day, he will walk in a planned route consisting of repeating $n$ steps, denoted by $c_i$ and $d_i$ meaning that he will walk from $(a_1,a_2,\dots ,a_{c_i},\dots ,a_k)$ to $(a_1,a_2,\dots ,a_{c_i}+d_i,\dots ,a_k)$ $(1\le c_i\le k,d_i\in \{-1,1\})$. C will repeat the route until he leaves the field. That is, if C is still in the field after $n$ steps, he will go back to step $1$ and start all over again.

Find the number of steps C took after $P$ days.

Input Specification

The first line contains two integers $n,k$, denoting the number of steps in C's route and the number of dimensions of the field. The next line contains $k$ integers $w_i$, denoting the sizes of dimensions of the field. The next $n$ lines contain two integers on every line, denoting $c_i,d_i$, as mentioned above.

Output Specification

Output one integer denoting the answer modulo ${10}^9+7$. If C will be stuck in the field forever on one day, output -1.

Sample Input 1

3 2
3 3
1 1
2 -1
1 1

Sample Output 1

21

Starting at $(1,1)$ will take $2$ steps, starting at $(1,2)$ will take $4$ steps, starting at $(1,3)$ will take $4$ steps.
Starting at $(2,1)$ will take $2$ steps, starting at $(2,2)$ will take $3$ steps, starting at $(2,3)$ will take $3$ steps.
Starting at $(3,1)$ will take $1$ steps, starting at $(3,2)$ will take $1$ steps, starting at $(3,3)$ will take $1$ steps.
The answer would be $21$.

Sample Input 2

5 4
6 8 6 5
3 1
2 1
1 1
2 1
2 -1

Sample Output 2

10265

Constraints

For all test cases, $1\le n\le 5\times {10}^5$, $1\le k\le 10$, $1\le w_i\le {10}^9$, $d_i\in \{-1,1\}$.

For partials, refer to the table below.

Test Case	$n=$	$k=$	$w_i\le$
1~3	$5$	$5$	$3$
4~6	$100$	$3$	$10$
7~8	${10}^5$	$1$	${10}^5$
9~12	${10}^5$	$2$	${10}^6$
13~16	$5\times {10}^5$	$10$	${10}^6$
17~20	$5\times {10}^5$	$3$	${10}^9$