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

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

Ограничение по времени Ограничение по памяти
1 секунда 512 мегабайт

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

Вам даны два массива целых чисел aa и bb размера nn и mm, соответственно. Все элементы массива bb попарно различны.

Вам нужно найти количество способов разделить массив aa на mm отрезков (l1l_1, r1r_1), \ldots, (lml_m, rmr_m) так, чтобы выполнялись следующие условия:

  • Каждый элемент массива aa принадлежит ровно одному отрезку.
  • Для каждого 11 \le ii \le mm, число bib_i встречается ровно один раз среди чисел (alia_{l_i}, \ldots, aria_{r_i}) (отрезки нумеруются по возрастанию левой границы).

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

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

Первая строка содержит из два целых числа — nn и mm (11 \le nn, mm \le 55 \cdot 10510^5).

Вторая строка содержит nn целых чисел a1a_1, a2a_2, \ldots, ana_n (11 \le aia_i \le 55 \cdot 10510^5) — массив aa.

Третья строка содержит mm целых чисел b1b_1, b2b_2, \ldots, bmb_m (11 \le bib_i \le 55 \cdot 10510^5) — массив bb.

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

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

Примеры

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

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