G. Ладьи
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сколькими способами можно расставить на квадратной доске размера N клеток K ладей, чтобы они не били друг друга?

На доске имеется несколько запрещённых клеток, в которые ставить фигуры нельзя.

Все ладьи одинаковые. Ни фигуры, ни клетки не имеют цвета.

Считается, что ладья бьёт другую ладью, если они обе находятся в одной строке или в одном столбце доски.

Посчитайте количество способов и выведите его остаток от деления на число 109 + 7.

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

Первая строка содержит два целых числа N и K — размеры доски и количество ладей (1 ≤ N ≤ 109; 1 ≤ K ≤ 107).

Вторая строка содержит целое число M — количество запрещённых клеток (0 ≤ M ≤ 40).

В следующих M строках содержатся координаты клеток в виде пар чисел xi, yi (1 ≤ xi, yi ≤ N).

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

Выведите единственное число — ответ на задачу.

Примеры
Входные данные
3 2
3
1 1
2 1
3 2
Выходные данные
8
Входные данные
2 2
2
1 1
1 2
Выходные данные
0
Входные данные
5 1
0
Выходные данные
25