Областная олимпиада по информатике 2022 года за 11 класс | Казахстанские олимпиады

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

Легендарный «LeGross» Арлан дал следующую задачу своим фанатам:

Вам даны два массива целых чисел $a$ и $b$ размера $n$ и $m$, соответственно. Все элементы массива $b$ попарно различны.

Вам нужно найти количество способов разделить массив $a$ на $m$ отрезков ($l_1$, $r_1$), $\ldots$, ($l_m$, $r_m$) так, чтобы выполнялись следующие условия:

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

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

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

Первая строка содержит из два целых числа — $n$ и $m$ ($1$ $\le$ $n$, $m$ $\le$ $5$ $\cdot$ $10^5$).

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

Третья строка содержит $m$ целых чисел $b_1$, $b_2$, $\ldots$, $b_m$ ($1$ $\le$ $b_i$ $\le$ $5$ $\cdot$ $10^5$) — массив $b$.

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

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

Примеры

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

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