题目描述

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

输入

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

输出

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

输入样例

3 2
3 3
1 1
2 −1
1 1

输出样例

21

提示

【样例 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 步。 共计 21 步 【样例 2 输入】

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

【样例 2 输】

10265

【数据范围】

测试点编号	n ≤	k ≤	$w_i$≤
1 ∼ 3	5	5	3
4 ∼ 6	100	3	10
7 ∼ 8	$10^5$	1	$10^5$
9 ∼ 12		2	$10^6$
13 ∼ 16	$5 × 10^5$	10
17 ∼ 20		3	$10^9$

对于所有测试点，保证 $1 ≤ n ≤ 5 × 10^5$，$1 ≤ k ≤ 10$，$1 ≤ w_i ≤ 10^9$，$di ∈ \{−1, 1\}$。 【下载】 下载附件文件

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。