| Технокубок 2019 - Отборочный Раунд 4 |
|---|
| Закончено |
Петя является коллекционером красивых матриц.
Матрица размера $$$n \times n$$$ является красивой, если:
- Все элементы матрицы являются целыми числами от $$$1$$$ до $$$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 2 1 1 2
1
3 1 2 3 2 3 1 3 1 2
1
3 1 2 3 3 1 2 2 3 1
3
Для матриц размера $$$2 \times 2$$$ существует всего $$$2$$$ красивые матрицы:
Красивых матриц $$$3 \times 3$$$ довольно много, вот первые $$$5$$$ в лексикографическом порядке:
