Дана перестановка \(p\) длины \(n\).
Найдите количество перестановок \(q\) длины \(n\), которые удовлетворяют следующему условию:
- для каждого \(1 \le i < n\), \(\max(q_1,\ldots,q_i) \neq \max(p_1,\ldots,p_i)\).
Поскольку ответ может быть очень большим, выведите ответ по модулю \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных выведите одно число — ответ по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных \(p = [2, 1]\). Единственной подходящей \(q\) является \([1, 2]\). Действительно, нам нужно выполнить неравенство \(q_1 \neq p_1\). Оно выполнено только для \(q = [1, 2]\).
Во втором наборе входных данных \(p = [1, 2, 3]\). Так что \(q\) должна удовлетворять двум неравенствам: \(q_1 \neq p_1\) и \(\max(q_1, q_2) \neq \max(1, 2) = 2\). Можно доказать, что это выполняется только для следующих \(3\) перестановок:
- \(q = [2, 3, 1]\): в этом случае \(q_1 = 2 \neq 1\) and \(\max(q_1, q_2) = 3 \neq 2\);
- \(q = [3, 1, 2]\): в этом случае \(q_1 = 3 \neq 1\) and \(\max(q_1, q_2) = 3 \neq 2\);
- \(q = [3, 2, 1]\): в этом случае \(q_1 = 3 \neq 1\) and \(\max(q_1, q_2) = 3 \neq 2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2
2 1
3
1 2 3
3
3 1 2
4
2 4 1 3
5
3 5 1 4 2
15
6 13 2 8 7 11 1 3 9 15 4 5 12 10 14
|
1
3
2
4
18
424488915
|