Matrix Operations and Rotations

We are given an (n \times n) matrix (A) where the element in the (i)-th row and (j)-th column (1-indexed) is defined as [ A_{i,j} = (i+1)^j \bmod 998244353, ] initially. You need to process (q) operations of the following two types:

1. Rotation Operation: The operation is given as \(1\ x_1\ y_1\ x_2\ y_2\) (with the guarantee that \(y_2 - y_1 = x_2 - x_1\)). Let \(d = x_2 - x_1 + 1\). First, extract the \(d \times d\) submatrix \(A'\) from \(A\) defined by \[ A'_{i,j} = A_{x_1+i-1,\,y_1+j-1} \quad \text{for } 1 \le i,j \le d. \] Then compute a new \(d \times d\) matrix \(B'\) by rotating \(A'\) counterclockwise by 90 degrees, i.e., \[ B'_{i,j} = A'_{j,\,d-i+1} \quad \text{for } 1 \le i,j \le d. \] Finally, write \(B'\) back to \(A\) in the same position (i.e., \(A_{x_1+i-1,\,y_1+j-1} = B'_{i,j}\) for every \(1 \le i,j \le d\)).
2. Addition Operation: The operation is given as \(2\ x_1\ y_1\ x_2\ y_2\ d\). For every \(i\) and \(j\) in the rectangle \([x_1, x_2] \times [y_1, y_2]\), update \[ A_{i,j} = A_{i,j} + d. \]

After processing all (q) operations, you need to output the value [ \left( \sum_{i=1}^{n} \sum_{j=1}^{n} A_{i,j} \times 12345^{(i-1)n + j} \right) \bmod 1000000007. ] Note that all exponentiation in the final summation is performed modulo (10^9+7).

inputFormat

The first line contains two integers (n) and (q) -- the size of the matrix and the number of operations. The following (q) lines each represent an operation in one of the two formats:

1. For a rotation: `1 x1 y1 x2 y2` (with \(y2 - y1 = x2 - x1\)).
2. For an addition: `2 x1 y1 x2 y2 d`.

All indices are 1-indexed.

outputFormat

Output a single integer, the final computed value: [ \Biggl( \sum_{i=1}^{n} \sum_{j=1}^{n} A_{i,j} \times 12345^{(i-1)n + j} \Biggr) \bmod 1000000007. ]

sample

2 2
2 1 1 2 2 1
1 1 1 2 2

/* The output is a computed integer modulo 1000000007 based on the operations. */