Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Кухонный стол накрыли клетчатой скатертью, и на его поверхности получился прямоугольник размером N × M клеток. Пронумеруем эти клетки сначала по вертикали от 1 до N сверху вниз, затем по горизонтали от 1 до M слева направо.
В клетку (1; 1) залез таракан, и он очень хочет добежать до клетки (N; M). Таракан умеет бегать только вправо или вниз. Его задача осложняется тем, что в некоторых клетках лежат столовые приборы, и перебегать по таким клеткам таракан не сможет.
Определите, сколько у таракана есть различных способов добраться из левой верхней клетки стола в правую нижнюю.
Входные данные
Первая строка содержит целые числа N и M (1 <= N, M <= 1000) — длину и ширину стола соответственно.
Вторая строка содержит целое число K (0 <= K <= N × M) — количество клеток, занятых столовыми приборами.
Следующие K строк содержат пары целых чисел Yi, Xi (1 <= Yi <= N, 1 <= Xi <= M) — координаты занятых клеток.
Выходные данные
Выведите единственное целое число — количество способов добраться из клетки (1; 1) в клетку (N; M). Ответ может оказаться очень большим, поэтому выведите остаток от его деления на 1000000007.
Примеры
| Входные данные | Выходные данные |
2 3
0 | 3 |
3 3
1
2 2 | 2 |
Для отправки решений необходимо выполнить вход.
|