| Codeforces Round 589 (Div. 2) |
|---|
| Закончено |
Предположим, что есть прямоугольная таблица $$$h \times w$$$, которая состоит из белых и черных ячеек. Определим следующее:
- $$$r_{i}$$$ — Количество подряд идущих черных ячеек, с которых начинается $$$i$$$-я строка при просмотре слева направо ($$$1 \le i \le h$$$). В частности, $$$r_i=0$$$, если крайняя левая ячейка $$$i$$$-й строки является белой.
- $$$c_{j}$$$ — Количество подряд идущих черных ячеек, с которых начинается $$$j$$$-й столбец при просмотре сверху вниз ($$$1 \le j \le w$$$). В частности, $$$c_j=0$$$, если самая верхняя ячейка $$$j$$$-го столбца является белой.
Иными словами, если $$$i$$$-я строка начинается ровно с $$$r_i$$$ черных ячеек. Аналогично, $$$j$$$-й столбец начинается ровно с $$$c_j$$$ черных ячеек.
Пример значений $$$r$$$ и $$$c$$$ таблицы $$$3 \times 4$$$. Даны $$$r$$$ и $$$c$$$. Изначально все ячейки белые. Найдите количество способов заполнить ячейки так, чтобы в заданной таблице значения $$$r$$$ и $$$c$$$ были равны заданным. Поскольку ответ может быть очень большим, найдите по модулю $$$1000000007\,(10^{9} + 7)$$$. Другими словами, найдите остаток от деления ответа на число $$$1000000007\,(10^{9} + 7)$$$.
Первая строка содержит два целых числа $$$h$$$ и $$$w$$$ ($$$1 \le h, w \le 10^{3}$$$) — количество строк и столбцов таблицы.
Вторая строка содержит $$$h$$$ целых чисел $$$r_{1}, r_{2}, \ldots, r_{h}$$$ ($$$0 \le r_{i} \le w$$$) — значения $$$r$$$.
Третья строка содержит $$$w$$$ целых чисел $$$c_{1}, c_{2}, \ldots, c_{w}$$$ ($$$0 \le c_{j} \le h$$$) — значения $$$c$$$.
Выведите ответ по модулю $$$1000000007\,(10^{9} + 7)$$$.
3 4 0 3 1 0 2 3 0
2
1 1 0 1
0
19 16 16 16 16 16 15 15 0 5 0 4 9 9 1 4 4 0 8 16 12 6 12 19 15 8 6 19 19 14 6 9 16 10 11 15 4
797922655
В первом примере есть другой возможный ответ.
Во втором примере нет таких сеток, у которых $$$r$$$ и $$$c$$$ такие же.
В третьем примере убедитесь вывести ответ по модулю $$$(10^9 + 7)$$$.
