提出 #4899562

---

ソースコード 拡げる

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime,random
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

H,W,K = inpl()
XYs = [inpl() for _ in range(K)]
XYs.sort()

MAX = H+W
fac = [1]*(MAX+1)
for i in range(1,MAX+1):
	fac[i] = (fac[i-1]*i)%mod

gyakugen = [1]*(MAX+1)
gyakugen[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
	gyakugen[i-1] = (gyakugen[i]*i)%mod

def Comb (n,k):#nCk
	return (fac[n]*gyakugen[k]*gyakugen[n-k])%mod

def calc(xys,xyt):
    dx = xyt[0] - xys[0]
    dy = xyt[1] - xys[1]
    return Comb(dx+dy,dx)

def LU(xy):
    x,y = xy
    return([x,y+1])

def RD(xy):
    x,y = xy
    return([x+1,y])

tmp0 = calc([1,1],LU(XYs[0]))
tmp1 = calc([1,1],RD(XYs[0]))
for i in range(1,K):
    tmp0ed,tmp1ed = tmp0,tmp1
    tmp0 = tmp0ed * calc(LU(XYs[i-1]),LU(XYs[i])) + tmp1ed * calc(RD(XYs[i-1]),LU(XYs[i]))
    tmp1 = tmp0ed * calc(LU(XYs[i-1]),RD(XYs[i])) + tmp1ed * calc(RD(XYs[i-1]),RD(XYs[i]))
    tmp0 %= mod
    tmp1 %= mod

ans = tmp0 * calc(LU(XYs[K-1]),[W,H]) + tmp1 * calc(RD(XYs[K-1]),[W,H])
print(ans%mod)

提出情報

ジャッジ結果