У Tokitsukaze есть перестановка \(p\). Она выполнила следующую операцию над \(p\) ровно \(k\) раз: за одну операцию для каждого \(i\) от \(1\) до \(n - 1\) по порядку, если \(p_i\) > \(p_{i+1}\), поменять местами \(p_i\), \(p_{i+1}\). Сделав ровно \(k\) таких операций, Tokitsukaze получила новую последовательность \(a\), очевидно, что последовательность \(a\) также является перестановкой.
После этого Tokitsukaze записала на бумаге последовательность значений \(v\) над \(a\). Обозначим последовательность значений \(v\) перестановки \(a\) длины \(n\), как \(v_i=\sum_{j=1}^{i-1}[a_i < a_j]\), где значение \([a_i < a_j]\) определяется как \(1\), если \(a_i < a_j\), иначе \(0\) (другими словами, \(v_i\) равно количеству элементов больших \(a_i\), которые находятся левее позиции \(i\)). Затем Tokitsukaze ушла на работу.
В доме Tokitsukaze живут три непослушных кота. Придя домой, она обнаружила, что бумага со значениями последовательности \(v\) прогрызена кошками в нескольких местах, и значения в этих местах неясно и может быть любым. Она забыла, какой была исходная перестановка \(p\). Она хочет знать, сколько существует различных перестановок \(p\), для которых последовательность значений \(v\) новой перестановки \(a\) после ровно \(k\) операций имеют ту же последовательность значений, что и последовательность \(v\), написанная на бумаге (не принимая во внимание испорченные позиции).
Поскольку ответ может быть слишком большим, выведите его по модулю \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество различных перестановок по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных только перестановка \(p=[5,4,3,2,1]\) удовлетворяет условию.
Во втором наборе входных данных имеется \(6\) перестановок, удовлетворяющих условию ограничения, а именно:
- \([3,4,5,2,1]\) \(\rightarrow\) \([3,4,2,1,5]\) \(\rightarrow\) \([3,2,1,4,5]\);
- \([3,5,4,2,1]\) \(\rightarrow\) \([3,4,2,1,5]\) \(\rightarrow\) \([3,2,1,4,5]\);
- \([4,3,5,2,1]\) \(\rightarrow\) \([3,4,2,1,5]\) \(\rightarrow\) \([3,2,1,4,5]\);
- \([4,5,3,2,1]\) \(\rightarrow\) \([4,3,2,1,5]\) \(\rightarrow\) \([3,2,1,4,5]\);
- \([5,3,4,2,1]\) \(\rightarrow\) \([3,4,2,1,5]\) \(\rightarrow\) \([3,2,1,4,5]\);
- \([5,4,3,2,1]\) \(\rightarrow\) \([4,3,2,1,5]\) \(\rightarrow\) \([3,2,1,4,5]\).
Таким образом, ровно через \(2\) операции все они станут \(a=[3,2,1,4,5]\), чья последовательность значений равна \(v=[0,1,2,0,0]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 0
0 1 2 3 4
5 2
-1 1 2 0 0
5 2
0 1 1 0 0
|
1
6
6
|