Description

Xiao C likes running, and he especially likes to climb the WeChat step leaderboard. For this, he made a plan to “farm” WeChat steps.

He comes to an open area. A person’s position in this area can be represented by a $k$-dimensional integer coordinate $(a_1, a_2, \ldots , a_k)$. The area has size limits: the size of the $i$-th dimension is $w_i$, so a person in the area must satisfy $1 \le a_i \le w_i$ ($1 \le i \le k$).

Xiao C plans that in the next $P = w_1 \times w_2 \times \cdots \times w_k$ days, he will start from a new position in the area each day to begin his step-farming plan (in other words, he will start once from every position in the area).

His plan is very simple. Every day he walks along a pre-defined route. The route of each day consists of $n$ moves, and each move can be described by $c_i$ and $d_i$: if he is currently at $(a_1, a_2, \ldots , a_{c_i}, \ldots, a_k)$, then in this move he will go to $(a_1, a_2, \ldots , a_{c_i} + d_i, \ldots , a_k)$, where $1 \le c_i \le k$ and $d_i \in \{-1, 1\}$. Xiao C will keep repeating this route until he walks out of the area, and then that day’s plan ends. (That is, after finishing step $n$, if Xiao C is still inside the area, he returns to step $1$ and walks the route again from the beginning.)

Xiao C is very confident about his speed, so he does not care about the actual time spent. He only wants to know: after $P$ days, how many WeChat steps has he farmed in total. Please help him compute it.

Input Format

The first line contains two integers $n, k$ separated by a single space, representing the number of moves in the route and the number of dimensions of the area.
The next line contains $k$ integers $w_i$ separated by a single space, representing the size of the area.
The next $n$ lines each contain two integers $c_i, d_i$ separated by a single space, in order describing the direction of each move. The meaning is given in the statement.

Output Format

Output one line with a single integer, the answer. The answer may be very large; you only need to output it modulo ${10}^9 + 7$.
If Xiao C’s plan would make it impossible for him to ever walk out of the area on some day, output one line with a single integer $-1$.

3 2
3 3
1 1
2 -1
1 1

21

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

10265

见附件中的 walk/walk3.in

见附件中的 walk/walk3.ans

见附件中的 walk/walk4.in

见附件中的 walk/walk4.ans

Hint

[Sample #1 Explanation]

Starting from $(1, 1)$ he will walk $2$ steps; starting from $(1, 2)$ he will walk $4$ steps; starting from $(1, 3)$ he will walk $4$ steps.
Starting from $(2, 1)$ he will walk $2$ steps; starting from $(2, 2)$ he will walk $3$ steps; starting from $(2, 3)$ he will walk $3$ steps.
Starting from $(3, 1)$ he will walk $1$ step; starting from $(3, 2)$ he will walk $1$ step; starting from $(3, 3)$ he will walk $1$ step.
In total, $21$ steps.

[Constraints]

For all test points, 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\}$.

Translated by ChatGPT 5