Задача №115419. Туристический маршрут
Школьники приехали на экскурсию в новый город и решили осмотреть его достопримечательности. Представим город в виде прямоугольной сетки \(n \times m\), в некоторых клетках которой могут находиться достопримечательности.
Друзья начинают свой путь в клетке \((1, 1)\), они хотят дойти до клетки \((n,m)\), а затем вернуться обратно. В городе есть \(k\) достопримечательностей, они расположены в клетках \((x_1, y_1), \ldots, (x_k, y_k)\), друзья обязательно хотят посетить их все.
За одну минуту можно перейти из клетки \((a, b)\) в клетку \((c, d)\), если они являются соседними по стороне, то есть выполняется равенство \(|a - c| + |b - d| = 1\). Легко видеть, что на маршрут необходимо потратить хотя бы \(2n+2m-4\) минут, будем рассматривать только такие маршруты.
Будем называть маршрут интересным , если выполняются следующие условия:
- для того, чтобы пройти маршрут, друзья потратят ровно \(2n+2m-4\) минут;
- маршрут проходит через каждую клетку не более одного раза.
- маршрут проходит через все клетки, которые содержат достопримечательности.
Помогите школьникам понять, сколько существует различных интересных маршрутов. Так как это число может оказаться достаточно большим, то выведите его остаток при делении на \(10^9+7\).
В первой строке указаны числа \(n\), \(m\) и \(k\) (\(3 \le n,m \le 10^6\), \(0 \le k \le 2\,000\)).
В последующих \(k\) строках указано по паре чисел \(x_i\), \(y_i\) (\(1 \le x_i \le n\), \(1 \le y_i \le m\)), гарантируется, что все пары \((x_i, y_i)\) различны. То есть для любой пары индексов \((i, j)\) (\(1 \le i < j \le k\)) верно хотя бы одно из двух: \(x_i \neq x_j\) или \(y_i \neq y_j\).
Выведите единственное число — остаток от деления числа интересных маршрутов на \(10^9+7\).
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 5 | \(n=3\); \(m, k \le 100\) | первая ошибка | |
| 2 | 9 | \(n, m, k \leq 5\) | первая ошибка | |
| 3 | 6 | \(n, m, k \leq 8\) | 2 | первая ошибка |
| 4 | 17 | \(n, m, k \leq 30\) | 2, 3 | первая ошибка |
| 5 | 16 | \(n, m, k \leq 100\) | 1–4 | первая ошибка |
| 6 | 8 | \(k=0\) | первая ошибка | |
| 7 | 11 | \(k=1\) | первая ошибка | |
| 8 | 12 | \(k \leq 16\) | 2, 3, 6, 7 | первая ошибка |
| 9 | 9 | \(k \leq 100\) | 1–8 | первая ошибка |
| 10 | 7 | нет | 1–9 | первая ошибка |
Ниже изображены все интересные маршруты для первого теста.
Клетки с достопримечательностями обозначены звездочкой.
3 4 2 2 2 2 3
6
3 4 3 3 1 2 3 1 4
0