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 \dots \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~