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: Wrong Answer

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)]
graph2 = [[] for i in range(N+1)]

for i in range(N+1):
  y,x = wall[i]//W, wall[i]%W
  left = INF
  for j in range(i+1,N+1):
    ny,nx = wall[j]//W, wall[j]%W
    if nx<x or ny<y: continue
    if nx<left:
      graph[i].append(j)
      graph2[j].append(i)
      left = nx

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 graph2[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: Wrong Answer

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)]
graph2 = [[] for i in range(N+1)]

for i in range(N+1):
  y,x = wall[i]//W, wall[i]%W
  left = INF
  for j in range(i+1,N+1):
    ny,nx = wall[j]//W, wall[j]%W
    if nx<x or ny<y: continue
    if nx<left:
      graph[i].append(j)
      graph2[j].append(i)
      left = nx

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 graph2[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: Wrong Answer

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

    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, (r1, c1) in enumerate(rcs):
        v = getNum(r1-1, c1-1, MOD)
        for j, (r0, c0) in enumerate(rcs):
            if i == j or r0 > r1 or c0 > c1:
                continue
            dr, dc = r1-r0, c1-c0
            v -= getNum(dr, dc, MOD)
            v %= MOD
        dp[i] = 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: Wrong Answer

Solution code:
mod = 10**9+7

h,w,n = map(int,input().split())
dp = [[0]*(w+1) for _ in range(h+1)]
p = [[False]*(w+1) for _ in range(h+1)]
dp[1][1] = 1

for _ in range(n):
  r,c = map(int,input().split())
  p[r][c] = True
  
for i in range(1,h+1):
  for j in range(1,w+1):
    if not p[i][j]:
      dp[i][j] = (dp[i-1][j]+dp[i][j-1]) % mod
      
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
mod = 10**9+7

h,w,n = map(int,input().split())
dp = [[0]*(w+1) for _ in range(h+1)]
p = [[False]*(w+1) for _ in range(h+1)]
dp[1][1] = 1

for _ in range(n):
  r,w = map(int,input().split())
  p[r][w] = True
  
for i in range(1,h+1):
  for j in range(1,w+1):
    if not p[i][j]:
      dp[i][j] = (dp[i-1][j]+dp[i][j-1]) % mod
      
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
h,w,n = map(int,input().split())
dp = [[0]*(w+1) for _ in range(h+1)]
p = dp[:]
dp[1][1] = 1

for _ in range(n):
  r,w = map(int,input().split())
  p[r][w] = 1
  
for i in range(1,h+1):
  for j in range(1,w+1):
    if not p[i][j]:
      dp[i][j] = dp[i-1][j]+dp[i][j-1]
      
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
h,w,n = map(int,input().split())
dp = [[0]*(w+1) for _ in range(h+1)]
p = dp[:]

for _ in range(n):
  r,w = map(int,input().split())
  p[r][w] = 1
  
for i in range(h+1):
  for j in range(w+1):
    if not p[i][j]:
      dp[i][j] = dp[i-1][j]+dp[i][j-1]
      
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
#-----conbination計算部分------
#   https://qiita.com/derodero24/items/91b6468e66923a87f39f より

def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5*2
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#-------------------------------------------------------

#入力
H,W,N = map(int, input().split())
#迷路の初期化
#keystr = str(H).zfill(6)+str(W).zfill(6)
maplst = []
maplst.append([H,W,cmb(H+W-2,W-1)])
for i in range(N):
    x,y = map(int, input().split())
    keystr = str(x).zfill(6)+str(y).zfill(6)
    maplst.append([x,y,cmb(x+y-2,y-1)])

maplst.sort()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

    mod = 1000000007
    # comb init
    nmax = 2 * 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(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()

Submission status: Wrong Answer

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

Solution code:
from functools import reduce
from collections import defaultdict
import operator as op

dp = defaultdict(int)

def binomial_coeff(n, r):
    r = min(n-r,r)
    if r < 0: return 0
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer//denom

def DP(i, j):
    if (i,j) not in dp:
        dp[(i,j)] =  binomial_coeff(i+j-2, j-1)
    return dp[(i,j)]

n = raw_input()
n = n.split()
r = int(n[0])
c = int(n[1])
z = int(n[2])
#print(r,c,z)
MOD = 10**9+7

ans = DP(r,c)
obstacles = []
sum = 0
value = defaultdict(int)

for i in range(z):
    x = raw_input()
    x = x.split()
    j = int(x[0])
    k = int(x[1])
    obstacles.append((j, k))

obstacles.sort()

for i,j in obstacles:
    value[(i,j)] = DP(i,j)

for i,j in obstacles:
    others_affect = 0
    for p,q in obstacles:
        if i >= p and j >= q and not (i==p and j==q) :
            others_affect = (others_affect + ((DP(i-p+1, j-q+1)%MOD) * (value[(p,q)]%MOD)) % MOD) % MOD
    value[(i,j)] = (value[(i,j)] - others_affect + MOD) % MOD
    sum = (sum + (DP(r-i+1, c-j+1)%MOD * value[(i,j)])%MOD)%MOD

ans = ans - sum + MOD
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from collections import defaultdict
import operator as op

dp = defaultdict(int)

def binomial_coeff(n, r):
    r = min(n-r,r)
    if r < 0: return 0
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer//denom

def DP(i, j):
    if (i,j) not in dp:
        dp[(i,j)] =  binomial_coeff(i+j-2, j-1)
    return dp[(i,j)]

n = input().split()
r = int(n[0])
c = int(n[1])
z = int(n[2])

MOD = 10**9+7

ans = DP(r,c)
obstacles = []
sum = 0
value = defaultdict(int)

for i in range(z):
    x = input().split()
    j = int(x[0])
    k = int(x[1])
    obstacles.append((j, k))

obstacles.sort()

for i,j in obstacles:
    value[(i,j)] = DP(i,j)

for i,j in obstacles:
    others_affect = 0
    for p,q in obstacles:
        if i >= p and j >= q and not (i==p and j==q) :
            others_affect = (others_affect + ((DP(i-p+1, j-q+1)%MOD) * (value[(p,q)]%MOD)) % MOD) % MOD
    value[(i,j)] = (value[(i,j)] - others_affect + MOD) % MOD
    sum = (sum + (DP(r-i+1, c-j+1)%MOD * value[(i,j)])%MOD)%MOD

ans = ans - sum + MOD
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from collections import defaultdict
import operator as op

def binomial_coeff(n, r):
    r = min(n-r,r)
    if r < 0: return 0
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer//denom

def dp(i, j):
    return binomial_coeff(i+j-2, j-1)

n = input().split()
r = int(n[0])
c = int(n[1])
z = int(n[2])

MOD = 10**9+7

ans = dp(r,c)
obstacles = []
sum = 0
value = defaultdict(int)

for i in range(z):
    x = input().split()
    j = int(x[0])
    k = int(x[1])
    obstacles.append((j, k))

obstacles.sort()

for i,j in obstacles:
    value[(i,j)] = dp(i,j)
for i,j in obstacles:
    others_affect = 0
    for p,q in obstacles:
        if i >= p and j >= q and not (i==p and j==q) :
            others_affect += (dp(i-p+1, j-q+1) * value[(p,q)])
    value[(i,j)] -= others_affect
    sum += (dp(r-i+1, c-j+1) * value[(i,j)])

ans -= sum
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
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):
        # start->i
        edge[0].append((i, comb(x1+y1-2, x1-1)))
        indeg[i] += 1
        # i->goal
        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()

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

h,w,n = map(int,input().split())
dp = [[0]*(w+1) for _ in range(h+1)]
p = [[False]*(w+1) for _ in range(h+1)]
dp[1][1] = 1

for _ in range(n):
  r,c = map(int,input().split())
  p[r][c] = True
  
for i in range(1,h+1):
  for j in range(1,w+1):
    if not p[i][j]:
      dp[i][j] += (dp[i-1][j]+dp[i][j-1]) % mod
      
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Feb 13 19:37:57 2020

@author: matsui
"""

H,W,N=map(int,input().split())
H-=1
W-=1

mod=1000000007

K=[1,1]
Kinv=[1,1]
inv=[1,1]

for i in range(2,H+W+1):
    K.append(K[i-1]*(i)%mod)
    inv.append(mod-inv[int(mod%i)]*(mod//i)%mod)
    Kinv.append(Kinv[-1]*inv[-1]%mod)

def co(r1,c1,r2,c2):
    return K[r2+c2-(r1+c1)]*(Kinv[r2-r1]*Kinv[c2-c1]%mod)%mod

ans=co(0,0,H,W)
#ans=K[H+W]*(Kinv[H]*Kinv[W]%mod)%mod
R,C=[],[]
for i in range(N):
    r,c=map(int,input().split())
    r-=1
    c-=1
    B=co(0,0,r,c)
    A=co(r,c,H,W)
    ans-=B*A%mod
    if ans<0: ans+=mod
    for ri,ci in zip(R,C):
        if r>=ri and c>=ci:
            ans+=co(0,0,ri,ci)*co(ri,ci,r,c)*co(r,c,H,W)
            #ans+=K[r+c-(ri+ci)]*(Kinv[r-ri]*Kinv[c-ci]%mod)%mod
        if r<=ri and c<=ci:
            ans+=co(0,0,r,c)*co(r,c,ri,ci)*co(ri,ci,H,W)
            #ans+=K[ri+ci-(r+c)]*(Kinv[ri-r]*Kinv[ci-c]%mod)%mod
    R.append(r)
    C.append(c)
    ans%=mod
    #print(B,A,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Feb 13 19:37:57 2020

@author: matsui
"""

H,W,N=map(int,input().split())
H-=1
W-=1

mod=1000000007

K=[1,1]
Kinv=[1,1]
inv=[1,1]

for i in range(2,H+W+1):
    K.append(K[i-1]*(i)%mod)
    inv.append(mod-inv[int(mod%i)]*(mod//i)%mod)
    Kinv.append(Kinv[-1]*inv[-1]%mod)


ans=K[H+W]*(Kinv[H]*Kinv[W]%mod)%mod
R,C=[],[]
for i in range(N):
    r,c=map(int,input().split())
    r-=1
    c-=1
    B=K[r+c]*(Kinv[r]*Kinv[c]%mod)%mod
    A=K[H+W-(r+c)]*(Kinv[H-r]*Kinv[W-c]%mod)%mod
    ans-=B*A%mod
    if ans<0: ans+=mod
    for ri,ci in zip(R,C):
        if r>=ri and c>=ci:
            ans+=K[r+c-(ri+ci)]*(Kinv[r-ri]*Kinv[c-ci]%mod)%mod
        if r<=ri and c<=ci:
            ans+=K[ri+ci-(r+c)]*(Kinv[ri-r]*Kinv[ci-c]%mod)%mod
    R.append(r)
    C.append(c)
    ans%=mod
    #print(B,A,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#-----combination計算部分------
def cmb(n, r):
    #if ( r<0 or r>n ):
    #    return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5*2
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#入力
H,W,N = map(int, input().split())
#迷路の初期化
maplst = []
for i in range(N):
    x,y = map(int, input().split())
    maplst.append([x,y,cmb(x+y-2,y-1)]) #壁を追加
maplst.sort()
maplst.append([H,W,cmb(H+W-2,W-1)]) #ゴールを最後に追加

#壁の分を減算
for i in range(N):
    x1,y1,v1 = maplst[i]
    for j in range(i+1,N+1):
        x2,y2,v2 = maplst[j]
        if y1 <= y2:
            #dx = x2 - x1 + 1
            #dy = y2 - y1 + 1
            #dv = v1 * cmb(dx+dy-2,dy-1)
            #maplst[j][2] = v2-dv
            maplst[j][2] = v2 - v1 * cmb(x2-x1+y2-y1,y2-y1)

print(maplst[-1][2] % mod)

Submission status: Time Limit Exceeded

Solution code:
#-----conbination計算部分------
def cmb(n, r):
    #if ( r<0 or r>n ):
    #    return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5*2
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#入力
H,W,N = map(int, input().split())

#迷路の初期化
maplst = [[0]*2 for i in range(N)]
for i in range(N-1,-1,-1):
    maplst[i][0],maplst[i][1] = map(int, input().split())
maplst.sort()
maplst.append([H,W])

dp = [0] * (N+1)
for i in range(N+1):
    x,y = maplst[i]
    dp[i] = cmb(x+y-2,y-1)

#壁の分を減算
for i in range(N):
    x1,y1 = maplst[i]
    for j in range(i+1,N+1):
        x2,y2 = maplst[j]
        if y1 <= y2:
            #dx = x2 - x1 + 1
            #dy = y2 - y1 + 1
            #dv = v1 * cmb(dx+dy-2,dy-1)
            #maplst[j][2] = v2-dv
            dp[j] = dp[j] - dp[i] * cmb(x2-x1+y2-y1,y2-y1)

print(dp[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
#-----conbination計算部分------
def cmb(n, r):
    #if ( r<0 or r>n ):
    #    return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5*2
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#入力
H,W,N = map(int, input().split())

#迷路の初期化
maplst = [[0]*2 for i in range(N)]
for i in range(N):
    maplst[i][0],maplst[i][1] = map(int, input().split())
maplst.sort()
maplst.append([H,W])

dp = [0] * (N+1)
for i in range(N+1):
    x,y = maplst[i]
    dp[i] = cmb(x+y-2,y-1)

#壁の分を減算
for i in range(N):
    x1,y1 = maplst[i]
    for j in range(i+1,N+1):
        x2,y2 = maplst[j]
        if y1 <= y2:
            #dx = x2 - x1 + 1
            #dy = y2 - y1 + 1
            #dv = v1 * cmb(dx+dy-2,dy-1)
            #maplst[j][2] = v2-dv
            dp[j] = dp[j] - dp[i] * cmb(x2-x1+y2-y1,y2-y1)

print(dp[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
#-----conbination計算部分------
def cmb(n, r):
    #if ( r<0 or r>n ):
    #    return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5*2
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#入力
H,W,N = map(int, input().split())

#迷路の初期化
maplst = []
for i in range(N):
    x,y = map(int, input().split())
    maplst.append([x,y])
maplst.sort()
maplst.append([H,W])

dp = []
for x,y in maplst:
    dp.append(cmb(x+y-2,y-1))

#壁の分を減算
for i in range(N):
    x1,y1 = maplst[i]
    for j in range(i+1,N+1):
        x2,y2 = maplst[j]
        if y1 <= y2:
            #dx = x2 - x1 + 1
            #dy = y2 - y1 + 1
            #dv = v1 * cmb(dx+dy-2,dy-1)
            #maplst[j][2] = v2-dv
            dp[j] = dp[j] - dp[i] * cmb(x2-x1+y2-y1,y2-y1)

print(dp[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
#-----conbination計算部分------
def cmb(n, r):
    #if ( r<0 or r>n ):
    #    return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5*2
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#入力
H,W,N = map(int, input().split())

#迷路の初期化
maplst = []
for i in range(N):
    x,y = map(int, input().split())
    maplst.append([x,y])
maplst.sort()
maplst.append([H,W])

dp = [0] * len(maplst)
for i in range(len(maplst)):
    x,y = maplst[i]
    dp[i] = cmb(x+y-2,y-1)

#壁の分を減算
for i in range(N):
    x1,y1 = maplst[i]
    for j in range(i+1,N+1):
        x2,y2 = maplst[j]
        if y1 <= y2:
            #dx = x2 - x1 + 1
            #dy = y2 - y1 + 1
            #dv = v1 * cmb(dx+dy-2,dy-1)
            #maplst[j][2] = v2-dv
            dp[j] = dp[j] - dp[i] * cmb(x2-x1+y2-y1,y2-y1)

print(dp[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
#-----conbination計算部分------
def cmb(n, r):
    #if ( r<0 or r>n ):
    #    return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5*2
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#入力
W,H,N = map(int, input().split())
#迷路の初期化
maplst = []
for i in range(N):
    y,x = map(int, input().split())
    maplst.append([x,y,cmb(x+y-2,y-1)])
maplst.append([H,W,cmb(H+W-2,W-1)])
maplst.sort()

#壁の分を減算
for i in range(len(maplst)-1):
    x1,y1,v1 = maplst[i]
    for j in range(i+1,len(maplst)):
        x2,y2,v2 = maplst[j]
        if y1 <= y2:
            #dx = x2 - x1 + 1
            #dy = y2 - y1 + 1
            #dv = v1 * cmb(dx+dy-2,dy-1)
            #maplst[j][2] = v2-dv
            maplst[j][2] = v2 - v1 * cmb(x2-x1+y2-y1,y2-y1)

print(maplst[-1][2] % mod)