小 C 喜欢跑步，并且非常喜欢在微信步数排行榜上刷榜，为此他制定了一个刷微信步数的计划。
他来到了一处空旷的场地，处于该场地中的人可以用 k 维整数坐标 (a1,a2,…,ak) 来表示其位置。场地有大小限制，第 i维的大小为 wi，因此处于场地中的人其坐标应满足1≤ai≤wi（1≤i≤k）。
小 C 打算在接下来的 P=w1×w2×⋯×wk 天中，每天从场地中一个新的位置出发，开始他的刷步数计划（换句话说，他将会从场地中每个位置都出发一次进行计划）。
他的计划非常简单，每天按照事先规定好的路线行进，每天的路线由 nn 步移动构成，每一步可以用 ci 与 di 表示：若他当前位于 (a1,a2,…,aci,…,ak)，则这一步他将会走到(a1,a2,…,aci+di,…,ak)，其中 1≤ci≤k，di∈{−1,1}。小 C 将会不断重复这个路线，直到他走出了场地的范围才结束一天的计划。（即走完第 n 步后，若小 C 还在场内，他将回到第 1 步从头再走一遍）。
小 C 对自己的速度非常有自信，所以他并不在意具体耗费的时间，他只想知道 P 天之后，他一共刷出了多少步微信步数。请你帮他算一算。

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

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

【样例 1 输入】
3 2
3 3
1 1
2 -1
1 1

【样例 2 输入】
5 4
6 8 6 5
3 1
2 1
1 1
2 1
2 -1

【样例 1 输出】
21

【样例 2 输出】
10265

点此下载样例

【样例 #1 解释】
 
从 (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 步。
共计 2121 步。
tle="1607501518715306.jpg" />