Олимпиадный тренинг

Задача . 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\).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число \(t\) (\(1 \le t \le 2\cdot 10^4\)) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число \(n\) (\(3\le n \le 500\)).

В \(i\)-й из следующих \(n\) строк содержится \(n\) целых чисел \(a_{i1}, \ldots, a_{in}\), которые задают \(i\)-ю строчку исходной матрицы (\(1 \le a_{ij} \le n^2\)).

В \(i\)-й из следующих \(n\) строк содержится \(n\) целых чисел \(b_{i1}, \ldots, b_{in}\), которые задают \(i\)-ю строчку конечной матрицы (\(1 \le b_{ij} \le n^2\)).

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

Гарантируется, что сумма значений \(n^2\) по всем наборам входных данных не превосходит \(250\,000\).

Выходные данные

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

Если решения не существует, выведите одно целое число \(0\).

Примечание

В первом наборе входных данных единственный способ преобразовать исходную матрицу в конечную — сдвинуть вторую строку на \(1\) вправо, а затем сдвинуть первый столбец на \(1\) вниз.

Во втором наборе входных данных можно показать, что нет ни одного корректного способа преобразовать матрицу, так что ответ равен \(0\).


Примеры
№Входные данныеВыходные данные
1
4
3
1 2 3
4 5 6
7 8 9
7 2 3
1 4 5
6 8 9
3
1 2 3
4 5 6
7 8 9
3 2 1
6 5 4
9 7 8
3
1 2 3
4 5 6
7 8 9
7 8 1
2 3 4
5 6 9
3
1 2 3
4 5 6
7 8 9
3 8 4
5 1 9
7 6 2
1
0
0
4
Статистика успешных решений по компиляторам
 Кол-во
С++3