Educational DP Contest - Grid 2

There is a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and the j-th column from the left.

In the grid, N Squares (r_1, c_1), (r_2, c_2), \ldots, (r_N, c_N) are wall squares, and the others are all empty squares. It is guaranteed that Squares (1, 1) and (H, W) are empty squares.

Taro will start from Square (1, 1) and reach (H, W) by repeatedly moving right or down to an adjacent empty square.

Find the number of Taro's paths from Square (1, 1) to (H, W), modulo 10^9 + 7.

Constraints

* All values in input are integers.
* 2 \leq H, W \leq 10^5
* 1 \leq N \leq 3000
* 1 \leq r_i \leq H
* 1 \leq c_i \leq W
* Squares (r_i, c_i) are all distinct.
* Squares (1, 1) and (H, W) are empty squares.

Input

Input is given from Standard Input in the following format:


H W N
r_1 c_1
r_2 c_2
:
r_N c_N


Output

Print the number of Taro's paths from Square (1, 1) to (H, W), modulo 10^9 + 7.

Examples

Input

3 4 2
2 2
1 4


Output

3


Input

5 2 2
2 1
4 2


Output

0


Input

5 5 4
3 1
3 5
1 3
5 3


Output

24


Input

100000 100000 1
50000 50000


Output

123445622

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys

def prepare(n):
	fact = [1] * (n + 1)
	for i in range(1, n + 1):
		fact[i] = fact[i - 1] * i % MOD
	inv = [1] * (n + 1)
	inv[n] = pow(fact[n], MOD - 2, MOD)
	for i in range(n - 1, 0, -1):
		inv[i] = inv[i + 1] * (i + 1) % MOD
	return (fact, inv)
MOD = 10 ** 9 + 7
(h, w, n) = map(int, input().split())
walls = [tuple(map(int, line.split())) for line in sys.stdin.readlines()]
walls.append((1, 1))
walls.append((h, w))
walls.sort()
(fact, inv) = prepare(h + w)
dp = [1]
for (i, (cy, cx)) in enumerate(walls[1:], start=1):
	res = 0
	for (j, (py, px)) in enumerate(walls[:i]):
		if cx < px:
			continue
		(dy, dx) = (cy - py, cx - px)
		res -= dp[j] * fact[dy + dx] % MOD * inv[dy] % MOD * inv[dx] % MOD
		res %= MOD
	dp.append(res)
print(-dp[-1] % MOD)


import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
(H, W, N) = map(int, input().split())
B = [tuple(map(int, input().split())) for i in range(N)]
B.append((H, W))
B.sort()
FACT = [1]
INVFACT = [1]
for i in range(1, H + W):
	FACT.append(FACT[-1] * i % mod)
	INVFACT.append(INVFACT[-1] * pow(i, mod - 2, mod) % mod)

def Combi(n, r):
	return FACT[n] * INVFACT[n - r] * INVFACT[r] % mod
DP = [0] * (N + 1)
for i in range(N + 1):
	(h, w) = B[i]
	ANS = Combi(h + w - 2, h - 1)
	for j in range(i):
		if B[j][0] > h or B[j][1] > w:
			continue
		ANS = (ANS - DP[j] * Combi(h + w - B[j][0] - B[j][1], h - B[j][0])) % mod
	DP[i] = ANS
print(DP[-1])


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(h, w, n) = list(map(int, input().split()))
h -= 1
w -= 1
rc = [None] * n
for i in range(n):
	rc[i] = tuple(map(lambda x: int(x) - 1, input().split()))
