#1074. 「NOIP2020」微信步数

内存限制:512 MiB 时间限制:1000 ms 输入文件:walk.in 输出文件:walk.out
题目类型:传统 评测方式:文本比较
上传者: Victor_Huang

题目描述

小 C 喜欢跑步,并且非常喜欢在微信步数排行榜上刷榜,为此他制定了一个刷微信步数的计划。

他来到了一处空旷的场地,处于该场地中的人可以用 k 维整数坐标 (a_1, a_2, \ldots , a_k) 来表示其位置。场地有大小限制,第 i 维的大小为 w_i ,因此处于场地中的人其坐标应满足 1 \le a_i \le w_i(1 \le i \le k)

小 C 打算在接下来的 P = w_1 \times w_2 \times \ldots \times w_k 天中,每天从场地中一个新的位置出发,开始他的刷步数计划(话句话说,他将会从场地中每个位置都出发一次进行计划)。 他的计划非常简单,每天按照事先规定好的路线行进,每天的路线由 n 步移动构成,每一步可以用 c_i d_i 表示:若他当前位于 (a_1, a_2, \ldots , a_{c_i}, \ldots , a_k) ,则这一步他将会走到 (a_1, a_2, \ldots , a_{c_i} + d_i, \ldots , a_k) ,其中 1 \le c_i \le k d_i \in \{−1, 1\} 。小 C 将会不断重复这个路线,直到他走出了场地的范围才结束一天的计划。(即走完第 n 步后,若小 C 还在场内,他将回到第 1 步从头再走一遍)。

小 C 对自己的速度非常有自信,所以他并不在意具体耗费的时间,他只想知道 P 天之后,他一共刷出了多少步微信步数。请你帮他算一算。

输入格式

从文件 walk.in 中读入数据。

第一行两个用单个空格分隔的整数 n k 。分别表示路线步数与场地维数。

接下来一行 k 个用单个空格分隔的整数 w_i ,表示场地大小。

接下来 n 行每行两个用单个空格分隔的整数 c_i d_i ,依次表示每一步的方向,具体意义见题目描述。

输出格式

输出到文件 walk.out 中。

仅一行一个整数表示答案。答案可能很大,你只需要输出其对 10^9 + 7 取模后的值。

若小 C 的计划会使得他在某一天在场地中永远走不出来,则输出一行一个整数 -1

样例

样例 1

输入数据:

3 2
3 3
1 1
2 -1
1 1

输出数据:

21

(1, 1) 出发将走 2 步,从 (1, 2) 出发将走 4 步,从 (1, 3) 出发将走 4 步。
(2, 1) 出发将走 2 步,从 (2, 2) 出发将走 3 步,从 (2, 3) 出发将走 3 步。
(3, 1) 出发将走 1 步,从 (3, 2) 出发将走 1 步,从 (3, 3) 出发将走 1 步。
共计 21 步。

样例 2

输入数据:

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

输出数据:

10265

样例 3、4

见附加文件。

数据范围与提示

测试点编号 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 2 10^6
13 \sim 16 5 \times 10^5 10
17 \sim 20 3 10^9

对于所有测试点,保证 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\}