题目描述
Problem Description
Xiao C loves running and is particularly keen on topping the WeChat step count leaderboard. To achieve this, he has devised a plan to maximize his step count on WeChat.
He has arrived at a spacious field where a person's position can be represented by a $k$-dimensional integer coordinate $(a_1, a_2, \ldots, a_k)$. The field has size constraints, with the $i$-th dimension having a size of $w_i$, thus a person's coordinates must satisfy $1 \le a_i \le w_i$ (for $1 \le i \le k$).
Xiao C plans to start from a new position in the field every day for the next $P = w_1 \times w_2 \times \cdots \times w_k$ days, effectively starting his step count plan from every possible position in the field.
His plan is straightforward: each day, he follows a predetermined route consisting of $n$ steps. Each step is defined by $c_i$ and $d_i$: if he is currently at $(a_1, a_2, \ldots, a_{c_i}, \ldots, a_k)$, he will move 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 repeat this route until he steps out of the field's boundaries, at which point he ends his day's plan (i.e., if he is still within the field after the $n$-th step, he will restart from the first step).
Xiao C is very confident in his speed and is not concerned about the time it takes. He simply wants to know the total number of steps he will have accumulated after $P$ days. Please help him calculate this.
Input Format
The first line contains two integers $n$ and $k$, separated by a single space. These represent the number of steps in the route and the number of dimensions of the field, respectively.
The next line contains $k$ integers $w_i$, separated by a single space, representing the size of each dimension of the field.
The following $n$ lines each contain two integers $c_i$ and $d_i$, separated by a single space, describing the direction of each step as per the problem description.
Output Format
Output a single integer, which is the answer modulo ${10}^9 + 7$. If Xiao C's plan would cause him to never exit the field on some day, output a single integer $-1$.
Sample Input and Output
Input Sample #1
3 2
3 3
1 1
2 -1
1 1
Output Sample #1
21
Input Sample #2
5 4
6 8 6 5
3 1
2 1
1 1
2 1
2 -1
Output Sample #2
10265
Input Sample #3
See attached file walk/walk3.in
Output Sample #3
See attached file walk/walk3.ans
Input Sample #4
See attached file walk/walk4.in
Output Sample #4
See attached file walk/walk4.ans
Notes/Hints
[Sample #1 Explanation]
Starting from $(1, 1)$ will take 2 steps, from $(1, 2)$ will take 4 steps, and from $(1, 3)$ will take 4 steps.
Starting from $(2, 1)$ will take 2 steps, from $(2, 2)$ will take 3 steps, and from $(2, 3)$ will take 3 steps.
Starting from $(3, 1)$ will take 1 step, from $(3, 2)$ will take 1 step, and from $(3, 3)$ will take 1 step.
Total is 21 steps.
[Data Range]
| Test Case Number | $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 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\}$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分