Сколькими способами можно расставить на квадратной доске размера 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
