P10061 [SNOI2024] 矩阵

你要维护一个 $n \times n$ 的矩阵 $A$，其中第 $i$ 行第 $j$ 列的元素记作 $A_{i, j}$。行和列从 $1$ 开始标号。一开始，有 $A_{i, j} = (i + 1)^j \bmod 998244353$。 你需要支持 $q$ 个操作，每个操作是下面两种操作中的一种。 - $1\ x_1\ y_1\ x_2\ y_2$，这里保证 $y_2 - x_2 = y_1 - x_1$。将子矩形 $[x_1, x_2] \times [y_1, y_2]$ 逆时针旋转 $90$ 度。 - 具体地，令 $d = x_2 - x_1 + 1$。 - 首先提取 $d \times d$ 的子矩阵 $A'$，对于所有的 $i, j$（$1 \le i, j \le d$），令 $A'_{i, j} \gets A_{x_1 + i - 1, y_1 + j - 1}$。 - 然后将 $A'$ 旋转，得到一个 $d \times d$ 的子矩阵 $B'$，令 $B'_{i, j} \gets A'_{j, d - i + 1}$。 - 然后将 $B'$ 填回到 $A$ 中，对所有的 $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$。将子矩形 $[x_1, x_2] \times [y_1, y_2]$ 内所有的元素加 $d$。 - 具体地，对于每个 $i$（$x_1 \le i \le x_2$）、$j$（$y_1 \le j \le y_2$），令 $A_{i, j} \gets A_{i, j} + d$。 你需要在所有操作结束之后，输出这个矩阵。由于输出可能很大，请输出 $$ \Biggl( \sum_{i = 1}^{n} \sum_{j = 1}^{n} A_{i, j} \times {12345}^{(i - 1) n + j} \Biggr) \bmod 1000000007 $$ 的结果。

无

无

**【样例 \#1 解释】** 对于第一个样例，矩阵分别为 $$\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}$$ 其中每个旋转操作对应的数字用红色表示，加操作对应的数字用蓝色表示。 --- **【样例 \#3】** 见附件中 `matrix/matrix3.in` 与 `matrix/matrix3.ans`，这个样例满足测试点 $5 \sim 6$ 的条件限制。 --- **【样例 \#4】** 见附件中 `matrix/matrix3.in` 与 `matrix/matrix3.ans`，这个样例满足测试点 $9 \sim 10$ 的条件限制。 --- **【数据范围】** 对于所有的数据，保证 $1 \le n \le 3000$，$1 \le q \le 3000$。 对于每个操作，保证 $1 \le x_1 \le x_2 \le n$，$1 \le y_1 \le y_2 \le n$，$1 \le d \le {10}^9$。 具体如下： | 测试点编号 | $n \le$ | $q \le$ | 特殊性质 | |:-:|:-:|:-:|:-:| | $1$ | $100$ | $3000$ | 无 | | $2$ | $3000$ | $3000$ | A | | $3 \sim 4$ | $3000$ | $2000$ | B | | $5 \sim 6$ | $3000$ | $3000$ | B | | $7 \sim 8$ | $3000$ | $2000$ | 无 | | $9 \sim 10$ | $3000$ | $3000$ | 无 | 特殊性质 A：保证没有第一类旋转操作。 特殊性质 B：保证没有第二类加法操作。