rc.sort()
M = 10 ** 9 + 7
N = h + w + 10
g1 = [None] * (N + 1)
g2 = [None] * (N + 1)
inverse = [None] * (N + 1)
g1[0] = g1[1] = g2[0] = g2[1] = 1
(inverse[0], inverse[1]) = [0, 1]
for i in range(2, N + 1):
	g1[i] = g1[i - 1] * i % M
	inverse[i] = -inverse[M % i] * (M // i) % M
	g2[i] = g2[i - 1] * inverse[i] % M

def cmb(n, r, M):
	if r < 0 or r > n:
		return 0
	r = min(r, n - r)
	return g1[n] * g2[r] * g2[n - r] % M
dp = [0] * n

def f(x, y):
	return cmb(x + y, x, M)
for i in range(n):
	(r, c) = rc[i]
	val = f(r, c)
	for j in range(i):
		val -= dp[j] * f(r - rc[j][0], c - rc[j][1])
		val %= M
	dp[i] = val
ans = 0
for i in range(n):
	(r, c) = rc[i]
	ans += dp[i] * f(h - r, w - c)
	ans %= M
ans = f(h, w) - ans
ans %= M
print(ans % M)


import sys
input = sys.stdin.readline
(H, W, N) = map(int, input().split())
a = []
mod = 10 ** 9 + 7
for _ in range(N):
	(x, y) = map(int, input().split())
	a.append((x, y))
a.sort(key=lambda x: (x[0], x[1]))

class Factorial:

	def __init__(self, n, mod):
		self.f = [1]
		for i in range(1, n + 1):
			self.f.append(self.f[-1] * i % mod)
		self.i = [pow(self.f[-1], mod - 2, mod)]
		for i in range(1, n + 1)[::-1]:
			self.i.append(self.i[-1] * i % mod)
		self.i.reverse()

	def factorial(self, i):
		return self.f[i]

	def ifactorial(self, i):
		return self.i[i]

	def combi(self, n, k):
		return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
f = Factorial(H + W, mod)
dp = [[0] * 2 for _ in range(N)]
for i in range(N):
	(x, y) = a[i]
	dp[i][1] = f.combi(x + y - 2, x - 1) % mod
for i in range(N):
	(x, y) = a[i]
	for j in range(N):
		if i == j:
			continue
		(u, v) = a[j]
		if u >= x and v >= y:
			t = f.combi(u + v - (x + y), u - x)
			dp[j][0] += t * dp[i][1]
			dp[j][0] %= mod
			dp[j][1] += t * dp[i][0]
			dp[j][1] %= mod
res = f.combi(H + W - 2, H - 1)
for i in range(N):
	(x, y) = a[i]
	res += dp[i][0] * f.combi(H + W - x - y, H - x)
	res %= mod
	res -= dp[i][1] * f.combi(H + W - x - y, H - x)
	res %= mod
print(res)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(h, w, n) = map(int, readline().split())
rc = [(1, 1)]
for i in range(n):
	(r, c) = map(int, readline().split())
	rc.append((r, c))
rc.sort(key=lambda x: sum(x) * -1)
mod = 10 ** 9 + 7
max_n = 3 * 10 ** 5
(fac, finv, inv) = ([0] * max_n, [0] * max_n, [0] * max_n)

def comInit(max_n):
	fac[0] = fac[1] = 1
	finv[0] = finv[1] = 1
	inv[1] = 1
	for i in range(2, max_n):
		fac[i] = fac[i - 1] * i % mod
		inv[i] = mod - inv[mod % i] * (mod // i) % mod
		finv[i] = finv[i - 1] * inv[i] % mod
comInit(max_n)

def com(n, k):
	if n < k:
		return 0
	if (n < 0) | (k < 0):
		return 0
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod
dp = [0] * (n + 2)
dp[0] = 1
for i in range(n + 1):
	(ri, ci) = rc[i]
	dp[i + 1] = com(h + w - ri - ci, h - ri)
	for j in range(i):
		(rj, cj) = rc[j]
		if (ri <= rj) & (ci <= cj):
			dp[i + 1] -= com(rj + cj - ri - ci, rj - ri) * dp[j + 1]
			dp[i + 1] %= mod
print(dp[-1])


mod = 10 ** 9 + 7
frac = [1] * 200001
for i in range(2, 200001):
	frac[i] = i * frac[i - 1] % mod
fraci = [None] * 200001
fraci[-1] = pow(frac[-1], mod - 2, mod)
for i in range(-2, -200001 - 1, -1):
	fraci[i] = fraci[i + 1] * (200001 + i + 1) % mod

def comb(a, b):
	if not a >= b >= 0:
		return 0
	return frac[a] * fraci[b] * fraci[a - b] % mod

def count(a, b):
	((r1, c1), (r2, c2)) = (RC[a], RC[b])
	if c2 < c1:
		return 0
	return comb(r2 - r1 + c2 - c1, r2 - r1)
(H, W, N) = map(int, input().split())
RC = [list(map(int, input().split())) for _ in range(N)] + [[1, 1], [H, W]]
RC.sort()
dp = [0] * (N + 2)
dp[0] += 1
for i in range(1, N + 2):
	res = count(0, i)
	for k in range(1, i):
		res = (res - count(k, i) * dp[k]) % mod
	dp[i] = res
print(dp[-1])


import sys
input = sys.stdin.readline
import math
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache
MOD = 10 ** 9 + 7
INF = float('inf')
AZ = 'abcdefghijklmnopqrstuvwxyz'

def I():
	return int(input().strip())

def S():
	return input().strip()

def IL():
	return list(map(int, input().split()))

def SL():
	return list(map(str, input().split()))

def ILs(n):
	return list((int(input()) for _ in range(n)))

def SLs(n):
	return list((input().strip() for _ in range(n)))

def ILL(n):
	return [list(map(int, input().split())) for _ in range(n)]

def SLL(n):
	return [list(map(str, input().split())) for _ in range(n)]

def DD(arg):
	return defaultdict(arg)

def inv(n):
	return pow(n, MOD - 2, MOD)
kaijo_memo = []

def kaijo(n):
	if len(kaijo_memo) > n:
		return kaijo_memo[n]
	if len(kaijo_memo) == 0:
		kaijo_memo.append(1)
	while len(kaijo_memo) <= n:
		kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
	return kaijo_memo[n]
gyaku_kaijo_memo = []

def gyaku_kaijo(n):
	if len(gyaku_kaijo_memo) > n:
		return gyaku_kaijo_memo[n]
	if len(gyaku_kaijo_memo) == 0:
		gyaku_kaijo_memo.append(1)
	while len(gyaku_kaijo_memo) <= n:
		gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo), MOD - 2, MOD) % MOD)
	return gyaku_kaijo_memo[n]

