Problem:
 Score : 100 points    Problem Statement 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 .        Sample Input 1 3 4 2
2 2
1 4      Sample Output 1 3  There are three paths as follows:        Sample Input 2 5 2 2
2 1
4 2      Sample Output 2 0  There may be no paths.       Sample Input 3 5 5 4
3 1
3 5
1 3
5 3      Sample Output 3 24       Sample Input 4 100000 100000 1
50000 50000      Sample Output 4 123445622  Be sure to print the count modulo 10^9 + 7 .

Solution (Python):
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])

Solution (Python):






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)

Solution (Python):
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])

Solution (Python):

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)


if __name__ == "__main__":
    resolve()

Solution (Python):

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])


if __name__ == "__main__":
    resolve()

Solution (Python):
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)

Solution (Python):
from operator import itemgetter
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

mod = 10 ** 9 + 7


class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    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])


if __name__ == "__main__":
    main()

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self, n):
        fact, invfact = [1] * (n + 1), [1] * (n + 1)
        for i in range(1, n + 1): fact[i] = i * fact[i - 1] % MOD
        invfact[n] = pow(fact[n], MOD - 2, MOD)
        for i in range(n - 1, -1, -1): invfact[i] = invfact[i + 1] * (i + 1) % MOD
        self._fact, self._invfact = fact, invfact

    def inv(self, n):
        return self._fact[n - 1] * self._invfact[n] % MOD

    def fact(self, n):
        return self._fact[n]

    def invfact(self, n):
        return self._invfact[n]

    def comb(self, n, k):
        if k < 0 or n < k: return 0
        return self._fact[n] * self._invfact[k] % MOD * self._invfact[n - k] % MOD

    def perm(self, n, k):
        if k < 0 or n < k: return 0
        return self._fact[n] * self._invfact[n - k] % MOD

def resolve():
    m, n, K = map(int, input().split())
    m -= 1; n -= 1
    mf = modfact(m + n)
    block = [None] * K
    for k in range(K):
        i, j = map(int, input().split())
        i -= 1; j -= 1
        block[k] = (i, j)
    block.append((m, n))
    K += 1
    block.sort(lambda tup : tup[0] + tup[1])

    dp = [0] * K
    for k in range(K):
        i, j = block[k]
        dp[k] += mf.comb(i + j, i)
        for k0 in range(k):
            pi, pj = block[k0]
            dp[k] -= dp[k0] * mf.comb((i - pi) + (j - pj), i - pi)
            dp[k] %= MOD

    print(dp[-1])
resolve()

Solution (Python):
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)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self,n):
        fact=[1]*(n+1); invfact=[1]*(n+1)
        for i in range(1,n+1): fact[i]=i*fact[i-1]%MOD
        invfact[n]=pow(fact[n],MOD-2,MOD)
        for i in range(n-1,-1,-1): invfact[i]=invfact[i+1]*(i+1)%MOD
        self.__fact=fact; self.__invfact=invfact

    def inv(self,n):
        assert(n>0)
        return self.__fact[n-1]*self.__invfact[n]%MOD

    def fact(self,n):
        return self.__fact[n]

    def invfact(self,n):
        return self.__invfact[n]

    def comb(self,n,k):
        if(k<0 or n<k): return 0
        return self.__fact[n]*self.__invfact[k]*self.__invfact[n-k]%MOD

    def perm(self,n,k):
        if(k<0 or n<k): return 0
        return self.__fact[n]*self.__invfact[n-k]%MOD

def resolve():
    h,w,n=map(int,input().split())
    RC=[None]*n
    for i in range(n):
        r,c=map(int,input().split())
        r-=1; c-=1
        RC[i]=(r,c)
    RC.append((h-1,w-1))
    n+=1
    RC.sort(lambda p:sum(p))

    mf=modfact(h+w)
    f=lambda x,y:mf.comb(x+y,x)
    dp=[None]*n
    for i in range(n):
        r,c=RC[i]
        res=f(r,c)
        for j in range(i):
            r0,c0=RC[j]
            res-=dp[j]*f(r-r0,c-c0)
        dp[i]=res%MOD

    print(dp[-1])
resolve()

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):
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)


if __name__ == '__main__':
    main()

Solution (Python):
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 = 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)

Solution (Python):






from sys import stdin, stdout, setrecursionlimit

input = stdin.readline
flush = stdout.flush





OUT = []


def write(item, sep=" "):
    if type(item) is int:
        OUT.append(str(item))
    elif type(item) is float:
        OUT.append("%.9f" % item)
    elif type(item) is list or type(item) is tuple:
        if type(item[0]) is int:
            OUT.append(sep.join(map(str, item)))
        else:
            OUT.append(sep.join(item))
    else:
        OUT.append(item)


def PRINT(sep="\n"):
    print(sep.join(OUT))


GI = lambda: int(input())
GS = lambda: input().rstrip()

gi = lambda: list(map(int, input().split()))
gs = lambda: input().split()

digits = lambda i: list(map(int, str(i)))




h, w, n = gi()

MOD = pow(10, 9) + 7

fact = [1, 1]
inv = [1, 1]
f = 1
for i in xrange(2, 300005):
    f = f * i % MOD
    fact.append(f)
    inv.append(pow(f, MOD - 2, MOD))

def mnomial(a, b):
    a = abs(a)
    b = abs(b)
    return fact[a + b] * inv[a] % MOD * inv[b] % MOD

p = [(h - 1, w - 1, 1)]

for i in xrange(n):
    a, b = gi()
    p.append((a - 1, b - 1, 0))

p.sort(key = lambda i: map(abs, i))

def solve(id):
    N = len(p)
    dp = [0] * N
    ans = 0
    for i, (h, w, ID) in enumerate(p):
        tot_1 = mnomial(h, w)
        for j in xrange(i):
            if abs(h - p[j][0]) > abs(h) or abs(w - p[j][1]) > abs(w):
                continue
            if abs(p[j][0]) > abs(h) or abs(p[j][1]) > abs(w) or p[j][2] == ID == id:
                continue
            tot_1 = (tot_1 - dp[j] * mnomial(h - p[j][0], w - p[j][1]) % MOD) % MOD
        dp[i] = tot_1
        if ID == id:
            ans = (ans + tot_1) % MOD
    return ans

ans = 1
for i in xrange(1, 2):
    ans = ans * solve(i) % MOD
print ans

Solution (Python):
import sys
h, w, n = [int(i) for i in sys.stdin.readline().split()]
m = 1000000007
fact = [1, 1]
for i in range(2, 200002):
    fact.append(fact[-1] * i % m)
inv = [pow(i, m - 2, m) for i in fact]
f = lambda i: fact[i[0] + i[1]] * inv[i[0]] * inv[i[1]] % m
dp = [0] * (n + 1)
p = [[int(i) - 1 for i in sys.stdin.readline().split()] for j in range(n)]
p = sorted(p + [[h - 1, w - 1]])
for i in range(n + 1):
    h1, w1 = p[i]
    tot = f([h1, w1])
    for j in range(i):
        if p[j][1] > w1:
            continue
        tot = (tot - dp[j] * f([h1 - p[j][0], w1 - p[j][1]]) % m) % m
    dp[i] = tot
print(dp[-1])

Solution (Python):
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()

Solution (Python):


import sys
mod=1000000007

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


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)