E. Выдача багажа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Каждый аэропорт имеет зону выдачи багажа, не исключение и аэропорт Балбесово. В какой-то момент одному из администраторов Шереметьево пришла в голову необычная идея: изменить привычную форму ленты выдачи багажа с карусели на более сложную форму.

Предположим, что зал выдачи багажа представлен как прямоугольная сетка размера $$$n \times m$$$. Администрация предложила, чтобы путь ленты проходил через ячейки $$$p_1, p_2, \ldots, p_{2k+1}$$$, где $$$p_i = (x_i, y_i)$$$.

Для каждой ячейки $$$p_i$$$ и следующей за ней ячейки $$$p_{i+1}$$$ (где $$$1 \leq i \leq 2k$$$) данные ячейки должны иметь общую сторону. Кроме того, путь должен быть простым, то есть ни для какой пары индексов $$$i \neq j$$$ клетки $$$p_i$$$ и $$$p_j$$$ не должны совпадать.

К сожалению, план маршрута был случайно испорчен пролитым кофе, и удалось сохранить только ячейки с нечётными индексами пути: $$$p_1, p_3, p_5, \ldots, p_{2k+1}$$$. Ваша задача — по заданным этим $$$k+1$$$ ячейкам определить количество способов восстановить исходный полный путь $$$p_1, p_2, \ldots, p_{2k+1}$$$.

Так как ответ может быть очень большим, выведите его по модулю $$$10^9+7$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n, m \le 1000$$$, $$$n \cdot m \ge 3$$$, $$$1 \le k \le \left\lfloor \frac12 (n m - 1) \right\rfloor$$$) — размеры сетки и параметр, задающий длину пути.

Далее следует $$$k+1$$$ строка, $$$i$$$-я из них содержит два целых числа $$$x_{2i-1}$$$ и $$$y_{2i-1}$$$ ($$$1 \le x_{2i-1} \le n$$$, $$$1 \le y_{2i-1} \le m$$$) — координаты ячейки $$$p_{2i-1}$$$, лежащей на пути.

Гарантируется, что все пары $$$(x_{2i-1}, y_{2i-1})$$$ различны.

Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превышает $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите единственное целое число — количество способов восстановить исходный полный путь по модулю $$$10^9+7$$$.

Пример
Входные данные
5
2 4 2
1 1
2 2
2 4
1 4 1
1 1
1 4
5 5 11
2 5
3 4
4 5
5 4
4 3
5 2
4 1
3 2
2 1
1 2
2 3
1 4
3 4 4
1 2
2 1
3 2
2 3
3 4
3 3 2
2 2
1 1
1 3
Выходные данные
2
0
2
5
1
Примечание

В первом наборе входных данных есть два возможных пути:

  • $$$(1,1) \to (2,1) \to (2, 2) \to (2, 3) \to (2, 4)$$$
  • $$$(1,1) \to (1,2) \to (2, 2) \to (2, 3) \to (2, 4)$$$

Во втором наборе входных данных не существует подходящего пути, так как у клеток $$$(1,1)$$$ и $$$(1,4)$$$ нет общей соседней клетки.