Оборона підземелля
Limits: 2 sec., 512 MiB
У підземеллі Нью-Йорка Сплінтер дав завдання черепашкам-ніндзя облаштувати захисну стіну.
Стіна має форму прямокутника висотою \(h\) та шириною \(w\). Стіну поділено на \(w\) стовпців одиничної ширини та \(h\) рядків одиничної висоти.
Черепашки повинні побудувати на цій стіні захисну лінію. Захисна лінія — це ламана, що задовольняє такі умови.
Захисна лінія починається в лівому нижньому куті стіни.
Захисна лінія закінчується в правому верхньому куті стіни.
Захисна лінія складається з \(w + h\) відрізків одиничної довжини, кожен з яких іде праворуч або догори.
Донателло також висунув додаткові умови до захисної лінії.
У рядку з номером \(i\) вертикальний відрізок знаходиться на відстані \(a_i\) від лівого краю стіни.
У стовпці з номером \(j\) горизонтальний відрізок знаходиться на відстані \(b_j\) над нижнім краєм стіни.
Захисна лінія у прикладі. Значення \(a_i\) зліва та \(b_j\) знизу.
Донателло все уважно обдумав, тому існує захисна лінія, яка задовольняє його умови.
Донателло доручив Мікеланджело записати всі \(h + w\) чисел у блокнот, але Мікеланджело випадково переплутав їхній порядок. Тепер у блокноті записаний набір чисел \(d_i\) та невідомо, які з них, за що відповідають.
На щастя, Мікеланджело переплутав лише порядок чисел, але самі значення записав без змін.
Допоможіть черепашкам та знайдіть, скільки існує способів побудувати захисну лінію, яка могла бути запланована черепашками спочатку. Оскільки відповідь може бути дуже великою, виведіть остачу від її ділення на просте число \(998244353\).
Input
У першому рядку задано два цілих числа \(h\) та \(w\) — висоту та ширину стіни.
У другому рядку задано \(h + w\) цілих чисел \(d_i\), які Мікеланджело записав у блокнот у довільному порядку.
Output
Виведіть ціле число — остачу від ділення кількості способів побудувати захисну лінію на просте число \(998244353\).
Constraints
\(1 \le w, h \le 10^5\),
\(0 \le d_i \le \max(w, h)\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 5 0 1 1 1 3 2 4 4 4 | 4 |
Notes
В умові зображено один із 4-ох можливих стособів побудувати захисну лінію. Тут зображені інші 3 способи:
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|