题目描述

维护一个 $n \times n$ 的矩阵 $A$，元素 $A_{i,j}$ 表示第 $i$ 行第 $j$ 列的元素（行和列均从 $1$ 开始标号）。初始时，$A_{i,j} = (i+1)^j \mod 998244353$。

需要支持 $q$ 个操作，操作分为两类，所有操作结束后需计算特定格式的矩阵总和（对 $10^9+7$ 取模）。

操作定义

1. 旋转操作：格式为 1 x1 y1 x2 y2

   • 保证 $y_2 - x_2 = y_1 - x_1$，即操作的子矩形为正方形。
   • 令 $d = x_2 - x_1 + 1$（正方形边长），提取子矩阵 $A'$：$A'_{i,j} = A_{x_1+i-1, y_1+j-1}$（$1 \leq i,j \leq d$）。
   • 将 $A'$ 逆时针旋转 $90$ 度得到 $B'$：$B'_{i,j} = A'_{d-j+1, i}$（$1 \leq i,j \leq d$）。
   • 将 $B'$ 填回原矩阵：$A_{x_1+i-1, y_1+j-1} = B'_{i,j}$（$1 \leq i,j \leq d$）。

2. 加法操作：格式为 2 x1 y1 x2 y2 d

   • 对於子矩形 $[x_1, x_2] \times [y_1, y_2]$ 内所有元素加 $d$，即 $A_{i,j} = A_{i,j} + d$（$x_1 \leq i \leq x_2$，$y_1 \leq j \leq y_2$）。

最终输出要求

计算总和 $\left( \sum_{i=1}^n \sum_{j=1}^n A_{i,j} \times 12345^{(i-1)n + j} \right) \mod 1000000007$，并输出结果。

输入格式

• 第一行：两个整数 $n$ 和 $q$，分别表示矩阵大小和操作个数。
• 接下来 $q$ 行：每行若干整数，表示一个操作（格式对应上述两类操作）。

输出格式

输出一个整数，表示上述总和对 $1000000007$ 取模的结果。

样例 1

输入

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

说明

矩阵变化过程如下（红色标记旋转涉及元素，蓝色标记加法涉及元素）：

1. 初始矩阵： $\begin{bmatrix} 2 & \color{red}{4} & \color{red}{8} & \color{red}{16} \\ 3 & \color{red}{9} & \color{red}{27} & \color{red}{81} \\ 4 & \color{red}{16} & \color{red}{64} & \color{red}{256} \\ 5 & 25 & 125 & 625 \end{bmatrix}$
2. 第一次旋转操作后： $\begin{bmatrix} 2 & 16 & 81 & 256 \\ \color{blue}{3} & \color{blue}{8} & 27 & 64 \\ \color{blue}{4} & \color{blue}{4} & 9 & 16 \\ \color{blue}{5} & \color{blue}{25} & 125 & 625 \end{bmatrix}$
3. 第一次加法操作后： $\begin{bmatrix} 2 & 16 & 81 & 256 \\ \color{red}{6} & \color{red}{11} & 27 & 64 \\ \color{red}{7} & \color{red}{7} & 9 & 16 \\ 8 & 28 & 125 & 625 \end{bmatrix}$
4. 第二次旋转操作后： $\begin{bmatrix} \color{blue}{2} & \color{blue}{16} & \color{blue}{81} & \color{blue}{256} \\ 11 & 7 & 27 & 64 \\ 6 & 7 & 9 & 16 \\ 8 & 28 & 125 & 625 \end{bmatrix}$
5. 第二次加法操作后： $\begin{bmatrix} 7 & 21 & 86 & 261 \\ 11 & 7 & 27 & 64 \\ 6 & 7 & 9 & 16 \\ 8 & 28 & 125 & 625 \end{bmatrix}$

数据范围与提示

• 所有数据：$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$。
• 测试点信息如下：

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

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