{"problem":{"name":"[SNOI2024] 矩阵","description":{"content":"你要维护一个 $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_","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":8000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10061"},"statements":[{"statement_type":"Markdown","content":"你要维护一个 $n \\times n$ 的矩阵 $A$，其中第 $i$ 行第 $j$ 列的元素记作 $A_{i, j}$。行和列从 $1$ 开始标号。一开始，有 $A_{i, j} = (i + 1)^j \\bmod 998244353$。\n\n你需要支持 $q$ 个操作，每个操作是下面两种操作中的一种。\n\n- $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$ 度。\n  - 具体地，令 $d = x_2 - x_1 + 1$。\n  - 首先提取 $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}$。\n  - 然后将 $A'$ 旋转，得到一个 $d \\times d$ 的子矩阵 $B'$，令 $B'_{i, j} \\gets A'_{j, d - i + 1}$。\n  - 然后将 $B'$ 填回到 $A$ 中，对所有的 $i, j$（$1 \\le i, j \\le d$），令 $A_{i + x_1 - 1, j + y_1 - 1} \\gets B'_{i, j}$。\n- $2\\ x_1\\ y_1\\ x_2\\ y_2\\ d$。将子矩形 $[x_1, x_2] \\times [y_1, y_2]$ 内所有的元素加 $d$。\n  - 具体地，对于每个 $i$（$x_1 \\le i \\le x_2$）、$j$（$y_1 \\le j \\le y_2$），令 $A_{i, j} \\gets A_{i, j} + d$。\n\n你需要在所有操作结束之后，输出这个矩阵。由于输出可能很大，请输出\n$$ \\Biggl( \\sum_{i = 1}^{n} \\sum_{j = 1}^{n} A_{i, j} \\times {12345}^{(i - 1) n + j} \\Biggr) \\bmod 1000000007 $$\n的结果。\n\n## Input\n\n第一行两个整数 $n, q$ 表示矩阵大小和操作个数。  \n接下来 $q$ 行，每行若干个数，表示上面的某种操作。\n\n## Output\n\n输出一个整数，表示答案对 $1000000007$ 取模的结果。\n\n[samples]\n\n## Note\n\n**【样例 \\#1 解释】**\n\n对于第一个样例，矩阵分别为\n$$\\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}$$\n$$\\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}$$\n其中每个旋转操作对应的数字用红色表示，加操作对应的数字用蓝色表示。\n\n---\n\n**【样例 \\#3】**\n\n见附件中 `matrix/matrix3.in` 与 `matrix/matrix3.ans`，这个样例满足测试点 $5 \\sim 6$ 的条件限制。\n\n---\n\n**【样例 \\#4】**\n\n见附件中 `matrix/matrix3.in` 与 `matrix/matrix3.ans`，这个样例满足测试点 $9 \\sim 10$ 的条件限制。\n\n---\n\n**【数据范围】**\n\n对于所有的数据，保证 $1 \\le n \\le 3000$，$1 \\le q \\le 3000$。  \n对于每个操作，保证 $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\n具体如下：\n\n| 测试点编号 | $n \\le$ | $q \\le$ | 特殊性质 |\n|:-:|:-:|:-:|:-:|\n| $1$ | $100$ | $3000$ | 无 |\n| $2$ | $3000$ | $3000$ | A |\n| $3 \\sim 4$ | $3000$ | $2000$ | B |\n| $5 \\sim 6$ | $3000$ | $3000$ | B |\n| $7 \\sim 8$ | $3000$ | $2000$ | 无 |\n| $9 \\sim 10$ | $3000$ | $3000$ | 无 |\n\n特殊性质 A：保证没有第一类旋转操作。  \n特殊性质 B：保证没有第二类加法操作。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10061","tags":["各省省选","2024","O2优化","陕西"],"sample_group":[["4 4\n1 1 2 3 4\n2 2 1 4 2 3\n1 2 1 3 2\n2 1 1 1 4 5\n","984660761\n"],["10 10\n2 5 1 10 4 689412516\n1 3 4 3 4\n1 3 5 4 6\n1 4 1 8 5\n1 1 2 1 2\n1 4 2 7 5\n1 2 5 2 5\n2 3 3 3 9 856075030\n2 4 2 5 6 308750020\n2 1 5 9 7 252732904\n","94292030\n"]],"created_at":"2026-03-03 11:09:25"}}