Codeforces Round 313 (Div. 1) |
---|
Закончено |
На Геральдионе очень распространены гигантские шахматы. Не будем углубляться в правила этой игры, скажем лишь, что игра происходит на поле размера 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
Название |
---|