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

Маленький Тайлер зашел на кухню и увидел, что на холодильнике магнитиками выложена строка $$$s$$$. Он сразу увидел её безграничный потенциал!

Тайлеру нравятся строки, особенно те, которые лексикографически меньше другой строки $$$t$$$. Играя с магнитиками на холодильнике, он задумался, а сколько различных строк, лексикографически меньших строки $$$t$$$, он может собрать, переставляя буквы в строке $$$s$$$. Так как он учится всего лишь во втором классе, он не может этого посчитать, поэтому просит вас о помощи! Так как в алфавите языка Тайлера много букв, то для вашего удобства Тайлер уже заменил одинаковые буквы в строках $$$s$$$ и $$$t$$$ одинаковыми числами, а разные — разными.

Напомним, что строка $$$x$$$ лексикографически меньше строки $$$y$$$, если выполнено одно из двух условий:

  • существует такая позиция символа $$$m$$$, присутствующая в обеих строках, что до $$$m$$$-го символа строки совпадают, а $$$m$$$-й символ строки $$$x$$$ меньше $$$m$$$-го символа $$$y$$$,
  • строка $$$x$$$ является префиксом $$$y$$$ и $$$x \neq y$$$.

Так как ответ может быть слишком большим, выведите его по модулю $$$998\,244\,353$$$.

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

В первой строке даны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 200\,000$$$) — длины строк $$$s$$$ и $$$t$$$ соответственно.

Во второй строке даны $$$n$$$ целых чисел $$$s_1, s_2, s_3, \ldots, s_n$$$ ($$$1 \le s_i \le 200\,000$$$) — буквы строки $$$s$$$.

Во третьей строке даны $$$m$$$ целых чисел $$$t_1, t_2, t_3, \ldots, t_m$$$ ($$$1 \le t_i \le 200\,000$$$) — буквы строки $$$t$$$.

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

Выведите единственное число — количество строк, лексикографически меньших $$$t$$$, которые можно получить, переставляя буквы в $$$s$$$, по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
3 4
1 2 2
2 1 2 1
Выходные данные
2
Входные данные
4 4
1 2 3 4
4 3 2 1
Выходные данные
23
Входные данные
4 3
1 1 1 2
1 1 2
Выходные данные
1
Примечание

В первом примере интересующие нас строки это $$$[1\, 2\, 2]$$$ и $$$[2\, 1\, 2]$$$. Строка $$$[2\, 2\, 1]$$$ лексикографически больше строки $$$[2\, 1\, 2\, 1]$$$, поэтому её мы не считаем.

Во втором примере подходят все строки, кроме $$$[4\, 3\, 2\, 1]$$$, так что их $$$4! - 1 = 23$$$.

В третьем примере подходит только строка $$$[1\, 1\, 1\, 2]$$$.