C. Геральд и гигантские шахматы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На Геральдионе очень распространены гигантские шахматы. Не будем углубляться в правила этой игры, скажем лишь, что игра происходит на поле размера h × w, и оно тоже раскрашено в два цвета, но не как в шахматах. Почти все клетки поля белые и только некоторые — чёрные. В данный момент Геральд заканчивает партию в гигантские шахматы против своего друга Полларда. Геральд почти выиграл, и для победы ему осталось только провести свою пешку из верхнего левого угла доски, где она сейчас стоит, в нижний правый. Геральд настолько уверен в победе, что ему стало интересно, сколькими способами он может выиграть?

Пешка, которая осталась у Геральда, может ходить двумя способами: на одну клетку вниз или на одну клетку вправо. Кроме того, она не может ходить на чёрные клетки, иначе Геральд всё-таки проиграет. Никаких других пешек или фигур на поле не осталось, так что, согласно правилам гигантских шахмат, Геральд ходит своей пешкой, пока игра не закончится, а Поллард просто наблюдает за этим процессом.

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

В первой строке входных данных заданы три числа: h, w, n — размеры доски и количество чёрных клеток (1 ≤ h, w ≤ 105, 1 ≤ n ≤ 2000).

В следующих n строках задано описание чёрных клеток. В i-й из этих строк написаны числа ri, ci (1 ≤ ri ≤ h, 1 ≤ ci ≤ w) — номер строки и столбца i-й клетки.

Гарантируется, что верхняя левая и нижняя правая клетка белые и все клетки в описании различны.

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

Выведите единственное число — остаток от деления количества способов провести пешку Геральда от верхней левой клетки до нижней правой на число 109 + 7.

Примеры
Входные данные
3 4 2
2 2
2 3
Выходные данные
2
Входные данные
100 100 3
15 16
16 15
99 88
Выходные данные
545732279