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 = int(1e9+7)

fact = [1 for _ in range(200001)]
for i in range(2, 200001):
    fact[i] = fact[i-1] * i % mod

fraci = [None] * 200001
fraci[-1] = pow(fact[-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 fact[a]*fraci[b]*fraci[a-b]%mod


h, w, n = [int(i) for i in raw_input().split()]
walls = []

for i in xrange(n):
    i, j = [int(i) for i in raw_input().split()]
    walls.append((i-1,j-1))
walls.append((h-1, w-1))

walls.sort()

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def binomial(n, k):
    
    

    p = int(1e9) + 7
    first = 1
    for x in range(1, n+1):
        first = first * x % p

    second = 1
    for x in range(1, k+1):
        second = second * x % p

    third = 1
    for x in range(1, n-k+1):
        third = third * x % p

    output = first * modinv(second, p) * modinv(third, p) % p

    return output

f = [0] * len(walls) 



for i in range(len(walls)):
    f[i] = comb(walls[i][0]+walls[i][1], walls[i][0])





p = int(1e9+7)
for i in range(len(walls)):
    for j in range(i+1, len(walls)):
        if walls[j][0] >= walls[i][0] and walls[j][1] >= walls[i][1]:
            f[j] -= f[i] * comb(walls[j][0]-walls[i][0]+walls[j][1]-walls[i][1], walls[j][0]-walls[i][0])
            f[j] %= p


print f[-1] % (int(1e9)+7)

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

import numpy as np

MOD = 10**9 + 7

H,W,N = map(int,input().split())
R,C = np.array(sys.stdin.read().split() + [H,W],dtype=np.int64).reshape(N+1,2).T

ind = np.argsort((R<<32)+C)
R = R[ind]
C = C[ind]

def cumprod(arr):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

U = 2 * 10**5 + 10
x = np.arange(U,dtype=np.int64)
x[0] = 1
fact = cumprod(x)
x = np.arange(U,0,-1,dtype=np.int64)
x[0] = pow(int(fact[-1]),MOD-2,MOD)
fact_inv = cumprod(x)[::-1]

dp = np.zeros(N+1,dtype=np.int64)
dp += fact[R+C-2] * fact_inv[R-1] % MOD * fact_inv[C-1] % MOD

for i,(r,c) in enumerate(zip(R,C)):
    j = np.where((R<=r)&(C<=c)&(R+C<r+c))
    dx,dy = r-R[j],c-C[j]
    dp[i] -= (dp[j] * fact[dx+dy] % MOD * fact_inv[dx] % MOD * fact_inv[dy] % MOD).sum()
    dp[i] %= MOD

answer = dp[-1]
print(answer)

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

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

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

Solution (Python):
mod = 10**9+7
frac = [1]*364364
for i in range(2,364364):
    frac[i] = i * frac[i-1]%mod
fraci = [None]*364364
fraci[-1] = pow(frac[-1], mod -2, mod)
for i in range(-2, -364364-1, -1):
    fraci[i] = fraci[i+1] * (364364 + 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)

Solution (Python):


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



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)

Solution (Python):


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)

Solution (Python):
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] * (h + w + 1)
    re_fct = [1] * (h + w + 1)
    fct_i = 1
    for i in range(1, h + w + 1):
        fct_i = fct_i * i % md
        fct[i] = fct_i
    
    re_i = pow(fct_i, md - 2, md)
    for i in range(h + w, 1, -1):
        re_fct[i] = re_i
        re_i = re_i * i % md
    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()

Solution (Python):
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] * (h + w + 1)
    re_fct = [1] * (h + w + 1)
    fct_i = 1
    for i in range(1, h + w + 1):
        fct_i = fct_i * i % md
        fct[i] = 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[i] = re_i
        re_i = re_i * i % md
    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()

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

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

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

Solution (Python):


MOD = 1000000007


maxn = 200005
fact = [1] * maxn
inv = [1] * maxn
ifact = [1] * maxn
for i in range(2, maxn):
    fact[i] = fact[i - 1] * i % MOD

    q = MOD / i
    r = MOD % i
    inv[i] = (-q * inv[r]) % MOD

    ifact[i] = ifact[i - 1] * inv[i] % MOD

def count_paths(a, b):
    xa, ya = cells[a]
    xb, yb = cells[b]
    if xa <= xb and ya <= yb:
        resp = fact[xb - xa + yb - ya] * ifact[xb - xa] % MOD
        resp = resp * ifact[yb - ya] % MOD
        return resp
    return 0


n, m, k = map(int, raw_input().split())
cells = [[1, 1]]
for _ in range(k):
    cells.append(map(int, raw_input().split()))
cells.append([n, m])
cells.sort()
k += 2

dp = [0] * k
dp[0] = 1
for i in range(1, k):
    dp[i] = count_paths(0, i)
    for j in range(1, i):
        dp[i] -= dp[j] * count_paths(j, i)
        dp[i] %= MOD
print(dp[k - 1])

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

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