У 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$$$.