You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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