题目描述

徐老师历经艰难，终于从洛基手中得到了宇宙魔方！

只要解开宇宙魔方，他就能从中获得空间宝石，从此造(wei)福(huo)人(ren)类(jian)

但是宇宙魔方的不是那么容易解开的，宇宙魔方的表面存在一个 $N * N$ 的网格阵法

每格阵法内封印着一股空间能量，并且每一股空间能量强度都不同，一开始阵法中的网格能量均由从上往下，从左往右的顺序依次增强，依次为 $1 \sim N * N$

例如一个 $5 * 5$ 的网格阵法初始情况如下

1  2  3  4  5
 6  7  8  9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

而徐老师发现在解密时，他每次可以选择一个 $2 * 2$ 的矩阵顺时针旋转 $90°$

为了方便描述旋转操作，徐老师将所有可操作的矩阵按从上往下，从左往右的顺序依次编号，依次为 $1 \sim (N-1) * (N-1)$

例如如上网格阵法，编号为 $6$ 的可操作矩阵为

7  8
12 13

而现在徐老师翻阅了阿斯加德所有的古籍，终于发现了若干条解密的指令，徐老师对指令进行了简单的整合:

一次指令的格式如下：m k a1,a2,a3,a4...ak

这个指令是由 $k$ 次旋转操作构成，依次旋转编号为 $a_1,a_2,a_3 ... a_k$ 的可操作性矩阵，并且这组旋转操作需要重复 $m$ 次，这样总共 $k * m$ 次操作构成了一次指令

而非常可惜的是，徐老师虽然找到了解密的指令，但是这些指令执行的顺序已经无从得知

所以徐老师只能边研究指令之间的关系，边进行测试，测试时徐老师有两种操作：

• 操作格式为 pos m k a1 a2 a3 ... ak 表示徐老师现在需要将这组指令放到当前指令序列的第 pos 个指令之后
• 操作格式为 -1，表示徐老师尝试用当前的指令序列进行一次解密，即输出按照当前指令序列操作以后的阵法情况

徐老师现在将所有的精力放在了研究指令之间的关系上，他希望由你来帮他进行指令序列的测试，请你帮帮他！

输入格式

输入一行包含两个整数 $N,M$ 表示宇宙魔方阵法的大小以及徐老师一共会给出 $M$ 次操作

接下来 $M$ 行每行包含一个操作

对于第一种操作，输入格式为 pos m k a1 a2 a3 ... ak

对于第二种操作，输入只有一个整数 $-1$

输出格式

对于每次的 $-1$ 输出当前指令序列操作以后的阵法情况，由于输出量可能太大

请你输出输出$(\sum_{i=1}^{N \times N}a[i] * 25^{i-1})$ 的结果，并对 $1e9+7$ 取模

数据范围

测试点$1$：$M\leq 1000,m=1,k=1$。

测试点$2,3$：$M \leq 10^5,m\leq 10^9,\sum k\leq 2 * 10^{5}$，保证每个指令都接在当前指令序列的最末尾。

测试点$4$：$M\leq 10^5,m \leq 10^9,\sum k \leq2 * 10^{5},N=2$。

测试点$5,6,7$：$M \leq 1000,m \leq 10^9,\sum k \leq 2 * 10^{5}$。

测试点$8,9,10$：没有特殊限制。

对于所有数据：$M \leq 10^5,m \leq 10^9,\sum k \leq 2 * 10^{5},N \leq 5$。

样例输入

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

样例输出

952776816
53500096
992339296

样例解释

对于第一次查询，此时没有操作，即直接输出

1  2  3  4  5
 6  7  8  9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

对于第二次查询，此时的操作序列为

1 1 6

即对 $6$ 号可操作矩阵进行一次旋转 此时操作后的阵法变成

1  2  3  4  5
 6 12  7  9 10
11 13  8 14 15
16 17 18 19 20
21 22 23 24 25

对于第三次查询，此时的操作序列为

2 2 3 4
1 1 8
1 1 6

即旋转顺序为 3 4 3 4 8 6 此时操作后的阵法变成

1  2  9  4  8
 6 12  7 14  5
11 13 10 15  3
16 17 18 19 20
21 22 23 24 25