Задача . G. Волшебный квадрат

У Aquamoon есть квадратик Рубика, который можно представить как матрицу размера \(n \times n\), причём элементы матрицы составляют перестановку чисел \(1, \ldots, n^2\).

Aquamoon можно производить над матрицей следующие операции:

• Сдвиг строки, т.е. сдвиг некоторой строки матрицы на несколько позиций (хотя бы на \(1\) и не более чем на \(n-1\)) вправо. Элементы, выходящие за правую границу матрицы, сдвигаются в начало строки. Так, например, сдвиг строки \(\begin{pmatrix} a & b & c \end{pmatrix}\) на \(2\) позиции превратит её в \(\begin{pmatrix} b & c & a \end{pmatrix}\);
• Сдвиг столбца, т.е. сдвиг некоторого столбца матрицы на несколько позиций (хотя бы на \(1\) и не более чем на \(n-1\)) вниз. Элементы, выходящие за нижнюю границу матрицы, сдвигаются в начало столбца. Так, например, сдвиг столбца \(\begin{pmatrix} a \\ b \\ c \end{pmatrix}\) на \(2\) позиции превратит его в \(\begin{pmatrix} b\\c\\a \end{pmatrix}\).

Строки матрицы пронумерованы от \(1\) до \(n\) сверху вниз, столбцы пронумерованы от \(1\) до \(n\) слева направо. Клетку на пересечении \(x\)-й строки и \(y\)-го столбца обозначим как \((x, y)\).

Aquamoon может выполнить несколько (возможно, ноль) операций, но она должна выполнять следующие ограничения:

• каждая строка и каждый столбец могут быть сдвинуты не более чем по одному разу;
• каждое число матрицы может быть сдвинуто не более чем дважды;
• итоговые смещения любых двух чисел, сдвинутых дважды, должны быть попарно различны. Формально, пусть числа \(a\) и \(b\) были сдвинуты по два раза. Пусть \(a\) изменило свою позицию с \((x_1,y_1)\) на \((x_2,y_2)\), а \(b\) изменило позицию с \((x_3,y_3)\) на \((x_4,y_4)\). Тогда \(x_2-x_1 \not\equiv x_4-x_3 \pmod{n}\) или \(y_2-y_1 \not\equiv y_4-y_3 \pmod{n}\).

Aquamoon интересно, сколькими способами она может преобразовать исходное состояние квадратика в некоторое заданное конечно состояние. Два способа считаются различными, если последовательности применяемых операций в них различны. Поскольку ответ может быть очень большим, выведите его по модулю modulo \(998\,244\,353\).