Петя является коллекционером красивых матриц.
Матрица размера \(n \times n\) является красивой, если:
- Все элементы матрицы являются целыми числами от \(1\) до \(n\);
- В строке все элементы различные;
- В столбце нет двух соседних одинаковых элементов.
Сегодня Петя купил красивую матрицу \(a\) размера \(n \times n\) и хочет определить ее редкость.
Редкость матрицы определяется, как ее номер в списке всех красивых матриц размера \(n \times n\), отсортированных в лексикографическом порядке. Сравнение матриц происходит построчно. (Нумерация начинается с нуля).
Так как красивых матриц очень много, то Пете будет достаточно узнать редкость матрицы \(a\) по модулю \(998\,244\,353\).
Выходные данные
Выведите одно целое число — редкость матрицы \(a\) по модулю \(998\,244\,353\).
Примечание
Для матриц размера \(2 \times 2\) существует всего \(2\) красивые матрицы:
Красивых матриц \(3 \times 3\) довольно много, вот первые \(5\) в лексикографическом порядке:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 1
1 2
|
1
|
|
2
|
3
1 2 3
2 3 1
3 1 2
|
1
|
|
3
|
3
1 2 3
3 1 2
2 3 1
|
3
|