Background

有一天，世界上各个大型网络公司都遭到了大型 DDOS 攻击，一个自称 fumo 的组织宣称发动了这次攻击。于是，世界上很多大型网络公司都陷入恐慌。

Description

你是一名 $Abstergo$ 公司的员工，并负责公司的网络安全。

有天，你收到了一封没有署名的文件。 $Abstergo$ 公司的 $Boss$ 有预感，这封文件可能携带某种不知名的高级病毒。你需要对文件上的 $N\times N$ 的正数矩阵进行 $T$ 次操作，来确保开启文件后不会遭到病毒攻击。

对于每次操作，可能是以下的几种形式之一：

1. 求出矩阵的 $k$ 次幂。

2. 将现矩阵乘另给出的一个 $N\times N$ 的矩阵。

3. 输出现矩阵的 第 $i,j$ 项。

如果你是新人，你可能要先掌握一些线性代数相关知识

如果你成功破解文件，$Boss\ Wyk$ 将会给你升值加薪的奖励。

注意，邪恶的 $fumo$ 为了不让别人轻易破解，矩阵里面可能存在负数，你需要将其先转化为正数再进行计算。 由于计算过程中出现的数可能很大，你只需要输出对 $10^9+7$ 取模后的结果。

Format

Input

第一行包括两个整数 $T$ 和 $N$ ，代表 $T$ 次操作和矩阵大小 $N$ $(1<N<1000)$。

接下来 $N$ 行，每行 $N$ 个整数，表示给定的矩阵。

再接下来 $T$ 个操作，保证每次操作第一个数 $op\in[1,3]$ ，代表上述的三种操作。

若 $op=1$ ，则接着输入 $k$ ，代表求现矩阵的 $k$ 次幂。

若 $op=2$ ，则接下来 $N$ 行，每行 $N$ 个整数，表示要乘的矩阵。

若 $op=3$ ，则接着输入 $i,j$ ，表示输出矩阵的第 $i,j$ 的项。

Output

对于每个 $op=3$ ，输出一行数表示矩阵的第 $i,j$ 项。

接下来 $N$ 行，每行 $N$ 个整数，表示最后求出的矩阵。

Samples

1 2
1 1
1 1
1 2

2 2
2 2

2 3
1 2 8
2 5 6
5 1 2
3 2 2
1 2

5
45 20 36
42 35 58
17 17 50

Limitation

1s, 1024KiB