29157번 - 폭탄 피하기

무한한 크기의 2차원 격자판이 있다. 성모는 좌측 상단의 점 $(0, 0)$에 있고, 우측 하단의 $(N, M)$에 있는 찬민이를 만나러 가려고 한다. 격자판 위에는 $K$개의 폭탄들이 격자점에 있기 때문에, 성모는 폭탄들을 피해서 이동해야 한다. 성모는 오른쪽, 또는 아래로만 이동할 수 있을 때, 성모가 폭탄을 피해서 찬민이가 있는 곳까지 도착할 수 있는 이동할 수 있는 경우의 수를 구하여라.

첫 번째 줄에 정수 $N, M, K$가 공백으로 구분되어 주어진다. $(1\leq N, M\leq 1\,000\,000;$ $0\leq K\leq 20)$

두 번째 줄부터 $K$개의 줄에 걸쳐 각 줄에 폭탄의 위치 $(X_{i}, Y_{i})$를 나타내는 $X_i, Y_i$가 공백으로 구분되어 주어진다. $(1\leq i\leq K;$ $0\leq X_{i}\leq N;$ $0\leq Y_{i}\leq M)$

폭탄의 위치는 시작점과 도착점을 제외한 정수 좌표에 있으며, 모두 다르다.

성모가 이동할 수 있는 경우의 수를 출력하라. 답이 커질 수 있으므로 $1\,000\,000\,007 (=10^{9} + 7)$로 나눈 나머지를 출력한다. 단, $1\,000\,000\,007$은 소수이다.