#P18938. [Mladen Manev 2019 A3] bmaze / 无限迷宫

[Mladen Manev 2019 A3] bmaze / 无限迷宫

无限迷宫(Infinite Maze)

题目描述

一个迷宫有 MM 行、无限多列,行列下标从1开始。第 ii 行、第 jj 列的格子编号为 i+(j−1)Mi+(j-1)M。

迷宫每 KK 列构成一个区块。第一个区块中有一些禁用格子,后面每个区块重复相同的禁用位置。

一条路径可以从第一个区块中的任意允许格子开始。每一步只能走向下一列的同一行、上一行或下一行,不能离开迷宫,也不能进入禁用格子。求终点位于第 NN 列的不同路径数,答案对 109+710^9+7 取模。起点可以位于第一个区块的任何一列;仅起点不同的路径也不同。

禁用格子通过一个长度为 PP 的编号序列指定。令 Q1=QQ_1=Q,之后

Qi=((Qi−1A+B) mod C)+1.Q_i=((Q_{i-1}A+B)\bmod C)+1.

序列中出现的编号均为禁用格子;同一编号重复出现时仍只禁用该格子一次。

输入格式

第一行三个整数 M,N,KM,N,K。第二行五个整数 P,Q,A,B,CP,Q,A,B,C。

输出格式

输出所求路径数模 109+710^9+7 的结果。

数据范围

1≤M≤1001\le M\le100,1≤K≤N≤10161\le K\le N\le10^{16},K≤10000K\le10000,1≤A,B,C,P,Q≤MK1\le A,B,C,P,Q\le MK。

样例

4 8 3
7 1 2 7 11
12

样例说明

第一个区块的禁用编号为1、10、6、9、4、5、7。允许的起点编号为2、3、8、11、12。第8列中只有编号32的格子允许进入,共有12条路径到达这里。

来源与数据说明

2019 年 Dr. Mladen Manev,A3,原题名 bmaze。赛事资料,原文题面见附件 statement.pdf。

本题使用官方原始测试数据;评测接口按本站环境适配。总分为 100 分。