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

Есеп B. Бірегей есеп

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

1 second

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

512 megabytes

Аңыз адам <> Арлан өз жанкүйерлеріне келесі есепті ұсынды: Сізге мөлшері $n$ және $m$ болатын бүтін сандардан тұратын $a$ және $b$ массивтері берілген. $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 )