Вам даны два массива $$$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$$$:
Вам нужно посчитать количество хороших разбиений массива $$$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
Название |
---|