You need to maintain an $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 1-indexed. Initially, $A_{i,j} = (i + 1)^j \pmod{998244353}$.

You need to support $q$ operations, where 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]$ counter-clockwise by 90 degrees.
  • 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} \leftarrow A_{x_1+i-1, y_1+j-1}$.
  • Then, rotate $A'$ to obtain a $d \times d$ sub-matrix $B'$, where $B'_{i,j} \leftarrow A'_{j, d-i+1}$.
  • Then, fill $B'$ back into $A$, where for all $i, j$ ($1 \le i, j \le d$), $A_{i+x_1-1, j+y_1-1} \leftarrow 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$), $A_{i,j} \leftarrow A_{i,j} + d$.

After all operations are completed, you need to output the matrix. Since the output can be very large, please output the result of: $$\left( \sum_{i=1}^{n} \sum_{j=1}^{n} A_{i,j} \times 12345^{(i-1)n+j} \right) \pmod{1000000007}$$

Input

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

Output

Output to the file matrix.out. Output a single integer representing the result of the answer modulo $1000000007$.

Examples

Input 1

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

Output 1

984660761

Note

For the first example, the matrices are:

Numbers corresponding to each rotation operation are shown in red, and numbers corresponding to addition operations are shown in blue.

Input 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 2

94292030

Constraints

For all data, 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$.

Special Property A: Guaranteed no type 1 rotation operations. Special Property B: Guaranteed no type 2 addition operations.