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: Time Limit Exceeded

Solution code:
divisor = 10 ** 9 + 7
h, w, n = map(int, input().split())
a = [['.'] * w for _ in range(h)]
for _ in range(n):
  r, c = map(int, input().split())
  a[r - 1][c - 1] = '#'
for i in range(h):
  a[i] = ''.join(a[i])
dp = [[0] * w for _ in range(h)]
dp[0][0] = 1
dp0 = dp[0]
a0 = a[0]
for j in range(1, w):
  if a0[j] != '#':
    dp0[j] = dp0[j - 1]
for i in range(1, h):
  dpi = dp[i]
  dpi1 = dp[i - 1]
  ai = a[i]
  if ai[0] != '#':
    dpi[0] = dpi1[0]
  for j in range(1, w):
    if ai[j] != '#':
      dpi[j] = (dpi1[j] + dpi[j - 1]) % divisor
print(dp[h - 1][w - 1])

Submission status: Time Limit Exceeded

Solution code:
R, C, n = map(int, input().split())
s=set()
visited =[[0]*(C+2)]+[[0]+[1]*C+[0] for j in range(R)]+[[0]*(C+2)]
for i in range(n):
    y,x=map(int,input().split())
    visited[y][x]=0
INF=10**9+7
for i in range(1,R+1):
    for j in range(1,C+1):
        visited[i][j]*=(visited[i-1][j]+visited[i][j-1])%INF
        if i==1 and j==1:visited[1][1]=1
        if i==R and j==C:print((visited[i-1][j]+visited[i][j-1])%INF)

Submission status: Time Limit Exceeded

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):
        rese = (rese + count(k, i)*dpo[k]) % mod
        reso = (reso + count(k, i)*dpe[k]) % mod
    dpe[i] = rese
    dpo[i] = reso

print((dpo[-1] - dpe[-1]) % mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:

mod = pow(10,9)+7
h,w,n = list(map(int,input().split()))
dp = [[0 for i in range(w)] for j in range(h)]
arr = [ [0 for i in range(w)] for j in range(h)]

for i in range(n):
    r,c = list(map(int,input().split()))
    arr[r-1][c-1] = 1

for i in range(h):
    if(arr[i][0] == 1):
        break
    dp[i][0] = 1

for i in range(w):
    if(arr[0][i] == 1):
        break
    dp[0][i] = 1

for i in range(1,h):
    for j in range(1,w):
        if(arr[i-1][j] == 0):
            dp[i][j] += dp[i-1][j]
        if(arr[i][j-1] == 0):
            dp[i][j] += dp[i][j-1]

print(dp[h-1][w-1]%mod)

Submission status: Time Limit Exceeded

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


# combination---

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[i]:= i-1番目までの壁を通らず、i番目の壁にたどり着く経路の数
dp = [0] * n

for i in range(n):
    res = 0    # i-1までの壁を一回以上通って、i回目の壁にたどり着く経路数
    for j in range(i):
        # 最初にぶつかる壁がjで、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] = (i番目の壁までの経路数) - (i-1までの壁を一回以上通って、i回目の壁にたどり着く経路数)
    dp[i] = nck(wall[i][0] - 1 + wall[i][1] - 1, wall[i][0] - 1) - res
    dp[i] %= mod

# 余事象 ((h, w)までに少なくとも1つの壁にぶつかる経路数を数える)
ans = 0
for i in range(n):
    # 最初にぶつかる壁がiで、(h, w)に到達する経路数
    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)

Submission status: Time Limit Exceeded

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

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

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
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

######Factorization######
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

#####MakeDivisors######
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

#####MakePrimes######
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

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

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

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

#####ChangeBase#####
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]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

class Combination:
    def __init__(self, n_max, mod=10 ** 9 + 7):
        # O(n_max + log(mod))
        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()

    # "n 要素" は区別できる n 要素
    # "k グループ" はちょうど k グループ

    def __call__(self, n, r):  # self.C と同じ
        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

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

class Combination:
    def __init__(self, n_max, mod=10 ** 9 + 7):
        # O(n_max + log(mod))
        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()

    # "n 要素" は区別できる n 要素
    # "k グループ" はちょうど k グループ

    def __call__(self, n, r):  # self.C と同じ
        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)

    # 壁がない時(0,0)から(x,y)まで移動する場合の数: x+yCx
    # dp[i] =f(r[i]+c[i],c[i])−(i−1番目までの壁に1回以上ぶつかって壁iの位置にたどり着く場合の数)
    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]
            # dp[j]: 1～j-1 番目の壁を避けてj番目の壁の位置にたどり着く場合の数
            # nCr :  j 番目の壁の位置からi番目の壁の位置まで壁を無視して移動する場合の数
            tmp = dp[j] * cmb.nCr(dx + dy, dy)
            dp[i] = (dp[i] - tmp % MOD + MOD) % MOD

    print(dp[N])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
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 # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    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) # iに初めてぶつかり、ゴールまで移動する
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

MAX = 2*10**5+100
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
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)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
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()

Submission status: Accepted

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

class PERM_COMB_MOD():
    # http://drken1215.hatenablog.com/entry/2018/06/08/210000
    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)
# start地点
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    import sys
    from operator import itemgetter
    input = sys.stdin.readline

    mod = 1000000007
    # comb init
    nmax = 3 * 10 ** 5 + 1  # change here
    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()