P10061 [SNOI2024] Matrix

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.

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

**[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$ | $3000$ | A | | $3 \sim 4$ | $3000$ | $2000$ | B | | $5 \sim 6$ | $3000$ | $3000$ | B | | $7 \sim 8$ | $3000$ | $2000$ | None | | $9 \sim 10$ | $3000$ | $3000$ | None | 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