E. PermutationForces II
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$a$$$ длины $$$n$$$. Напомним, что перестановкой называется массив из $$$n$$$ различных чисел от $$$1$$$ до $$$n$$$ в произвольном порядке.

Ваша сила равна $$$s$$$. Вы можете выполнить $$$n$$$ операций с перестановкой $$$a$$$. $$$i$$$-я операция состоит в следующем:

  • Выберите два значения $$$x$$$ и $$$y$$$ такие, что $$$i \leq x \leq y \leq \min(i+s,n)$$$, и поменяйте местами числа $$$x$$$ и $$$y$$$ в перестановке $$$a$$$. Обратите внимание, что вы можете выбрать $$$x=y$$$, в таком случае обмена не произойдет.

Вы хотите превратить $$$a$$$ в другую перестановку $$$b$$$ после $$$n$$$ операций. Однако некоторые элементы $$$b$$$ отсутствуют и заменены на $$$-1$$$. Вычислите количество способов заменить каждую $$$-1$$$ в $$$b$$$ на некоторое целое число от $$$1$$$ до $$$n$$$ так, чтобы $$$b$$$ была перестановкой, и можно было превратить $$$a$$$ в $$$b$$$ силой $$$s$$$.

Так как ответ может быть большим, выведите его по модулю $$$998\,244\,353$$$.

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

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$s$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq s \leq n$$$) — размер перестановки и ваша сила, соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы $$$a$$$. Все элементы $$$a$$$ различны.

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$ или $$$b_i = -1$$$) — элементы $$$b$$$. Все элементы $$$b$$$, не равные $$$-1$$$, различны.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
6
3 1
2 1 3
3 -1 -1
3 2
2 1 3
3 -1 -1
4 1
1 4 3 2
4 3 1 2
6 4
4 2 6 3 1 5
6 1 5 -1 3 -1
7 4
1 3 6 2 7 4 5
2 5 -1 -1 -1 4 -1
14 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
Выходные данные
1
2
0
2
12
331032489
Примечание

В первом примере $$$a=[2,1,3]$$$. Существуют два способа заменить $$$-1$$$, чтобы $$$b$$$ стала перестановкой: $$$[3,1,2]$$$ и $$$[3,2,1]$$$. Перестановку $$$a$$$ можно превратить в $$$[3,1,2]$$$ силой $$$1$$$ следующим образом: $$$$$$[2,1,3] \xrightarrow[x=1,\,y=1]{} [2,1,3] \xrightarrow[x=2,\,y=3]{} [3,1,2] \xrightarrow[x=3,\,y=3]{} [3,1,2].$$$$$$ Можно показать, что невозможно превратить $$$[2,1,3]$$$ в $$$[3,2,1]$$$ силой $$$1$$$. Поэтому только одна перестановка $$$b$$$ подходит, поэтому ответ $$$1$$$.

Во втором примере $$$a$$$ и $$$b$$$ такие же, как в предыдущем примере, но теперь у нас сила $$$2$$$. Перестановку $$$a$$$ можно превратить в $$$[3,2,1]$$$ силой $$$2$$$ следующим образом: $$$$$$[2,1,3] \xrightarrow[x=1,\,y=3]{} [2,3,1] \xrightarrow[x=2,\,y=3]{} [3,2,1] \xrightarrow[x=3,\,y=3]{} [3,2,1].$$$$$$ Можно также превратить $$$a$$$ в $$$[3,1,2]$$$ используя силу $$$1$$$ как раньше, поэтому ответ $$$2$$$.

В третьем примере есть только одна перестановка $$$b$$$. Можно показать, что невозможно превратить $$$a$$$ в $$$b$$$, поэтому ответ $$$0$$$.