A93172.「SNOI2024」矩阵

你要维护一个 $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\leq i, j \leq d)$，令$A'_{i, j} \leftarrow A_{x_1 + i - 1, y_1 + j- 1}$。
  • 然后将 $A'$ 旋转，得到一个 $d\times d$ 的子矩阵 $B'$，令 $B'_{i, j} \leftarrow A'_{d - j + 1, i}$。
  • 然后将 $B'$ 填回到 $A$ 中，对所有的 $i, j (1\leq i, j \leq d)$，令 $A_{i + x_1 - 1, j + y_1 - 1} \leftarrow 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 \leq i \leq x_2), j (y_1 \leq j \leq y_2)$，令 $A_{i, j} \leftarrow A_{i, j} + d$。

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

$$\left( \sum_{i=1}^n \sum_{j=1}^n A_{i,j}\times 12345^{(i-1)n + j}\right) \bmod 1000000007$$

的结果。

第一行两个整数 $n, q$ 表示矩阵大小和操作个数。

接下来 $q$ 行，每行若干个数，表示上面的某种操作。

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

对于所有的数据，保证 $1\leq n \leq 3000$, $1 \leq q\leq 3000$。

对于每个操作，保证 $1\leq x_1 \leq x_2\leq n, 1\leq y_1\leq y_2 \leq n, 1\leq d \leq 10^9$。

具体如下：

测试点编号	$n\leq$	$q\leq$	特殊性质
$1$	$100$	$3000$
$2$	$3000$	$3000$	A
$ 3<>im4$	$3000$	$2000$	B
$ 5<>im6$	$3000$	$3000$	B
$ 7<>im8$	$3000$	$2000$
$9\sim10$	$3000$	$3000$

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

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