B. Восстановление операций
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть перестановка $$$a_1, a_2, \ldots, a_n$$$ и изначально пустая последовательность $$$b$$$. К ней $$$k$$$ раз применяется следующая операция.

На $$$i$$$-м шаге выбирается индекс $$$t_i$$$ ($$$1 \le t_i \le n-i+1$$$), число $$$a_{t_i}$$$ удаляется из массива, а одно из чисел $$$a_{t_i-1}$$$ или $$$a_{t_i+1}$$$ (если они определены, т. е. $$$t_i-1$$$ или $$$t_i+1$$$ не выходят за границы массива) записывается в конец последовательности $$$b$$$. После удаления из массива элементы $$$a_{t_i+1}, \ldots, a_n$$$ сдвигаются влево, занимая освободившееся место.

Вам даны перестановка $$$a_1, a_2, \ldots, a_n$$$ и последовательность $$$b_1, b_2, \ldots, b_k$$$. Так получилось, что все элементы массива $$$b$$$ различны. Посчитайте количество возможных последовательностей индексов $$$t_1, t_2, \ldots, t_k$$$ по модулю $$$998\,244\,353$$$.

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

Каждый тест содержит несколько наборов входных данных. В первой строке содержится целое число $$$t$$$ ($$$1 \le t \le 100\,000$$$) — количество наборов входных данных в тесте.

Первая строка каждого набора входных данных содержит два целых числа $$$n, k$$$ ($$$1 \le k < n \le 200\,000$$$) — длины массивов $$$a$$$ и $$$b$$$.

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

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

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превысит $$$200\,000$$$.

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

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

Пример
Входные данные
3
5 3
1 2 3 4 5
3 2 5
4 3
4 3 2 1
4 3 1
7 4
1 4 7 3 6 2 5
3 2 4 5
Выходные данные
2
0
4
Примечание

$$$\require{cancel}$$$

Будем обозначать записью $$$a_1 a_2 \ldots \cancel{a_i} \underline{a_{i+1}} \ldots a_n \rightarrow a_1 a_2 \ldots a_{i-1} a_{i+1} \ldots a_{n-1}$$$ операцию над индексом $$$i$$$: удаление элемента $$$a_i$$$ из массива $$$a$$$ и запись элемента $$$a_{i+1}$$$ в последовательность $$$b$$$.

В первом тестовом примере есть два способа получить данную последовательность $$$b$$$:

  • $$$1 2 \underline{3} \cancel{4} 5 \rightarrow 1 \underline{2} \cancel{3} 5 \rightarrow 1 \cancel{2} \underline{5} \rightarrow 1 2$$$; $$$(t_1, t_2, t_3) = (4, 3, 2)$$$;
  • $$$1 2 \underline{3} \cancel{4} 5 \rightarrow \cancel{1} \underline{2} 3 5 \rightarrow 2 \cancel{3} \underline{5} \rightarrow 1 5$$$; $$$(t_1, t_2, t_3) = (4, 1, 2)$$$.

Во втором тестовом примере нет ни одной подходящей последовательности — поскольку первым действием было удалено число, соседнее с $$$4$$$, а именно число $$$3$$$, которое из-за этого не могло быть добавлено в массив $$$b$$$ на втором шаге.

В третьем тестовом примере есть четыре способа получить данную последовательность $$$b$$$:

  • $$$1 4 \cancel{7} \underline{3} 6 2 5 \rightarrow 1 4 3 \cancel{6} \underline{2} 5 \rightarrow \cancel{1} \underline{4} 3 2 5 \rightarrow 4 3 \cancel{2} \underline{5} \rightarrow 4 3 5$$$;
  • $$$1 4 \cancel{7} \underline{3} 6 2 5 \rightarrow 1 4 3 \cancel{6} \underline{2} 5 \rightarrow 1 \underline{4} \cancel{3} 2 5 \rightarrow 1 4 \cancel{2} \underline{5} \rightarrow 1 4 5$$$;
  • $$$1 4 7 \underline{3} \cancel{6} 2 5 \rightarrow 1 4 7 \cancel{3} \underline{2} 5 \rightarrow \cancel{1} \underline{4} 7 2 5 \rightarrow 4 7 \cancel{2} \underline{5} \rightarrow 4 7 5$$$;
  • $$$1 4 7 \underline{3} \cancel{6} 2 5 \rightarrow 1 4 7 \cancel{3} \underline{2} 5 \rightarrow 1 \underline{4} \cancel{7} 2 5 \rightarrow 1 4 \cancel{2} \underline{5} \rightarrow 1 4 5$$$;