【ZYCode R2】A Dance of Fire and Ice and Wood and Gold and Soil
题目背景
zly 最近沉迷于 A Dance of Fire and Ice 导致他抽不出来时间陪他的 npy,她很愤怒,于是把他扔进了一个二维的游戏世界里。
题目描述
这个世界是一个 \(n \times n\) 的二维矩阵, 每个格子上有 F , I , W , G ,_S_ 中的任意一个。 zly 会选择一个 F 格子开始,然后在他周围的四个格子中选择 I 格子进入,然后一个 W 格子,然后一个 G 格子,然后一个 S 格子, 最后回到 F 格子。这样算一次操作。 为了取悦他的 npy , zly 想走出尽可能多的路径,为她绘出一幅五彩斑斓的画,现在他想知道, \(t\) 次操作后,他有多少种方案,对 \(1226999999\) 取模(它是质数!)
输入格式
第一行两个数, \(n\) 和 \(t\)
接下来一个 \(n \times n\) 的矩阵, 表示这个世界
输出格式
方案数,对 \(1226999999\) 取模
样例
样例输入 1
4 1
F I F F
I W G W
W G S F
W W W W
样例输出 1
7
提示说明
对于 \( 30\% \) 的数据 \(t \le 5\)
对于 \( 50\% \) 的数据 \(n \le 8\)
对于另外 \( 20\% \) 的数据 \(t \le 1000\)
对于 \( 100\% \) 的数据
- \(t \le 10^9\)
- \(n \le 50\)
- 保证数据随机生成
相关
在下列比赛中: