Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

Вам даны два массива $$$a_1, a_2, \dots , a_n$$$ и $$$b_1, b_2, \dots , b_m$$$. Массив $$$b$$$ отсортирован в порядке возрастания ($$$b_i < b_{i + 1}$$$ верно для любого $$$i$$$ от $$$1$$$ до $$$m - 1$$$).

Вам нужно разбить массив $$$a$$$ на $$$m$$$ непрерывных подмассивов так, чтобы для всех $$$i$$$ от $$$1$$$ до $$$m$$$ минимум в $$$i$$$-м подмассиве был равен $$$b_i$$$. Обратите внимание, что каждый элемент должен принадлежать ровно одному подмассиву, и они формируются следующим образом: первые несколько элементов массива $$$a$$$ принадлежат первому подмассиву, следующие несколько элементов массива $$$a$$$ принадлежат второму подмассиву, и так далее.

Например, если $$$a = [12, 10, 20, 20, 25, 30]$$$, а $$$b = [10, 20, 30]$$$, то существует два подходящих разбиения массива $$$a$$$:

  1. $$$[12, 10, 20], [20, 25], [30]$$$;
  2. $$$[12, 10], [20, 20, 25], [30]$$$.

Вам нужно посчитать количество хороших разбиений массива $$$a$$$. Так как это значение может быть слишком велико — выведите его по модулю 998244353.

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

Первая строка содержит два числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — длины массивов $$$a$$$ и $$$b$$$ соответственно.

Вторая строка содержит $$$n$$$ чисел $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le 10^9$$$) — массив $$$a$$$.

Третья строка содержит $$$m$$$ чисел $$$b_1, b_2, \dots , b_m$$$ ($$$1 \le b_i \le 10^9; b_i < b_{i+1}$$$) — массив $$$b$$$.

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

В единственной строке выведите число — количество хороших разбиений массива $$$a$$$ по модулю 998244353.

Примеры
Входные данные
6 3
12 10 20 20 25 30
10 20 30
Выходные данные
2
Входные данные
4 2
1 3 3 7
3 7
Выходные данные
0
Входные данные
8 2
1 2 2 2 2 2 2 2
1 2
Выходные данные
7