CodeEff/ECCO huggingface dataset:
# Original solution
from sys import stdin, stdout, stderr, setrecursionlimit
from functools import lru_cache

setrecursionlimit(10**7)

mod = 10**9 + 7

def solve():
    def binom(n, k):
        res = (modfact[n] * factinv[k]) % mod
        res = (res * factinv[n - k]) % mod
        return res

    h, w, a, b = list(map(int, input().split()))
    ans = 0
    modfact = [1] * (h + w)
    factinv = [1] * (h + w)

    for i in range(1, h + w):
        modfact[i] = (i * modfact[i - 1]) % mod
        factinv[i] = (pow(i, mod - 2, mod) * factinv[i - 1]) % mod

    for i in range(h - a):
        ans += (binom(b + i - 1, i) * binom(w + h - b - i - 2, h - i - 1)) % mod
        ans %= mod

    print(ans)

'''
@lru_cache(maxsize=None)
def binom(n, k):
    res = (modfact(n) * factinv(k)) % mod
    res = (res * factinv(n - k)) % mod
    return res

@lru_cache(maxsize=None)
def modfact(n):
    if n == 0:
        return 1

    return (n * modfact(n - 1)) % mod

@lru_cache(maxsize=None)
def factinv(n):
    if n == 0:
        return 1

    return (pow(n, mod - 2, mod) * factinv(n - 1)) % mod
'''

if __name__ == '__main__':
    solve()

# Optimized solution
from sys import stdin, stdout, stderr

mod = 10**9 + 7

