Little C likes running and is very fond of topping the WeChat step count leaderboard. To this end, he has devised a plan to rack up WeChat steps.

He arrives at an open field. A person in this field can be represented by their $k$-dimensional integer coordinates $(a_1, a_2, \dots, a_k)$. The field has size constraints: the size of the $i$-th dimension is $w_i$, so a person in the field must have coordinates satisfying $1 \le a_i \le w_i$ ($1 \le i \le k$).

Little C plans to spend the next $P = w_1 \times w_2 \times \dots \times w_k$ days starting his step-counting plan from a new position in the field each day (in other words, he will start his plan once from every possible position in the field).

His plan is very simple: every day, he follows a pre-determined route consisting of $n$ steps. Each step is represented by $c_i$ and $d_i$: if he is currently at $(a_1, a_2, \dots, a_{c_i}, \dots, a_k)$, this step will move him to $(a_1, a_2, \dots, a_{c_i} + d_i, \dots, a_k)$, where $1 \le c_i \le k$ and $d_i \in \{-1, 1\}$. Little C will continuously repeat this route until he moves outside the boundaries of the field, at which point the day's plan ends. (That is, after completing the $n$-th step, if Little C is still within the field, he will return to the 1st step and start over).

Little C is very confident in his speed, so he does not care about the actual time spent; he only wants to know how many total WeChat steps he has accumulated after $P$ days. Please help him calculate this.

Input

The first line contains two space-separated integers $n$ and $k$, representing the number of steps in the route and the number of dimensions of the field, respectively.

The next line contains $k$ space-separated integers $w_i$, representing the size of the field in each dimension.

The next $n$ lines each contain two space-separated integers $c_i$ and $d_i$, representing the direction of each step, as described in the problem statement.

Output

Output a single integer representing the answer. Since the answer can be very large, you only need to output the value modulo $10^9 + 7$.

If Little C's plan causes him to never leave the field on any given day, output -1.

Examples

Input 1

3 2
3 3
1 1
2 -1
1 1

Output 1

21

Note 1

Starting from $(1, 1)$, he takes 2 steps; from $(1, 2)$, he takes 4 steps; from $(1, 3)$, he takes 4 steps. Starting from $(2, 1)$, he takes 2 steps; from $(2, 2)$, he takes 3 steps; from $(2, 3)$, he takes 3 steps. Starting from $(3, 1)$, he takes 1 step; from $(3, 2)$, he takes 1 step; from $(3, 3)$, he takes 1 step. Total: 21 steps.

Input 2

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

Output 2

10265

Examples 3

See walk/walk3.in and walk/walk3.ans in the contestant directory.

Examples 4

See walk/walk4.in and walk/walk4.ans in the contestant directory.

Constraints

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