D. Tokitsukaze и перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У 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$$$.

Входные данные

Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Каждый набор входных данных состоит из двух строк.

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 10^6$$$; $$$0 \leq k \leq n-1$$$) — длина перестановки и точное количество операций.

Вторая строка содержит $$$n$$$ целых чисел $$$v_1, v_2, \dots, v_n$$$ ($$$-1 \leq v_i \leq i-1$$$) — последовательность значений $$$v$$$. $$$v_i = -1$$$ означает, что $$$i$$$-я позиция $$$v$$$ испорчена и может принимать любое значение.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество различных перестановок по модулю $$$998\,244\,353$$$.

Пример
Входные данные
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
Примечание

В первом наборе входных данных только перестановка $$$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]$$$.