题目背景

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\)
- 保证数据随机生成