Оборона підземелля#12994

Оборона підземелля

У підземеллі Нью-Йорка Сплінтер дав завдання черепашкам-ніндзя облаштувати захисну стіну.

Стіна має форму прямокутника висотою та шириною . Стіну поділено на стовпців одиничної ширини та рядків одиничної висоти.

Черепашки повинні побудувати на цій стіні захисну лінію. Захисна лінія — це ламана, що задовольняє такі умови.

Донателло також висунув додаткові умови до захисної лінії.

Захисна лінія у прикладі. Значення a_i зліва та b_j знизу.

Донателло все уважно обдумав, тому існує захисна лінія, яка задовольняє його умови.

Донателло доручив Мікеланджело записати всі h + w чисел у блокнот, але Мікеланджело випадково переплутав їхній порядок. Тепер у блокноті записаний набір чисел d_i та невідомо, які з них, за що відповідають.

На щастя, Мікеланджело переплутав лише порядок чисел, але самі значення записав без змін.

Допоможіть черепашкам та знайдіть, скільки існує способів побудувати захисну лінію, яка могла бути запланована черепашками спочатку. Оскільки відповідь може бути дуже великою, виведіть остачу від її ділення на просте число .

Вхідні дані

У першому рядку задано два цілих числа та — висоту та ширину стіни.

У другому рядку задано h + w цілих чисел d_i, які Мікеланджело записав у блокнот у довільному порядку.

1 \le w, h \le 10^5,

0 \le d_i \le \max(w, h).

Вихідні дані

Виведіть ціле число — остачу від ділення кількості способів побудувати захисну лінію на просте число .

Приклади

Приклад

Loading
Loading

Примітка

В умові зображено один із 4-ох можливих стособів побудувати захисну лінію. Тут зображені інші 3 способи: