Problem Description

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

You are required to support $q$ operations, each of which 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$. This operation rotates the sub-matrix $[x_1, x_2] \times [y_1, y_2]$ 90 degrees counterclockwise.
• Specifically, let $d = x_2 - x_1 + 1$.
• First, extract the $d \times d$ sub-matrix $A'$, where for all $i, j$ ($1 \le i, j \le d$), $A'_{i, j} \gets A_{x_1 + i - 1, y_1 + j - 1}$.
• Then, rotate $A'$ to get a $d \times d$ sub-matrix $B'$, where $B'_{i, j} \gets A'_{j, d - i + 1}$.
• Finally, place $B'$ back into $A$, where for all $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$. This operation adds $d$ to all elements within the sub-matrix $[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$), $A_{i, j} \gets A_{i, j} + d$.

After all operations, you need to output the matrix. Since the output might be large, output the result of
$$ \Biggl( \sum_{i = 1}^{n} \sum_{j = 1}^{n} A_{i, j} \times {12345}^{(i - 1) n + j} \Biggr) \bmod 1000000007 $$

Input Format

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

Output Format

Output a single integer, which is the result modulo $1000000007$.

Sample Input and Output

Input Sample #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

Output Sample #1

984660761

Input Sample #2

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

Output Sample #2

94292030

Notes/Hints

[Sample #1 Explanation]

For the first sample, the matrix transitions as follows:
$$\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}$$
Where each rotation operation is represented in red and each addition operation is represented in blue.

[Data Range]

For all data, it is guaranteed that $1 \le n \le 3000$, $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$, $1 \le d \le {10}^9$.

The specific data ranges are as follows:

Special Condition A: No rotation operations of the first type are present.
Special Condition B: No addition operations of the second type are present.

见题面 Input 部分

见题面 Output 部分