P2357 - 「NOIP2020」微信步数

内存限制：128 MB 时间限制：1.000 S

评测方式：文本比较命题人：

提交：2 解决：0

小 C 喜欢跑步，并且非常喜欢在微信步数排行榜上刷榜，为此他制定了一个刷微信步数的计划。
他来到了一处空旷的场地，处于该场地中的人可以用

k

维整数坐标

(a_{1}, a_{2}, \dots, a_{k})

来表示其位置。场地有大小限制，第

i

维的大小为

w_{i}

，因此处于场地中的人其坐标应满足

1 \leq a_{i} \leq w_{i}

（

1 \leq i \leq k

）。
小 C 打算在接下来的

P

w_{1} \times w_{2} \times \dots \times w_{k}

天中，每天从场地中一个新的位置出发，开始他的刷步数计划（话句话说，他将会从场地中每个位置都出发一次进行计划）。
他的计划非常简单，每天按照事先规定好的路线行进，每天的路线由

n

步移动构成，每一步可以用

c_{i}

与

d_{i}

表示：若他当前位于

(a_{1}, a_{2}, \dots, a_{c_{i}}, \dots, a_{k})

，则这一步他将会走到

(a_{1}, a_{2}, \dots, a_{c_{i}} + d_{i}, \dots, a_{k})

，其中

1 \leq c_{i} \leq k

，

d_{i} \in {- 1, 1}

。小 C 将会不断重复这个路线，直到他走出了场地的范围才结束一天的计划。（即走完第

n

步后，若小 C 还在场内，他将回到第

1

步从头再走一遍）。
小 C 对自己的速度非常有自信，所以他并不在意具体耗费的时间，他只想知道

P

天之后，他一共刷出了多少步微信步数。请你帮他算一算。

第一行两个用单个空格分隔的整数

n, k

。分别表示路线步数与场地维数。
接下来一行

k

个用单个空格分隔的整数

w_{i}

，表示场地大小。
接下来

n

行每行两个用单个空格分隔的整数

c_{i}, d_{i}

，依次表示每一步的方向，具体意义见题目描述。

仅一行一个整数表示答案。答案可能很大，你只需要输出其对

10^{9} + 7

取模后的值。
若小 C 的计划会使得他在某一天在场地中永远走不出来，则输出一行一个整数

- 1

。

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

步。
【数据范围】

测试点编号	$\le$	$\le$	$w_i \le$
$\$	$5$	$5$	$3$
$\$	$100$	$3$	$10$
$\$	$10^{5}$	$1$	$10^{5}$
$\$	$10^{5}$	$2$	$10^{6}$
$\$	$5 \times 10^{5}$	$10$	$10^{6}$
$\$	$5 \times 10^{5}$	$3$	$10^{9}$

对于所有测试点，保证

1 \leq n \leq 5 \times 10^{5}

，

1 \leq k \leq 10

，

1 \leq w_{i} \leq 10^{9}

，

d_{i} \in {- 1, 1}

。

「NOIP2020」提高组

提交提交记录统计讨论版露一手!

2357: 「NOIP2020」微信步数

题目描述

输入

输出

样例输入复制

样例输出复制

提示

来源/分类

2357: 「NOIP2020」微信步数

题目描述

输入

输出

样例输入 复制

样例输出 复制

提示

来源/分类

样例输入复制

样例输出复制