def nCr(n, r):
	if n == r:
		return 1
	if n < r or r < 0:
		return 0
	ret = 1
	ret = ret * kaijo(n) % MOD
	ret = ret * gyaku_kaijo(r) % MOD
	ret = ret * gyaku_kaijo(n - r) % MOD
	return ret

def factorization(n):
	arr = []
	temp = n
	for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
		if temp % i == 0:
			cnt = 0
			while temp % i == 0:
				cnt += 1
				temp //= i
			arr.append([i, cnt])
	if temp != 1:
		arr.append([temp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr

def make_divisors(n):
	divisors = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n // i)
	return divisors

def make_primes(N):
	max = int(math.sqrt(N))
	seachList = [i for i in range(2, N + 1)]
	primeNum = []
	while seachList[0] <= max:
		primeNum.append(seachList[0])
		tmp = seachList[0]
		seachList = [i for i in seachList if i % tmp != 0]
	primeNum.extend(seachList)
	return primeNum

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	return a * b // gcd(a, b)

def count_bit(n):
	count = 0
	while n:
		n &= n - 1
		count += 1
	return count

def base_10_to_n(X, n):
	if X // n:
		return base_10_to_n(X // n, n) + [X % n]
	return [X % n]

def base_n_to_10(X, n):
	return sum((int(str(X)[-i - 1]) * n ** i for i in range(len(str(X)))))

def base_10_to_n_without_0(X, n):
	X -= 1
	if X // n:
		return base_10_to_n_without_0(X // n, n) + [X % n]
	return [X % n]

def int_log(n, a):
	count = 0
	while n >= a:
		n //= a
		count += 1
	return count
(H, W, N) = IL()
wall = [0]
for i in range(N):
	(r, c) = IL()
	wall.append((r - 1) * W + (c - 1))
wall.sort()
graph = [[] for i in range(N + 1)]
for i in range(N + 1):
	(y, x) = (wall[i] // W, wall[i] % W)
	for j in range(i + 1, N + 1):
		(ny, nx) = (wall[j] // W, wall[j] % W)
		if nx < x or ny < y:
			continue
		graph[j].append(i)
dp = [0 for i in range(N + 1)]
for j in range(1, N + 1):
	(y, x) = (wall[j] // W, wall[j] % W)
	dp[j] = nCr(y + x, y)
	for i in graph[j]:
		(py, px) = (y - wall[i] // W, x - wall[i] % W)
		dp[j] -= nCr(py + px, py) * dp[i]
		dp[j] %= MOD
ans = nCr(H + W - 2, H - 1)
for i in range(1, N + 1):
	(y, x) = (H - 1 - wall[i] // W, W - 1 - wall[i] % W)
	ans -= nCr(y + x, y) * dp[i]
	ans %= MOD
print(ans)


SIZE = 300000
MOD = 10 ** 9 + 7
inv = [0] * (SIZE + 1)
fac = [0] * (SIZE + 1)
finv = [0] * (SIZE + 1)
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2, SIZE + 1):
	inv[i] = MOD - MOD // i * inv[MOD % i] % MOD
	fac[i] = fac[i - 1] * i % MOD
	finv[i] = finv[i - 1] * inv[i] % MOD

def choose(n, r):
	if 0 <= r <= n:
		return fac[n] * finv[r] % MOD * finv[n - r] % MOD
	else:
		return 0
(h, w, n) = [int(i) for i in input().split()]
xy = [[1, 1]] + [[int(i) for i in input().split()] for _ in range(n)]
dp = [0] * (n + 1)
dp[0] = 1
xy.sort(key=lambda x: x[1])
xy.sort(key=lambda x: x[0])
for i in range(1, n + 1):
	(x, y) = xy[i]
	for j in range(i):
		(xj, yj) = xy[j]
		dp[i] -= choose(x - xj + y - yj, y - yj) * dp[j]
		dp[i] %= MOD
ans = 0
for (i, dpi) in enumerate(dp):
	(x, y) = xy[i]
	ans += choose(h - x + w - y, w - y) * dpi
	ans %= MOD
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def MI():
	return map(int, sys.stdin.readline().split())

def MI1():
	return map(int1, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def com(com_n, com_r):
	return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md

def way(h, w):
	if h < 0 or w < 0:
		return 0
	else:
		return com(h + w, h)
md = 10 ** 9 + 7
n_max = 200005
fac = [1]
inv = [1] * (n_max + 1)
k_fac_inv = 1
for i in range(1, n_max + 1):
	k_fac_inv = k_fac_inv * i % md
	fac.append(k_fac_inv)
k_fac_inv = pow(k_fac_inv, md - 2, md)
for i in range(n_max, 1, -1):
	inv[i] = k_fac_inv
	k_fac_inv = k_fac_inv * i % md

def main():
	(h, w, n) = MI()
	rc = [LI1() for _ in range(n)]
	rc.sort(key=lambda x: x[0] + x[1])
	dp = [0] * n
	for (i, (r, c)) in enumerate(rc):
		dp[i] = way(r, c) - sum((v * way(r - pr, c - pc) % md for (v, (pr, pc)) in zip(dp[:i], rc[:i])))
		dp[i] %= md
	(h, w) = (h - 1, w - 1)
	ans = way(h, w) - sum((v * way(h - r, w - c) % md for (v, (r, c)) in zip(dp, rc)))
	print(ans % md)
main()


def f():
	(h, w, n) = map(int, input().split())
	md = 10 ** 9 + 7
	k = [list(map(int, input().split())) for _ in range(n)] + [[h, w]]
	k.sort(key=lambda x: x[0] + x[1])
	fct = [1]
	re_fct = []
	fct_i = 1
	for i in range(1, h + w + 1):
		fct_i = fct_i * i % md
		fct += [fct_i]
	re_i = 1
	p = md - 2
	while p:
		if p & 1:
			re_i = re_i * fct_i % md
		p >>= 1
		fct_i = fct_i ** 2 % md
	for i in range(h + w, -1, -1):
		re_fct += [re_i]
		re_i = re_i * i % md
	re_fct = re_fct[::-1]
	cmb = lambda a, b: fct[a] * re_fct[b] * re_fct[a - b] % md
	dp = [0] * (n + 1)
	for (i, [r, c]) in enumerate(k):
		dpi = cmb(r + c - 2, r - 1) % md
		for j in range(i):
			(dr, dc) = (r - k[j][0], c - k[j][1])
			if dr >= 0 and dc >= 0:
				dpi = (dpi - dp[j] * cmb(dr + dc, dr)) % md
		dp[i] = dpi
	print(dp[-1])
f()


class Combination:

	def __init__(self, n, MOD):
		self.fact = [1] * (n + 1)
		for i in range(1, n + 1):
			self.fact[i] = self.fact[i - 1] * i % MOD
		self.inv_fact = [pow(self.fact[i], MOD - 2, MOD) for i in range(n + 1)]
		self.MOD = MOD

	def factorial(self, k):
		return self.fact[k]

	def inverse_factorial(self, k):
		return self.inv_fact[k]

	def permutation(self, k, r):
		if k < r:
			return 0
		return self.fact[k] * self.inv_fact[r] % self.MOD

	def combination(self, k, r):
		if k < r:
			return 0
		return self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r] % self.MOD
(h, w, n) = map(int, input().split())
info = [(1, 1)] + [tuple(map(int, input().split())) for i in range(n)] + [(h, w)]
info = sorted(info)
n += 2
MOD = 10 ** 9 + 7
comb = Combination(w + h + 1, MOD)
dp = {}
dp[0] = (0, 1)

def solve(ind):
	if ind in dp:
		return dp[ind]
	(i, j) = info[ind]
	dp0 = 0
	dp1 = 0
	for ind2 in range(n):
		if ind2 == ind:
			continue
		(pi, pj) = info[ind2]
		if pi <= i and pj <= j:
			tmp = comb.combination(i + j - (pi + pj), i - pi)
			dp0 += tmp * solve(ind2)[1] % MOD
			dp1 += tmp * solve(ind2)[0] % MOD
	dp[ind] = (dp0, dp1)
	return dp[ind]
for i in range(n):
	solve(i)
print((dp[n - 1][0] - dp[n - 1][1]) % MOD)


class Combination:

	def __init__(self, n_max, mod=10 ** 9 + 7):
		self.mod = mod
		f = 1
		self.fac = fac = [f]
		for i in range(1, n_max + 1):
			f = f * i % mod
			fac.append(f)
		f = pow(f, mod - 2, mod)
		self.facinv = facinv = [f]
		for i in range(n_max, 0, -1):
			f = f * i % mod
			facinv.append(f)
		facinv.reverse()

	def __call__(self, n, r):
		return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

	def nCr(self, n, r):
		if not 0 <= r <= n:
			return 0
		return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

def resolve():
	MOD = 10 ** 9 + 7
	(H, W, N) = map(int, input().split())
	wall = []
	for _ in range(N):
		(r, c) = map(lambda x: int(x) - 1, input().split())
		wall.append((r, c))
	wall.append((H - 1, W - 1))
	wall.sort()
	cmb = Combination(H + W + 1)
	dp = [0] * (N + 1)
	for i in range(N + 1):
		(r1, c1) = wall[i]
		dp[i] = cmb.nCr(r1 + c1, c1)
		for j in range(0, i):
			dx = r1 - wall[j][0]
			dy = c1 - wall[j][1]
			tmp = dp[j] * cmb.nCr(dx + dy, dy)
			dp[i] = (dp[i] - tmp % MOD + MOD) % MOD
	print(dp[N])
resolve()


from collections import deque
import sys
input = sys.stdin.readline

def solve():
	MOD = 10 ** 9 + 7
	(H, W, N) = map(int, input().split())
	rcs = [tuple(map(int, input().split())) for _ in range(N)]
	adjL = [[] for _ in range(N)]
	for i in range(N):
		(r1, c1) = rcs[i]
		for j in range(i + 1, N):
			(r2, c2) = rcs[j]
			if r1 <= r2 and c1 <= c2:
				adjL[i].append(j)
			if r1 >= r2 and c1 >= c2:
				adjL[j].append(i)

	def TopologicalSort(adjList):
		numV = len(adjList)
		indegs = [0] * numV
		for v in range(numV):
			for v2 in adjList[v]:
				indegs[v2] += 1
		anss = [v for v in range(numV) if indegs[v] == 0]
		Q = deque(anss)
		while Q:
			vNow = Q.popleft()
			for v2 in adjList[vNow]:
				indegs[v2] -= 1
				if indegs[v2] == 0:
					anss.append(v2)
					Q.append(v2)
		return anss
	nos = TopologicalSort(adjL)

	def getFacts(n, MOD):
		facts = [1] * (n + 1)
		for x in range(2, n + 1):
			facts[x] = facts[x - 1] * x % MOD
		return facts
	facts = getFacts(H + W, MOD)

	def getInvFacts(n, MOD):
		invFacts = [0] * (n + 1)
		invFacts[n] = pow(facts[n], MOD - 2, MOD)
		for x in reversed(range(n)):
			invFacts[x] = invFacts[x + 1] * (x + 1) % MOD
		return invFacts
	invFacts = getInvFacts(H + W, MOD)

	def getNum(r, c, MOD):
		return facts[r + c] * invFacts[r] * invFacts[c] % MOD
	dp = [0] * N
	for i in range(N):
		noi = nos[i]
		(r1, c1) = rcs[noi]
		v = getNum(r1 - 1, c1 - 1, MOD)
		for j in range(i):
			noj = nos[j]
			(r0, c0) = rcs[noj]
			if i == j or r0 > r1 or c0 > c1:
				continue
			(dr, dc) = (r1 - r0, c1 - c0)
			v -= dp[noj] * getNum(dr, dc, MOD)
			v %= MOD
		dp[noi] = v
	ans = getNum(H - 1, W - 1, MOD)
	for (i, (r, c)) in enumerate(rcs):
		(dr, dc) = (H - r, W - c)
		ans -= dp[i] * getNum(dr, dc, MOD)
		ans %= MOD
	print(ans)
solve()


mod = 10 ** 9 + 7
frac = [1] * 200001
for i in range(2, 200001):
	frac[i] = i * frac[i - 1] % mod
fraci = [None] * 200001
fraci[-1] = pow(frac[-1], mod - 2, mod)
for i in range(-2, -200001 - 1, -1):
	fraci[i] = fraci[i + 1] * (200001 + i + 1) % mod

def comb(a, b):
	if not a >= b >= 0:
		return 0
	return frac[a] * fraci[b] * fraci[a - b] % mod
(H, W, N) = map(int, input().split())
RC = [tuple(map(int, input().split())) for _ in range(N)] + [(1, 1), (H, W)]
RC.sort()
(R, C) = map(tuple, zip(*RC))
dp = [0] * (N + 2)
for i in range(1, N + 2):
	(r, c) = (R[i], C[i])
	res = comb(r + c - 2, r - 1)
	for k in range(1, i):
		(rk, ck) = (R[k], C[k])
		if ck > c:
			continue
		res = (res - comb(r - rk + c - ck, r - rk) * dp[k] % mod) % mod
	dp[i] = res
print(dp[-1])


(H, W, N) = map(int, input().split())
import sys
M = 10 ** 9 + 7

def C(n, r):
	if r < 0 or r > n:
		return 0
	r = min(r, n - r)
	return g1[n] * g2[r] * g2[n - r] % M
NNN = 2 * 10 ** 5
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range(2, NNN + 1):
	g1.append(g1[-1] * i % M)
	inverse.append(-inverse[M % i] * (M // i) % M)
	g2.append(g2[-1] * inverse[-1] % M)
vs = []
for _ in range(N):
	(X, Y) = map(int, input().split())
	vs.append((X, Y))
d = [0] * N
d2 = [0] * N
vs.sort()
for i in range(N - 1, -1, -1):
	(x, y) = vs[i]
	d2[i] = C(x + y - 2, x - 1)
	r = C(H - x + W - y, H - x)
	for j in range(N - 1, i, -1):
		(v, w) = vs[j]
		r = (r - C(v - x + w - y, v - x) * d[j]) % M
	d[i] = r
r = 0
for i in range(N):
	r = (r + d[i] * d2[i] % M) % M
r = (C(H + W - 2, H - 1) - r) % M
print(r)


(H, W, N) = map(int, input().split())
P = [list(map(int, input().split())) for i in range(N)]
P.sort(reverse=1)
MOD = 10 ** 9 + 7
fact = [1] * (H + W + 1)
rfact = [1] * (H + W + 1)
for i in range(H + W):
	fact[i + 1] = r = fact[i] * (i + 1) % MOD
	rfact[i + 1] = pow(r, MOD - 2, MOD)

def comb(n, k):
	return fact[n] * rfact[k] * rfact[n - k] % MOD
dp = [0] * N
for i in range(N):
	(r, c) = P[i]
	res = comb(H - r + W - c, H - r)
	for j in range(i):
		(r0, c0) = P[j]
		if not r <= r0 or not c <= c0:
			continue
		res -= comb(r0 - r + c0 - c, r0 - r) * dp[j] % MOD
	dp[i] = res % MOD
ans = comb(H + W - 2, H - 1)
for i in range(N):
	(r0, c0) = P[i]
	ans -= comb(r0 + c0 - 2, r0 - 1) * dp[i] % MOD
print(ans % MOD)


import sys
input = sys.stdin.readline
MAX = 2 * 10 ** 5 + 100
MOD = 10 ** 9 + 7
fact = [0] * MAX
inv = [0] * MAX
finv = [0] * MAX
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
for i in range(2, MAX):
	fact[i] = fact[i - 1] * i % MOD
	inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
	finv[i] = finv[i - 1] * inv[i] % MOD

def C(n, r):
	if n < r:
		return 0
	if n < 0 or r < 0:
		return 0
	return fact[n] * (finv[r] * finv[n - r] % MOD) % MOD
(H, W, N) = map(int, input().split())
rc = [tuple(map(int, input().split())) for _ in range(N)]
rc.sort(key=lambda t: t[0] + t[1])
ans = C(H + W - 2, H - 1)
dp = [0] * N
for i in range(N):
	(ri, ci) = rc[i]
	dp[i] = C(ri + ci - 2, ri - 1)
	for j in range(i):
		(rj, cj) = rc[j]
		dp[i] -= dp[j] * C(ri - rj + ci - cj, ri - rj)
		dp[i] %= MOD
	ans -= dp[i] * C(H - ri + W - ci, H - ri)
	ans %= MOD
print(ans)


from operator import itemgetter
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

class Combination:

	def __init__(self, N, MOD=10 ** 9 + 7):
		self.MOD = MOD
		(self.fact, self.inv) = self._make_factorial_list(N)

	def __call__(self, n, k):
		if k < 0 or k > n:
			return 0
		res = self.fact[n] * self.inv[k] % self.MOD
		res = res * self.inv[n - k] % self.MOD
		return res

	def _make_factorial_list(self, N):
		fact = [1] * (N + 1)
		inv = [1] * (N + 1)
		MOD = self.MOD
		for i in range(1, N + 1):
			fact[i] = fact[i - 1] * i % MOD
		inv[N] = pow(fact[N], MOD - 2, MOD)
		for i in range(N, 0, -1):
			inv[i - 1] = inv[i] * i % MOD
		return (fact, inv)

def main():
	(H, W, N) = map(int, input().split())
	XY = list((tuple(map(int, input().split())) for _ in range(N)))
	comb = Combination(H + W + 10, mod)
	fact = tuple(comb.fact)
	inv = tuple(comb.inv)
	edge = [[] for _ in range(N + 2)]
	indeg = {i: 0 for i in range(N + 2)}
	edge[0].append((N + 1, comb(H + W - 2, H - 1)))
	indeg[N + 1] += 1
	for (i, (x1, y1)) in enumerate(XY, 1):
		edge[0].append((i, comb(x1 + y1 - 2, x1 - 1)))
		indeg[i] += 1
		edge[i].append((N + 1, comb(H + W - x1 - y1, H - x1)))
		indeg[N + 1] += 1
		for (j, (x2, y2)) in enumerate(XY, 1):
			if i == j:
				continue
			if x1 <= x2 and y1 <= y2:
				edge[i].append((j, comb(x2 + y2 - x1 - y1, x2 - x1)))
				indeg[j] += 1
	order = sorted(indeg.items(), key=itemgetter(1))
	dp = [0] * (N + 2)
	dp[0] = -1
	for (s, _) in order:
		for (t, path) in edge[s]:
			dp[t] = (dp[t] - path * dp[s] + mod) % mod
	print(dp[N + 1])
main()


class Combination:

	def __init__(self, n_max, mod=10 ** 9 + 7):
		self.mod = mod
		f = 1
		self.fac = fac = [f]
		for i in range(1, n_max + 1):
			f = f * i % mod
			fac.append(f)
		f = pow(f, mod - 2, mod)
		self.facinv = facinv = [f]
		for i in range(n_max, 0, -1):
			f = f * i % mod
			facinv.append(f)
		facinv.reverse()

	def __call__(self, n, r):
		return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

	def nCr(self, n, r):
		if not 0 <= r <= n:
			return 0
		return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

def resolve():

	def route(a, b):
		dx = b[0] - a[0]
		dy = b[1] - a[1]
		if dx < 0 or dy < 0:
			return 0
		return cmb.nCr(dx + dy, dx)
	MOD = 10 ** 9 + 7
	(H, W, N) = map(int, input().split())
	wall = []
	for _ in range(N):
		(r, c) = map(lambda x: int(x) - 1, input().split())
		wall.append((r, c))
	wall.append((0, 0))
	wall.sort()
	cmb = Combination(H + W + 1)
	dp = [[0] * 2 for _ in range(N + 1)]
	dp[0][0] = 1
	for i in range(1, N + 1):
		for j in range(0, i):
			dp[i][0] += dp[j][1] * route(wall[j], wall[i]) % MOD
			dp[i][0] %= MOD
			dp[i][1] += dp[j][0] * route(wall[j], wall[i]) % MOD
			dp[i][1] %= MOD
	goal = (H - 1, W - 1)
	ng = 0
	for i in range(1, N + 1):
		ng -= dp[i][0] * route(wall[i], goal) % MOD
		ng += dp[i][1] * route(wall[i], goal) % MOD
		ng %= MOD
	all = cmb.nCr(H + W - 2, H - 1)
	ans = (all - ng + MOD) % MOD
	print(ans)
resolve()


import sys
input = lambda : sys.stdin.readline().strip()

class PERM_COMB_MOD:

	def __init__(self, max_n=510000, mod=10 ** 9 + 7):
		self.fac = [0] * max_n
		self.finv = [0] * max_n
		self.inv = [0] * max_n
		self.fac[0] = self.fac[1] = 1
		self.finv[0] = self.finv[1] = 1
		self.inv[1] = 1
		self.max = max_n
		self.mod = mod
		self._maesyori()

	def _maesyori(self):
		for i in range(2, self.max):
			self.fac[i] = self.fac[i - 1] * i % self.mod
			self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
			self.finv[i] = self.finv[i - 1] * self.inv[i] % self.mod

	def comb(self, n, k):
		if n < k:
			return 0
		if n < 0 or k < 0:
			return 0
		return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.mod) % self.mod
mod = 10 ** 9 + 7
PCM = PERM_COMB_MOD(3 * 10 ** 5, mod=mod)
(h, w, n) = map(int, input().split())
rc = [list(map(int, input().split())) for i in range(n)]
rc.append([h, w])
n += 1
rc.sort()
DP = [0] * (n + 1)
DP[0] = 1
for i in range(n):
	(r, c) = rc[i]
	DP[i + 1] = PCM.comb(r - 1 + c - 1, r - 1)
	for j in range(i):
		(rj, cj) = rc[j]
		if rj <= r and cj <= c:
			DP[i + 1] -= DP[j + 1] * PCM.comb(r - rj + c - cj, r - rj)
	DP[i + 1] %= mod
print(DP[-1])


def main():
	import sys
	from operator import itemgetter
	input = sys.stdin.readline
	mod = 1000000007
	nmax = 3 * 10 ** 5 + 1
	fac = [0] * (nmax + 1)
	finv = [0] * (nmax + 1)
	inv = [0] * (nmax + 1)
	fac[0] = 1
	fac[1] = 1
	finv[0] = 1
	finv[1] = 1
	inv[1] = 1
	for i in range(2, nmax):
		fac[i] = fac[i - 1] * i % mod
		inv[i] = mod - inv[mod % i] * (mod // i) % mod
		finv[i] = finv[i - 1] * inv[i] % mod

	def comb(n, r):
		if n < r:
			return 0
		else:
			return fac[n] * (finv[r] * finv[n - r] % mod) % mod
	(H, W, N) = map(int, input().split())
	block = []
	for _ in range(N):
		(r, c) = map(int, input().split())
		block.append((r, c))
	block.sort(key=itemgetter(1))
	block.sort(key=itemgetter(0))
	block.insert(0, (1, 1))
	dp_p = [0] * (N + 1)
	dp_n = [0] * (N + 1)
	dp_p[0] = 1
	for i in range(1, N + 1):
		(ri, ci) = block[i]
		for j in range(i):
			(rj, cj) = block[j]
			if ri >= rj and ci >= cj:
				dp_p[i] = (dp_p[i] + dp_n[j] * comb(ri - rj + ci - cj, ri - rj) % mod) % mod
				dp_n[i] = (dp_n[i] + dp_p[j] * comb(ri - rj + ci - cj, ri - rj) % mod) % mod
	ans = 0
	for i in range(N + 1):
		ans = (ans + (dp_p[i] - dp_n[i]) % mod * comb(H - block[i][0] + W - block[i][1], H - block[i][0]) % mod) % mod
	print(ans)
main()


(h, w, n) = map(int, input().split())
wall = [list(map(int, input().split())) for _ in range(n)]
wall.sort(key=lambda x: x[1])
wall.sort(key=lambda x: x[0])
mod = 10 ** 9 + 7
fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, h + w + 1):
	fac.append(fac[i - 1] * i % mod)
	inv.append(mod - inv[mod % i] * (mod // i) % mod)
	finv.append(finv[i - 1] * inv[i] % mod)

def nck(n, k):
	if n < k:
		return 0
	if n < 0 or k < 0:
		return 0
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod
dp = [0] * n
for i in range(n):
	res = 0
	for j in range(i):
		res += dp[j] * nck(wall[i][0] - wall[j][0] + wall[i][1] - wall[j][1], wall[i][0] - wall[j][0])
		res %= mod
	dp[i] = nck(wall[i][0] - 1 + wall[i][1] - 1, wall[i][0] - 1) - res
	dp[i] %= mod
ans = 0
for i in range(n):
	ans += dp[i] * nck(h - wall[i][0] + w - wall[i][1], h - wall[i][0])
	ans %= mod
print((nck(h - 1 + w - 1, h - 1) - ans) % mod)


MOD = 10 ** 9 + 7
kaijo_memo = []

def kaijo(n):
	if len(kaijo_memo) > n:
		return kaijo_memo[n]
	if len(kaijo_memo) == 0:
		kaijo_memo.append(1)
	while len(kaijo_memo) <= n:
		kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
	return kaijo_memo[n]
gyaku_kaijo_memo = []

def gyaku_kaijo(n):
	if len(gyaku_kaijo_memo) > n:
		return gyaku_kaijo_memo[n]
	if len(gyaku_kaijo_memo) == 0:
		gyaku_kaijo_memo.append(1)
	while len(gyaku_kaijo_memo) <= n:
		gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo), MOD - 2, MOD) % MOD)
	return gyaku_kaijo_memo[n]

def nCr(n, r):
	if n == r:
		return 1
	if n < r or r < 0:
		return 0
	ret = 1
	ret = ret * kaijo(n) % MOD
	ret = ret * gyaku_kaijo(r) % MOD
	ret = ret * gyaku_kaijo(n - r) % MOD
	return ret
(H, W, N) = list(map(int, input().split()))
wall = [0, H * W - 1]
for i in range(N):
	(r, c) = list(map(int, input().split()))
	wall.append((r - 1) * W + (c - 1))
wall.sort()
graph = [[] for i in range(N + 2)]
for i in range(N + 2):
	(y, x) = (wall[i] // W, wall[i] % W)
	for j in range(i + 1, N + 2):
		(ny, nx) = (wall[j] // W, wall[j] % W)
		if nx < x or ny < y:
			continue
		graph[j].append(i)
dp = [0 for i in range(N + 2)]
for j in range(1, N + 2):
	(y, x) = (wall[j] // W, wall[j] % W)
	dp[j] = nCr(y + x, y)
	for i in graph[j]:
		(py, px) = (y - wall[i] // W, x - wall[i] % W)
		dp[j] -= nCr(py + px, py) * dp[i]
		dp[j] %= MOD
print(dp[-1])


mod = 10 ** 9 + 7
frac = [1] * 200001
for i in range(2, 200001):
	frac[i] = i * frac[i - 1] % mod
fraci = [None] * 200001
fraci[-1] = pow(frac[-1], mod - 2, mod)
for i in range(-2, -200001 - 1, -1):
	fraci[i] = fraci[i + 1] * (200001 + i + 1) % mod

def comb(a, b):
	if not a >= b >= 0:
		return 0
	return frac[a] * fraci[b] * fraci[a - b] % mod

def count(a, b):
	((r1, c1), (r2, c2)) = (RC[a], RC[b])
	if c2 < c1:
		return 0
	return comb(r2 - r1 + c2 - c1, r2 - r1)
(H, W, N) = map(int, input().split())
RC = [list(map(int, input().split())) for _ in range(N)] + [[1, 1], [H, W]]
RC.sort()
dpe = [0] * (N + 2)
dpo = [0] * (N + 2)
dpe[0] += 1
for i in range(1, N + 2):
	rese = 0
	reso = 0
	for k in range(i):
		t = count(k, i)
		if not t:
			continue
		rese = (rese + t * dpo[k]) % mod
		reso = (reso + t * dpe[k]) % mod
	dpe[i] = rese
	dpo[i] = reso
print((dpo[-1] - dpe[-1]) % mod)