Problem Description

You need to maintain an $n \times n$ matrix $A$, where the element in row $i$ and column $j$ is denoted as $A_{i, j}$. Rows and columns are indexed starting from $1$. Initially, $A_{i, j} = (i + 1)^j \bmod 998244353$.

You need to support $q$ operations. Each operation is one of the following two types.

• $1\ x_1\ y_1\ x_2\ y_2$, where it is guaranteed that $y_2 - x_2 = y_1 - x_1$. Rotate the sub-rectangle $[x_1, x_2] \times [y_1, y_2]$ by $90$ degrees counterclockwise.
  • Specifically, let $d = x_2 - x_1 + 1$.
  • First, extract a $d \times d$ submatrix $A'$. For all $i, j$ ($1 \le i, j \le d$), set $A'_{i, j} \gets A_{x_1 + i - 1, y_1 + j - 1}$.
  • Then rotate $A'$ to obtain a $d \times d$ submatrix $B'$, and set $B'_{i, j} \gets A'_{j, d - i + 1}$.
  • Then write $B'$ back into $A$. For all $i, j$ ($1 \le i, j \le d$), set $A_{i + x_1 - 1, j + y_1 - 1} \gets B'_{i, j}$.
• $2\ x_1\ y_1\ x_2\ y_2\ d$. Add $d$ to all elements in the sub-rectangle $[x_1, x_2] \times [y_1, y_2]$.
  • Specifically, for each $i$ ($x_1 \le i \le x_2$) and $j$ ($y_1 \le j \le y_2$), set $A_{i, j} \gets A_{i, j} + d$.

After all operations are finished, output this matrix. Since the output can be very large, please output the value of

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

instead.

Input Format

The first line contains two integers $n, q$, representing the matrix size and the number of operations.
The next $q$ lines each contain several numbers, describing one of the operations above.

Output Format

Output one integer, representing the answer modulo $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

Hint

[Sample #1 Explanation]

For the first sample, the matrix is respectively

$$\begin{bmatrix} 2 & {\textcolor{red}{4}} & {\textcolor{red}{8}} & {\textcolor{red}{16}} \\ 3 & {\textcolor{red}{9}} & {\textcolor{red}{27}} & {\textcolor{red}{81}} \\ 4 & {\textcolor{red}{16}} & {\textcolor{red}{64}} & {\textcolor{red}{256}} \\ 5 & 25 & 125 & 625 \end{bmatrix} \to \begin{bmatrix} 2 & 16 & 81 & 256 \\ {\textcolor{blue}{3}} & {\textcolor{blue}{8}} & 27 & 64 \\ {\textcolor{blue}{4}} & {\textcolor{blue}{4}} & 9 & 16 \\ {\textcolor{blue}{5}} & {\textcolor{blue}{25}} & 125 & 625 \end{bmatrix} \to \begin{bmatrix} 2 & 16 & 81 & 256 \\ {\textcolor{red}{6}} & {\textcolor{red}{11}} & 27 & 64 \\ {\textcolor{red}{7}} & {\textcolor{red}{7}} & 9 & 16 \\ 8 & 28 & 125 & 625 \end{bmatrix}$$$$\to \begin{bmatrix} {\textcolor{blue}{2}} & {\textcolor{blue}{16}} & {\textcolor{blue}{81}} & {\textcolor{blue}{256}} \\ 11 & 7 & 27 & 64 \\ 6 & 7 & 9 & 16 \\ 8 & 28 & 125 & 625 \end{bmatrix} \to \begin{bmatrix} 7 & 21 & 86 & 261 \\ 11 & 7 & 27 & 64 \\ 6 & 7 & 9 & 16 \\ 8 & 28 & 125 & 625 \end{bmatrix}$$

The numbers corresponding to each rotation operation are marked in red, and the numbers corresponding to each addition operation are marked in blue.

---

[Sample #3]

See the attachments matrix/matrix3.in and matrix/matrix3.ans. This sample satisfies the constraints of test points $5 \sim 6$.

---

[Sample #4]

See the attachments matrix/matrix3.in and matrix/matrix3.ans. This sample satisfies the constraints of test points $9 \sim 10$.

---

[Constraints]

For all testdata, it is guaranteed that $1 \le n \le 3000$ and $1 \le q \le 3000$.
For each operation, it is guaranteed that $1 \le x_1 \le x_2 \le n$, $1 \le y_1 \le y_2 \le n$, and $1 \le d \le {10}^9$.

Details are as follows:

Test Point ID	$n \le$	$q \le$	Special Property
$1$	$100$	$3000$	None
$2$	$3000$		A
$3 \sim 4$		$2000$	B
$5 \sim 6$		$3000$
$7 \sim 8$		$2000$	None
$9 \sim 10$		$3000$

Special property A: It is guaranteed that there are no type 1 rotation operations.
Special property B: It is guaranteed that there are no type 2 addition operations.

Translated by ChatGPT 5