#208. 微信步数

微信步数

题目描述

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

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

小 C 打算在接下来的 P=w1×w2××wkP = w_1 \times w_2 \times \ldots \times w_k 天中,每天从场地中一个新的位置出发,开始他的刷步数计划(换句话说,他将会从场地中每个位置都出发一次进行计划)。

他的计划非常简单,每天按照事先规定好的路线行进,每天的路线由 nn 步移动构成,每一步可以用 cic_idid_i 表示:若他当前位于 (a1,a2,,aci,,ak)(a_1, a_2, \ldots , a_{c_i}, \ldots , a_k),则这一步他将会走到 (a1,a2,,aci+di,,ak)(a_1, a_2, \ldots , a_{c_i} + d_i, \ldots , a_k),其中 1cik1 \le c_i \le kdi{1,1}d_i \in \{−1, 1\}。小 C 将会不断重复这个路线,直到他走出了场地的范围才结束一天的计划。(即走完第 nn 步后,若小 C 还在场内,他将回到第 11 步从头再走一遍)。

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

输入格式

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

第一行两个用单个空格分隔的整数 nnkk。分别表示路线步数与场地维数。
接下来一行 kk 个用单个空格分隔的整数 wiw_i,表示场地大小。
接下来 nn 行每行两个用单个空格分隔的整数 cic_idid_i,依次表示每一步的方向,具体意义见题目描述。

输出格式

输出到文件 walk.out 中。

仅一行一个整数表示答案。答案可能很大,你只需要输出其对 109+710^9 + 7 取模后的值。
若小 C 的计划会使得他在某一天在场地中永远走不出来,则输出一行一个整数 -1

3 2
3 3
1 1
2 -1
1 1
21

样例说明 1

(1,1)(1, 1) 出发将走 22 步,从 (1,2)(1, 2) 出发将走 44 步,从 (1,3)(1, 3) 出发将走 44 步。
(2,1)(2, 1) 出发将走 22 步,从 (2,2)(2, 2) 出发将走 33 步,从 (2,3)(2, 3) 出发将走 33 步。
(3,1)(3, 1) 出发将走 11 步,从 (3,2)(3, 2) 出发将走 11 步,从 (3,3)(3, 3) 出发将走 11 步。
共计 2121 步。

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

样例 3

见附加文件中的 walk3.inwalk3.ans

样例 4

见附加文件中的 walk4.inwalk4.ans

数据范围与提示

测试点编号 nn \le kk \le wiw_i \le
131 \sim 3 55 33
464 \sim 6 100100 33 1010
787 \sim 8 10510^5 11 10510^5
9129 \sim 12 22 10610^6
131613 \sim 16 5×1055 \times 10^5 1010
172017 \sim 20 33 10910^9

对于所有测试点,保证 1n5×1051 \le n \le 5 \times 10^51k101 \le k \le 101wi1091 \le w_i \le 10^9di{1,1}d_i \in \{−1, 1\}