У Aquamoon есть квадратик Рубика, который можно представить как матрицу размера $$$n \times n$$$, причём элементы матрицы составляют перестановку чисел $$$1, \ldots, n^2$$$.
Aquamoon можно производить над матрицей следующие операции:
Строки матрицы пронумерованы от $$$1$$$ до $$$n$$$ сверху вниз, столбцы пронумерованы от $$$1$$$ до $$$n$$$ слева направо. Клетку на пересечении $$$x$$$-й строки и $$$y$$$-го столбца обозначим как $$$(x, y)$$$.
Aquamoon может выполнить несколько (возможно, ноль) операций, но она должна выполнять следующие ограничения:
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$$$.
431 2 34 5 67 8 97 2 31 4 56 8 931 2 34 5 67 8 93 2 16 5 49 7 831 2 34 5 67 8 97 8 12 3 45 6 931 2 34 5 67 8 93 8 45 1 97 6 2
1 0 0 4
В первом наборе входных данных единственный способ преобразовать исходную матрицу в конечную — сдвинуть вторую строку на $$$1$$$ вправо, а затем сдвинуть первый столбец на $$$1$$$ вниз.
Во втором наборе входных данных можно показать, что нет ни одного корректного способа преобразовать матрицу, так что ответ равен $$$0$$$.
Название |
---|