题目描述

你要维护一个 $n \times n$ 的矩阵 $A$，其中第 $i$ 行第 $j$ 列的元素记作 $A_{i, j}$。行和列从 $1$ 开始标号。一开始，有 $A_{i, j} = (i + 1)^j \bmod 998244353$。

你需要支持 $q$ 个操作，每个操作是下面两种操作中的一种。

• $1\ x_1\ y_1\ x_2\ y_2$，这里保证 $y_2 - x_2 = y_1 - x_1$。将子矩形 $[x_1, x_2] \times [y_1, y_2]$ 逆时针旋转 $90$ 度。
  • 具体地，令 $d = x_2 - x_1 + 1$。
  • 首先提取 $d \times d$ 的子矩阵 $A'$，对于所有的 $i, j$（$1 \le i, j \le d$），令 $A'_{i, j} \gets A_{x_1 + i - 1, y_1 + j - 1}$。
  • 然后将 $A'$ 旋转，得到一个 $d \times d$ 的子矩阵 $B'$，令 $B'_{i, j} \gets A'_{j, d - i + 1}$。
  • 然后将 $B'$ 填回到 $A$ 中，对所有的 $i, j$（$1 \le i, j \le d$），令 $A_{i + x_1 - 1, j + y_1 - 1} \gets B'_{i, j}$。
• $2\ x_1\ y_1\ x_2\ y_2\ d$。将子矩形 $[x_1, x_2] \times [y_1, y_2]$ 内所有的元素加 $d$。
  • 具体地，对于每个 $i$（$x_1 \le i \le x_2$）、$j$（$y_1 \le j \le y_2$），令 $A_{i, j} \gets A_{i, j} + d$。

你需要在所有操作结束之后，输出这个矩阵。由于输出可能很大，请输出

的结果。

输入格式

第一行两个整数 $n, q$ 表示矩阵大小和操作个数。
接下来 $q$ 行，每行若干个数，表示上面的某种操作。

输出格式

输出一个整数，表示答案对 $1000000007$ 取模的结果。

4 4
1 1 2 3 4
2 2 1 4 2 3
1 2 1 3 2
2 1 1 1 4 5

984660761

10 10
2 5 1 10 4 689412516
1 3 4 3 4
1 3 5 4 6
1 4 1 8 5
1 1 2 1 2
1 4 2 7 5
1 2 5 2 5
2 3 3 3 9 856075030
2 4 2 5 6 308750020
2 1 5 9 7 252732904

94292030

提示

【样例 #1 解释】

对于第一个样例，矩阵分别为

其中每个旋转操作对应的数字用红色表示，加操作对应的数字用蓝色表示。

【样例 #3】

见附件中 matrix/matrix3.in 与 matrix/matrix3.ans，这个样例满足测试点 $5 \sim 6$ 的条件限制。

【样例 #4】

见附件中 matrix/matrix3.in 与 matrix/matrix3.ans，这个样例满足测试点 $9 \sim 10$ 的条件限制。

【数据范围】

对于所有的数据，保证 $1 \le n \le 3000$，$1 \le q \le 3000$。
对于每个操作，保证 $1 \le x_1 \le x_2 \le n$，$1 \le y_1 \le y_2 \le n$，$1 \le d \le {10}^9$。

具体如下：

特殊性质 A：保证没有第一类旋转操作。
特殊性质 B：保证没有第二类加法操作。