def solve():
    def binom(n, k):
        res = (modfact[n] * factinv[k]) % mod
        res = (res * factinv[n - k]) % mod
        return res

    h, w, a, b = list(map(int, input().split()))
    ans = 0
    modfact = [1] * (h + w)
    factinv = [1] * (h + w)
    inv = [1] * (h + w)

    for i in range(2, h + w):
        modfact[i] = (i * modfact[i - 1]) % mod
        inv[i] = (-(mod // i) * inv[mod % i]) % mod
        factinv[i] = (inv[i] * factinv[i - 1]) % mod

    for i in range(h - a):
        ans += (binom(b + i - 1, i) * binom(w + h - b - i - 2, h - i - 1)) % mod
        ans %= mod

    print(ans)

if __name__ == '__main__':
    solve()
# Original solution
from sys import stdin, stdout, stderr

mod = 10**9 + 7

def solve():
    def binom(n, k):
        res = (modfact[n] * factinv[k]) % mod
        res = (res * factinv[n - k]) % mod
        return res

    h, w, a, b = list(map(int, input().split()))
    ans = 0
    modfact = [1] * (h + w)
    factinv = [1] * (h + w)
    inv = [1] * (h + w)

    for i in range(2, h + w):
        modfact[i] = (i * modfact[i - 1]) % mod
        inv[i] = (-(mod // i) * inv[mod % i]) % mod
        factinv[i] = (inv[i] * factinv[i - 1]) % mod

    for i in range(h - a):
        ans += (binom(b + i - 1, i) * binom(w + h - b - i - 2, h - i - 1)) % mod
        ans %= mod

    print(ans)

if __name__ == '__main__':
    solve()

# Optimized solution
from sys import stdin, stdout, stderr

mod = 10**9 + 7

def solve():
    def binom(n, k):
        res = (modfact[n] * factinv[k]) % mod
        res = (res * factinv[n - k]) % mod
        return res

    h, w, a, b = list(map(int, input().split()))
    ans = 0
    modfact = [1] * (h + w)
    factinv = [1] * (h + w)
    inv = [1] * (h + w)

    for i in range(2, h + w):
        modfact[i] = (i * modfact[i - 1]) % mod

    factinv[h + w - 1] = pow(modfact[h + w - 1], mod - 2, mod)

    for i in range(h + w - 2, 0, -1):
        factinv[i] = (factinv[i + 1] * (i + 1)) % mod

    for i in range(h - a):
        ans += (binom(b + i - 1, i) * binom(w + h - b - i - 2, h - i - 1)) % mod
        ans %= mod

    print(ans)

if __name__ == '__main__':
    solve()
# Original solution
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

from collections import deque

n, q = list(map(int, input().split()))
a = [deque() for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        if a[c[1]]:
            if a[c[1]][-1] < c[2]:
                a[c[1]].append(c[2])
            elif a[c[1]][0] > c[2]:
                a[c[1]].appendleft(c[2])
            else:
                left = 0
                right = len(a[c[1]])-1
                while right - left > 1:
                    mid = (right + left)//2
                    if a[c[1]][mid] < c[2]:
                        left = mid
                    else:
                        right = mid
                a[c[1]].insert(right, c[2])
        else:
            a[c[1]].append(c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print((a[c[1]][-1]))
    else:
        if a[c[1]]:
            a[c[1]].pop()




# Optimized solution
import heapq

n, q = list(map(int, input().split()))
a = [[] for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        heapq.heappush(a[c[1]],-c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print((-a[c[1]][0]))
    else:
        if a[c[1]]:
            heapq.heappop(a[c[1]])
# Original solution
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    print(("NO" if s.count("x") >= 8 else "YES"))


if __name__ == '__main__':
    solve()


# Optimized solution
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    print(("YES" if s.count("x") < 8 else "NO"))


if __name__ == '__main__':
    solve()
# Original solution
N,X=list(map(int,input().split()))
above=[0]*N
now=0
data=[0]*N
for i in range(N):
    b,l,u=list(map(int,input().split()))
    above[i]=(i,b*l+(X-b)*u)
    data[i]=(b,l,u)
    now-=l*b
above.sort(key=lambda x:x[1],reverse=True)
used=set()
ans=0
idx=0
for i in range(N):
    if now+above[i][1]<0:
        now+=above[i][1]
        used|={above[i][0]}
        ans+=X
        idx=i+1
    else:
        break
base=ans
ans+=X
now*=-1
for i in range(N):
    b,l,u=data[i]
    if i in used:
        now0=now+b*l+(X-b)*u
        M=base-X
    else:
        now0=now
        M=base
    for i in range(idx,N):
        if now0+above[i][1]<0:
            now+=above[i][1]
    if now0<=b*l:
        ans=min(ans,M+(now0+l-1)//l)
    elif now0<=b*l+(X-b)*u:
        ans=min(ans,M+b+(now0-b*l+u-1)//u)
print(ans)

# Optimized solution
N,X=list(map(int,input().split()))
data=[0]*N
A=[0]*N
zero=0
for i in range(N):
    b,l,u=list(map(int,input().split()))
    zero-=l*b
    data[i]=(b,l,u)
    A[i]=(i,(X-b)*u+b*l)
A.sort(key=lambda x:x[1],reverse=True)
S=[0]*N
idx=[0]*N
for i,a in enumerate(A):
    S[i]=S[i-1]+a[1]
    idx[a[0]]=i
def check(k):
    q=k//X
    r=k-q*X
    for i in range(N):
        b,l,u=data[i]
        if q==0:
            now=zero
        elif idx[i]<q:
            now=zero+S[q]-A[idx[i]][1]
        else:
            now=zero+S[q-1]
        if r<=b:
            now+=r*l
        else:
            now+=(r-b)*u+b*l
        if now>=0:
            return True
    return False
Mincan=N*X
Maxcant=-1
c=(1,2)
while True:
    if Maxcant+1==Mincan:
        ans=Mincan
        break
    x=N*X*c[0]//c[1]
    if check(x):
        if Mincan>x:
            Mincan=x
            c=(c[0]*2-1,c[1]*2)
    else:
        if Maxcant<x:
            Maxcant=x
            c=(c[0]*2+1,c[1]*2)
print(ans)
# Original solution
import sys
from bisect import bisect_left
from itertools import accumulate
from operator import itemgetter

n, x = list(map(int, input().split()))
exams = []
norma = 0
for i, line in enumerate(sys.stdin):
    b, l, u = list(map(int, line.split()))
    exams.append((u * x - b * (u - l), b, l, u, i))
    norma += b * l
exams_sorted = sorted(exams, reverse=True)
exams_acc = list(accumulate(list(map(itemgetter(0), exams_sorted))))
exams_loc = {i: loc for loc, i in enumerate(map(itemgetter(4), exams_sorted))}
# print(norma)
# print(exams_sorted)
# print(exams_acc)

ans = 10 ** 10
base_loc = bisect_left(exams_acc, norma)
base_ans = base_loc * x
base_remain_norma = norma - exams_acc[base_loc - 1] if base_loc > 0 else norma
# print(f'base_remain_norma:{base_remain_norma}')
for d, b, l, u, i in exams:
    exam_loc = exams_loc[i]
    if base_loc <= exam_loc:
        curr_ans = base_ans
        curr_remain_norma = base_remain_norma
    else:
        tmp_norma = norma + d
        tmp_loc = bisect_left(exams_acc, tmp_norma)
        curr_ans = (tmp_loc - 1) * x
        curr_remain_norma = tmp_norma - exams_acc[tmp_loc - 1]
    if curr_remain_norma <= b * l:
        extra = (curr_remain_norma - 1) // l + 1
    else:
        extra = (curr_remain_norma + b * (u - l) - 1) // u + 1
    # print(d, b, l, u, i)
    # print(f'exl:{exam_loc}  {int(base_loc <= exam_loc)}  norma:{curr_remain_norma}  curans:{curr_ans}  '
    #       f'extra:{extra}')
    if extra > x:
        continue
    ans = min(ans, curr_ans + extra)

print(ans)


# Optimized solution
import sys

n, x = list(map(int, input().split()))
exams = []
norma = 0
for i, line in enumerate(sys.stdin):
    b, l, u = list(map(int, line.split()))
    exams.append((u * x - b * (u - l), b, l, u, i))
    norma += b * l
exams_sorted = sorted(exams, reverse=True)

remain_norma = norma
sub_d = -1
i = 0
used = set()
for i, (d, b, l, u, ei) in enumerate(exams_sorted):
    if remain_norma < d:
        sub_d = d
        break
    remain_norma -= d
    used.add(ei)

if sub_d == -1:
    print((n * x))
    exit()

base_ans = i * x
base_remain_norma = remain_norma

ans = 10 ** 10

for d, b, l, u, i in exams:
    if i in used:
        curr_remain_norma = base_remain_norma + d - sub_d
    else:
        curr_remain_norma = base_remain_norma
    if curr_remain_norma <= b * l:
        extra = (curr_remain_norma - 1) // l + 1
    else:
        extra = (curr_remain_norma + b * (u - l) - 1) // u + 1
    if extra > x:
        continue
    ans = min(ans, base_ans + extra)

print(ans)
# Original solution
n, x = list(map(int, input().split()))
B = 0
blu = []

for i in range(n):
  b, l, u = list(map(int, input().split()))
  blu.append((b, l, u, x*u-b*u+b*l))
  B += b*l
blu.sort(key=lambda x: x[3], reverse=True)

ans = n*x
for i in range(n):
  ok = n*x
  ng = -1
  while ok-ng>1:
    A = 0
    tB = B
    mid = (ok+ng)//2
    k = mid//x
    t = mid%x
    for j in range(n):
      if j!=i and k>0:
        A += x*blu[j][2]
        tB += blu[j][0]*(blu[j][2]-blu[j][1])
        k -= 1
      elif k<=0:
        break
    if t!=0:
      if t<=blu[i][0]:
        A += t*blu[i][1]
      else:
        A += t*blu[i][2]
        tB += blu[i][0]*(blu[i][2]-blu[i][1])
    if A>=tB:
      ok = mid
    else:
      ng = mid
  ans = min(ans, ok)

print(ans)

# Optimized solution
n, x = list(map(int, input().split()))
B = 0
blu = []
s = [0 for i in range(n)]

for i in range(n):
  b, l, u = list(map(int, input().split()))
  blu.append((b, l, u, x*u-b*u+b*l))
  B += b*l
blu.sort(key=lambda x: x[3], reverse=True)

for i in range(n):
  if i==0:
    s[i] = blu[i][3]
  else:
    s[i] = s[i-1] + blu[i][3]

ok = n*x
ng = -1
while ok-ng>1:
  A = 0
  mid = (ok+ng)//2
  k = mid//x
  t = mid%x
  for i in range(n):
    if t<=blu[i][0]:
      rm = t*blu[i][1]
    else:
      rm = t*blu[i][2] - blu[i][0]*(blu[i][2]-blu[i][1])
    if k==0:
      A = max(A, rm)
    elif i<k:
      A = max(A, s[k]-blu[i][3]+rm)
    else:
      A = max(A, s[k-1]+rm)
  if A>=B:
    ok = mid
  else:
    ng = mid

print(ok)
# Original solution
N, X = list(map(int, input().split()))
items = []
for i in range(N):
    b, l, u = list(map(int, input().split()))
    items.append((b, l, u, u * (X - b), - b * l))

items = sorted(items, key=lambda x: -(x[3] - x[4]))


def f(num):
    cnt = num // X
    mod = num % X
    point = 0
    for i in range(cnt):
        point += items[i][3]
    for i in range(cnt, N):
        point += items[i][4]

    if mod == 0:
        if point >= 0:
            return True
        else:
            return False
    else:
        tmp = -float("inf")
        for i, tmp2 in enumerate(items):
            b, l, u, d1, d2 = tmp2
            if mod >= b:
                mul = u * (mod - b)
            else:
                mul = l * (mod - b)

            if i < cnt:
                tmp = max(tmp, point - d1 + mul + items[cnt][3] - items[cnt][4])
            else:
                tmp = max(tmp, point - d2 + mul)
        if tmp >= 0:
            return True
        else:
            return False

ok = N * X + 1
ng = - 1
while (ok - ng) > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)


# Optimized solution
N, X = list(map(int, input().split()))
items = []
for i in range(N):
    b, l, u = list(map(int, input().split()))
    items.append((b, l, u, u * (X - b), - b * l))

items = sorted(items, key=lambda x: -(x[3] - x[4]))


def f(num):
    cnt = num // X
    mod = num % X
    point = 0
    for i in range(cnt):
        point += items[i][3]
    for i in range(cnt, N):
        point += items[i][4]

    if mod == 0:
        if point >= 0:
            return True
        else:
            return False
    else:
        tmp = -float("inf")
        for i in range(N):
            b, l, u, d1, d2 = items[i]
            if mod >= b:
                mul = u * (mod - b)
            else:
                mul = l * (mod - b)

            if i < cnt:
                tmp = max(tmp, point - d1 + mul + items[cnt][3] - items[cnt][4])
            else:
                tmp = max(tmp, point - d2 + mul)
        if tmp >= 0:
            return True
        else:
            return False

ok = N * X + 1
ng = - 1
while (ok - ng) > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)
# Original solution
import sys
input = sys.stdin.readline

N,X=list(map(int,input().split()))
A=[list(map(int,input().split())) for i in range(N)]

A.sort(key=lambda x:x[2]*(X-x[0])+x[0]*x[1],reverse=True)
ALL=[a[2]*(X-a[0])+a[0]*a[1] for a in A]

from itertools import accumulate

SUM=[0]+list(accumulate(ALL))

MAX=0
MINUS=0

for a,r,l in A:
    MAX+=a
    MINUS+=a*r

OUT=-1

def binsearch(score):

    alluse=score//X
    rest=score-alluse*X

    for ri in range(N):
        plus=0
        
        if rest<A[ri][0]:
            plus+=rest*A[ri][1]
        else:
            plus+=rest*A[ri][2]+A[ri][0]*A[ri][1]-A[ri][0]*A[ri][2]

        if alluse<=ri:
            plus+=SUM[alluse]

        else:
            plus+=SUM[alluse+1]-ALL[ri]

        #print(score,ri,plus)

        if plus>=MINUS:
            return 1

    return 0


while MAX-OUT>1:
    mid=(MAX+OUT)//2

    x=binsearch(mid)

    if x==1:
        MAX=mid
    else:
        OUT=mid

print(MAX)


# Optimized solution
import sys
input = sys.stdin.readline

N,X=list(map(int,input().split()))
A=[list(map(int,input().split())) for i in range(N)]

A.sort(key=lambda x:x[2]*(X-x[0])+x[0]*x[1],reverse=True)
ALL=[a[2]*(X-a[0])+a[0]*a[1] for a in A]

from itertools import accumulate

SUM=[0]+list(accumulate(ALL))

MAX=0
MINUS=0

for a,r,l in A:
    MAX+=a
    MINUS+=a*r

OUT=-1

def binsearch(score):

    alluse=score//X
    rest=score-alluse*X

    for ri in range(N):
        plus=0
        b,l,u=A[ri]
        
        if rest<b:
            plus+=rest*l
        else:
            plus+=rest*u+b*l-b*u

        if alluse<=ri:
            plus+=SUM[alluse]

        else:
            plus+=SUM[alluse+1]-ALL[ri]

        #print(score,ri,plus)

        if plus>=MINUS:
            return 1

    return 0


while MAX-OUT>1:
    mid=(MAX+OUT)//2

    if binsearch(mid)==1:
        MAX=mid
    else:
        OUT=mid

print(MAX)
# Original solution
import sys
import math
readline = sys.stdin.readline

N, X = list(map(int, input().split()))

q_array = []

score_needed = 0

for i in range(N):
    b, l, u = list(map(int, readline().split()))
    q_array.append([b, l, u, b * l + (X - b) * u])
    score_needed += b * l

q_array = sorted(q_array, key=lambda x: -x[3])

ans = 0
# print(q_array)
for i in range(N):
    if q_array[i][3] <= score_needed:
        ans += X
        score_needed -= q_array[i][3]
        if score_needed == 0:
            break
    else:
        study_min = X
        # print(score_needed)
        for j in range(i, N):
            b, l, u, s = q_array[j]
            if score_needed > s:
                break
            yobun = s - score_needed
            if score_needed <= b * l:
                study_min = min(study_min, math.ceil(score_needed / l))
            else:
                study_min = min(study_min, b + math.ceil(
                    (score_needed - b * l) / u))
            for k in range(i):
                b, l, u, s = q_array[k]
                needed = s - yobun
                if score_needed <= b * l:
                    study_min = min(study_min, math.ceil(needed / l))
                else:
                    study_min = min(study_min, b + math.ceil(
                        (needed - b * l) / u))
        ans += study_min
        break
print(ans)

# Optimized solution
import sys
readline = sys.stdin.readline

N, X = list(map(int, input().split()))

q_array = []
s_array = []

score_needed = 0

for i in range(N):
    b, l, u = list(map(int, readline().split()))
    q_array.append([b, l, u, b * l + (X - b) * u])
    s_array.append(b * l + (X - b) * u)
    score_needed += b * l

q_array = sorted(q_array, key=lambda x: -x[3])
s_array = sorted(s_array, key=lambda x: -x)
sum_array = []
ss = 0
for s in s_array:
    ss += s
    sum_array.append(ss)
ans_min = 0
ans_max = N * X
if score_needed == 0:
    print((0))
    exit()
while ans_max - ans_min > 1:
    ans = (ans_min + ans_max) // 2
    use_all = ans // X
    use_part = ans % X
    # print(use_all, use_part)
    score_get_max = 0
    score_tmp = 0
    if use_part == 0:
        score_get_max = sum_array[use_all - 1]
    else:
        score_get_max = 0
        score_tmp = 0
        for q in q_array:
            b, l, u, s = q
            score_tmp = 0
            if use_part <= b:
                score_tmp = use_part * l
            else:
                score_tmp = (b * l + (use_part - b) * u)
            if use_all > 0:
                if s_array[use_all - 1] <= s:
                    score_tmp += (sum_array[use_all] - s)
                else:
                    score_tmp += sum_array[use_all - 1]
            score_get_max = max(score_get_max, score_tmp)
    # print(ans, score_get_max)
    if score_get_max >= score_needed:
        ans_max = ans
    else:
        ans_min = ans

print(ans_max)
# Original solution
class Combination:
    '''MOD上の
    計算量：階乗・逆元テーブルの作成O(N)
    nCkを求めるO(1)'''

    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):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


h, w, n = list(map(int, input().split()))
info = [(1, 1)] + [tuple(map(int, input().split())) for i in range(n)] + [(h, w)]
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))


# Optimized solution
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):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


h, w, n = list(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))
# Original solution
# coding: utf-8
# Your code here!
SIZE=300000; MOD=10**9+7 #ここを変更する

inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod MOD
fac = [0]*(SIZE+1)# fac[j] = j! mod MOD
finv = [0]*(SIZE+1)# finv[j] = (j!)^{-1} mod MOD
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): # nCk mod MOD の計算
    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])

