Submission #3981441

Source Code Expand

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 Info

Submission Time
Task Y - Grid 2
User yaketake08
Language PyPy3 (2.4.0)
Score 100
Code Size 748 Byte
Status AC
Exec Time 1315 ms
Memory 49880 KiB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 22
Set Name Test Cases
All 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17
Case Name Status Exec Time Memory
0_00 AC 170 ms 38256 KiB
0_01 AC 169 ms 38256 KiB
0_02 AC 167 ms 38256 KiB
0_03 AC 335 ms 41840 KiB
1_00 AC 169 ms 38256 KiB
1_01 AC 177 ms 38256 KiB
1_02 AC 338 ms 41840 KiB
1_03 AC 337 ms 41840 KiB
1_04 AC 169 ms 38256 KiB
1_05 AC 374 ms 45784 KiB
1_06 AC 1039 ms 49368 KiB
1_07 AC 1057 ms 49368 KiB
1_08 AC 1315 ms 49368 KiB
1_09 AC 530 ms 48728 KiB
1_10 AC 1018 ms 49752 KiB
1_11 AC 985 ms 49752 KiB
1_12 AC 1025 ms 49752 KiB
1_13 AC 1027 ms 49880 KiB
1_14 AC 1021 ms 49624 KiB
1_15 AC 1014 ms 49880 KiB
1_16 AC 1014 ms 49496 KiB
1_17 AC 1015 ms 49880 KiB