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.



Sample input:
3 4 2
2 2
1 4


Sample output:
3

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#
#   Bad python template TM
#
#       Zeyu, 2019
#

from sys import stdin, stdout, setrecursionlimit

input = stdin.readline
flush = stdout.flush

# setrecursionlimit(1000000)

############################################################

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

# from https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_4
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

#n=int(input())
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)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_h

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):
    # n choose k mod p
    # (n, k) mod m = (n! * (k!)^-1 * ((n - k)!)^-1) mod m

    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) # ways to reach dest without going through f[i]

# print walls

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

# print f

# f[i] = no of ways to reach (h,w) without going walls[0..i]

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
print f[-1] % (int(1e9)+7)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# 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)

Submission status: Accepted

Solution code:
# 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)

Submission status: Accepted

Solution code:
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
    # fct_i**(md-2)が逆元re_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()

Submission status: Accepted

Solution code:
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]
    # fct_i**(md-2)が逆元re_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()

Submission status: Accepted

Solution code:
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)#i-1番目までに触れず、i番目のブロックに触れる経路数

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

Submission status: Accepted

Solution code:


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

Submission status: Accepted

Solution code:
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)

Submission status: Runtime Error

Solution code:

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

    # 全体 - ng
    all = cmb.nCr(H+W-2, H-1)
    ans = (all - ng + MOD) % MOD
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
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)

# combinationの準備
# md>n_maxの条件
md = 10 ** 9 + 7
n_max = 100
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)]
    # i番目の壁まで無傷で来る方法の数
    # (全ルート)－(i-1までの壁にぶつかる分)
    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()

Submission status: Runtime Error

Solution code:
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)

# combinationの準備
# md>n_maxの条件
md = 10 ** 9 + 7
n_max = 100
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)]
    # i番目の壁まで無傷で来る方法の数
    # (全ルート)－(i-1までの壁にぶつかる分)
    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) 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) for v, (r, c) in zip(dp, rc))
    print(ans % md)

main()

Submission status: Runtime Error

Solution code:
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)

# combinationの準備
# md>n_maxの条件
md = 10 ** 9 + 7
n_max = 100
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)]
    # i番目の壁まで無傷で来る方法の数
    # (全ルート)－(i-1までの壁にぶつかる分)
    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) for v, (pr, pc) in zip(dp[:i], rc[:i]))
    h, w = h - 1, w - 1
    ans = way(h, w) - sum(v * way(h - r, w - c) for v, (r, c) in zip(dp, rc))
    print(ans)

main()

Submission status: Runtime Error

Solution code:
import sys
h, w, n = [int(i) for i in sys.readline().split()]
m = 1000000007
fact = [1, 1]
for i in range(2, 200002):
    fact.append(fact[-1] * i)
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.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])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def modfact(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
    return fact,invfact

def resolve():
    h,w,n=map(int,input().split())
    R=[(1,1),(h,w)]+[tuple(map(int,input().split())) for _ in range(n)]
    R.sort()
    n+=1
    dp=[[0]*2 for _ in range(n+1)]
    dp[0][0]=1
    fact,invfact=modfact(2000)
    for i in range(n):
        x,y=R[i]
        for j in range(i+1,n+1):
            dx=R[j][0]-x
            dy=R[j][1]-y
            if(dx<0 or dy<0): continue
            for m in range(2):
                dp[j][1-m]+=dp[i][m]*fact[dx+dy]*invfact[dx]*invfact[dy]
                dp[j][1-m]%=MOD
    print(dp[n][1]-dp[n][0])
resolve()

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
a = [input() for _ in range(H)]

WARU = 10**9+7

dp = [[0]*(W+1) for _ in range(H+1)]

dp[0][0] = 1

for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            continue
        
        dp[i][j] %= WARU

        dp[i+1][j] += dp[i][j]
        dp[i][j+1] += dp[i][j]

print(dp[H-1][W-1])