#print(xy)

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
#print(dp)
for i,dpi in enumerate(dp):
    x,y=xy[i]
    ans += choose(h-x + w-y, w-y) * dpi
    ans %= MOD
print(ans)




# Optimized solution
# coding: utf-8
# Your code here!
SIZE=300000; MOD=10**9+7 #ここを変更する

inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod MOD
fac = [0]*(SIZE+1)# fac[j] = j! mod MOD
finv = [0]*(SIZE+1)# finv[j] = (j!)^{-1} mod MOD
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): # nCk mod MOD の計算
    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()

#print(xy)

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
#print(dp)
for i,dpi in enumerate(dp):
    x,y=xy[i]
    ans += choose(h-x + w-y, w-y) * dpi
    ans %= MOD
print(ans)
# Original solution
str1 , str2 = input().split(" ")
str3 = str2+str1
print(str3)

# Optimized solution
#---Strings
S, T = map(str, input().split(" "))
print(T, S, sep="")
# Original solution
def main():
    S,T = input().split()
    print(("{}{}".format(T,S)))
main()

# Optimized solution
S,T = input().split()
print((T+S))
# Original solution
S=list(input().split())
a=S[1]+S[0]
print(a)

# Optimized solution
S,T=input().split()
print((T+S))
# Original solution
import sys
S,T = input().split()

if not ( S.islower() and T.islower() ): sys.exit()
if not ( 1 <= len(S) <= 100 and 1 <= len(S) <= 100 ): sys.exit()

print(T,end='')
print(S)


# Optimized solution
import sys
S,T = input().split()

if not ( S.islower() and T.islower() ): sys.exit()
if not ( 1 <= len(S) <= 100 and 1 <= len(S) <= 100 ): sys.exit()

print(T,S,sep='')
# Original solution
s,t=list(map(str,input().split()))
print((t+s))


# Optimized solution
s,t=input().split()
print((t+s))
# Original solution
S, T = input().split()
S = str(S)
T = str(T)
print((T+S))

# Optimized solution
def funk(S,T):
    return T+S
S,T = input().split()
print((funk(S,T)))