Петя является коллекционером красивых матриц.
Матрица размера \(n \times n\) является красивой, если:
Сегодня Петя купил красивую матрицу \(a\) размера \(n \times n\) и хочет определить ее редкость.
Редкость матрицы определяется, как ее номер в списке всех красивых матриц размера \(n \times n\), отсортированных в лексикографическом порядке. Сравнение матриц происходит построчно. (Нумерация начинается с нуля).
Так как красивых матриц очень много, то Пете будет достаточно узнать редкость матрицы \(a\) по модулю \(998\,244\,353\).
В первой строке записано целое число \(n\) (\(1 \le n \le 2000\)) — размеры матрицы \(a\).
В последующих \(n\) строках записано по \(n\) целых чисел \(a_{i,j}\) (\(1 \le a_{i,j} \le n\)) — элементы матрицы \(a\).
Гарантируется, что матрица \(a\) удовлетворяет свойствам красивой матрицы.
Выведите одно целое число — редкость матрицы \(a\) по модулю \(998\,244\,353\).
Для матриц размера \(2 \times 2\) существует всего \(2\) красивые матрицы:
Красивых матриц \(3 \times 3\) довольно много, вот первые \(5\) в лексикографическом порядке:
2 2 1 1 2
1
3 1 2 3 2 3 1 3 1 2
3 1 2 3 3 1 2 2 3 1
3
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач