题目描述

输入格式

第一行两个用单个空格分隔的整数 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

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

10265

见附件中的 walk/walk3.in

见附件中的 walk/walk3.ans

见附件中的 walk/walk4.in

见附件中的 walk/walk4.ans

说明/提示

【样例 #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 步。

【数据范围】

对于所有测试点，保证1≤n≤5×10^5，1≤k≤10，1≤wi​≤10^9，di​∈{−1,1}。

附件下载

walk.zip90.95KB