#2134231398. [NOIP 2020] 微信步数

内存限制:512 MiB 时间限制:1000 ms 输入文件:walk.in 输出文件:walk.out
题目类型:传统 评测方式:文本比较
上传者: j27eGU

题目描述

一. 题目概况

中文题目名称 微信步数
英文题目与子目录名
可执行文件名
输入文件名
输出文件名
每个测试点时限
测试点数目
测试点分值
附加样例文件
结果比较方式 全文比较(过滤行末空格)
题目类型 传统
运行内存上限

二. 提交源程序文件名

对于C++语言
对于C语言
对于pascal语言

4.微信步数

()

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

他来到了一处空旷的场地,处于该场地中的人可以用 维整数坐标 来表示其位置。场地有大小限制,第 维的大小为 ,因此处于场地中的人其坐标应满足 )。

小 C 打算在接下来的 天中,每天从场地中一个新的位置出发,开始他的刷步数计划(换句话说,他将会从场地中每个位置都出发一次进行计划)。

他的计划非常简单,每天按照事先规定好的路线行进,每天的路线由 步移动构成,每一步可以用 表示:若他当前位于 ,则这一步他将会走到 ,其中 。小 C 将会不断重复这个路线,直到他走出了场地的范围才结束一天的计划。(即走完第 步后,若小 C 还在场内,他将回到第 步从头再走一遍)。

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

输入格式

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

输出格式

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

样例

样例#1

输入样例#1

3 2
3 3
1 1
2 -1
1 1

输出样例#1

21

样例#2

输入样例#2

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

输出样例#2

10265

样例#3

输入样例#3

见附件中的 walk/walk3.in

输出样例#3

见附件中的 walk/walk3.ans

样例#4

输入样例#4

见附件中的 walk/walk4.in

输出样例#4

见附件中的 walk/walk4.ans

数据范围与提示

【样例 #1 解释】

出发将走 步,从 出发将走 步,从 出发将走 步。
出发将走 步,从 出发将走 步,从 出发将走 步。
出发将走 步,从 出发将走 步,从 出发将走 步。
共计 步。

【数据范围】

测试点编号

对于所有测试点,保证

原题链接:https://www.luogu.com.cn/problem/P7116