3-й этап Республиканской олимпиады по информатике 2021-2022, 2 тура

Задача B. Уникальная задача

Ограничение по времени:

1 секунда

Ограничение по памяти:

512 мегабайт

Легендарный <> Арлан дал следующую задачу своим фанатам: Вам даны два массива целых чисел $a$ и $b$ размера $n$ и $m$, соответственно. Все элементы массива $b$ попарно различны. Вам нужно найти количество способов разделить массив $a$ на $m$ отрезков $(l_1, r_1), \ldots, (l_m, r_m)$ так, чтобы выполнялись следующие условия:

• Каждый элемент массива $a$ принадлежит ровно одному отрезку.
• Для каждого $1 <= i <= m$, число $b_i$ встречается ровно один раз среди чисел $(a_{l_i}, \ldots, a_{r_i})$ (отрезки нумеруются по возрастанию левой границы).

Так как ответ может быть слишком большим, выведите его остаток при делении на $998244353$.

Формат входного файла

Первая строка содержит из два целых числа — $n$ и $m$ ($1 <= n, m <= 5 \cdot 10^5$). Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ $(1 <= a_i <= 5 \cdot 10^5)$ — массив $a$. Третья строка содержит $m$ целых чисел $b_1, b_2, \ldots, b_m$ $(1 <= b_i <= 5 \cdot 10^5)$ — массив $b$.

Формат выходного файла

Выведите одно целое число — ответ на задачу Арлана по модулю $998244353$.

Примеры:

Вход

4 2
1 7 7 3
7 3

Ответ

1

Вход

2 1
1 1
1

Ответ

0

Замечание

В первом примере можно разделить массив на отрезки $(1, 2)$ и $(3, 4)$. ( Dimash Tursynbai )