Problem p02782 (python)

Fixed submission:
import sys
read = sys.stdin.read
mod = 10 ** 9 + 7
r1, c1, r2, c2 = map(int, read().split())

def prepare(n, MOD):

    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


fac, finv = prepare(2 * 10**6 + 10, mod)


def comb(n, k, mod=mod, fac=fac, finv=finv):
    '''
    二項係数の計算

    Parameters
    n : int
        元集合
    k : int
        元集合から選択する数
    mod : int
        あまり
    fac : list
        階乗のリスト
    finv : list
        逆元のリスト

    Returns
    c : int
        nCkの組み合わせの数
    '''
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


answer = comb(r2 + c2 + 2, r2 + 1) - comb(r1 + c2 + 1, r1) - \
    comb(c1 + r2 + 1, c1) + comb(r1 + c1, r1)
answer %= mod
print(answer)

Buggy submission (verdict: Runtime Error):
import sys
from itertools import product
from collections import defaultdict
read = sys.stdin.read
sys.setrecursionlimit(1000000)

r1, c1, r2, c2 = map(int, read().split())
mod = 10 ** 9 + 7
dic = defaultdict(lambda: 1)


def count(r, c):
    if r * c == 0:
        return 1
    if (r - 1, c) in dic:
        a = dic[(r - 1, c)]
    else:
        a = dic[(r - 1, c)] = count(r - 1, c) % mod
    if (r, c - 1) in dic:
        b = dic[(r, c - 1)]
    else:
        b = dic[(r, c - 1)] = count(r, c - 1) % mod
    return (a + b) % mod


dic[(r1 - 1, c2)] = count(r1 - 1, c2)
dic[(r2, c1 - 1)] = count(r2, c1 - 1)
res = 0
for r, c in product(range(r1, r2 + 1), range(c1, c2 + 1)):
    tmp = dic[(r, c)] = dic[(r - 1, c)] + dic[(r, c - 1)]
    res += tmp % mod
print(res % mod)

Buggy submission (verdict: Runtime Error):
import sys
from itertools import product
from collections import defaultdict
read = sys.stdin.read
sys.setrecursionlimit(1000000)

r1, c1, r2, c2 = map(int, read().split())
mod = 10 ** 9 + 7
dic = {}


def count(r, c):
    if r * c == 0:
        return 1
    if (r - 1, c) in dic:
        a = dic[(r - 1, c)]
    else:
        a = dic[(r - 1, c)] = count(r - 1, c) % mod
    if (r, c - 1) in dic:
        b = dic[(r, c - 1)]
    else:
        b = dic[(r, c - 1)] = count(r, c - 1) % mod
    return (a + b) % mod


dic[(r1 - 1, c2)] = count(r1 - 1, c2)
dic[(r2, c1 - 1)] = count(r2, c1 - 1)
res = 0
for r, c in product(range(r1, r2 + 1), range(c1, c2 + 1)):
    tmp = dic[(r, c)] = dic[(r - 1, c)] + dic[(r, c - 1)]
    res += tmp % mod
print(res % mod)

Buggy submission (verdict: Runtime Error):
import sys
from itertools import product
read = sys.stdin.read
sys.setrecursionlimit(1000000)

r1, c1, r2, c2 = map(int, read().split())
mod = 10 ** 9 + 7
dic = {}


def count(r, c):
    if r * c == 0:
        return 1
    if (r - 1, c) in dic:
        a = dic[(r - 1, c)]
    else:
        a = dic[(r - 1, c)] = count(r - 1, c) % mod
    if (r, c - 1) in dic:
        b = dic[(r, c - 1)]
    else:
        b = dic[(r, c - 1)] = count(r, c - 1) % mod
    return (a + b) % mod


dic[(r1 - 1, c2)] = count(r1 - 1, c2)
dic[(r2, c1 - 1)] = count(r2, c1 - 1)
res = 0
for r, c in product(range(r1, r2 + 1), range(c1, c2 + 1)):
    tmp = dic[(r, c)] = dic[(r - 1, c)] + dic[(r, c - 1)]
    res += tmp % mod
print(res % mod)