P7116 [NOIP2020] WeChat Step Count.

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.

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 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$.

**[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]** | Test Point ID | $n \le$ | $k \le$ | $w_i \le$ | |:-:|:-:|:-:|:-:| | $1 \sim 3$ | $5$ | $5$ | $3$ | | $4 \sim 6$ | $100$ | $3$ | $10$ | | $7 \sim 8$ | ${10}^5$ | $1$ | ${10}^5$ | | $9 \sim 12$ | ${10}^5$ | $2$ | ${10}^6$ | | $13 \sim 16$ | $5 \times {10}^5$ | $10$ | ${10}^6$ | | $17 \sim 20$ | $5 \times {10}^5$ | $3$ | ${10}^9$ | 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