Problem:


Score : 600 points

Problem Statement

Snuke is standing on a two-dimensional plane. In one operation, he can move by 1 in the positive x-direction, or move by 1 in the positive y-direction.

Let us define a function f(r, c) as follows:

f(r,c) :=  (The number of paths from the point (0, 0) to the point (r, c) that Snuke can trace by repeating the operation above)

Given are integers r_1, r_2, c_1, and c_2.
Find the sum of f(i, j) over all pair of integers (i, j) such that r_1 ≤ i ≤ r_2 and c_1 ≤ j ≤ c_2, and compute this value modulo (10^9+7).

Constraints

1 ≤ r_1 ≤ r_2 ≤ 10^6

1 ≤ c_1 ≤ c_2 ≤ 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

r_1 c_1 r_2 c_2

Output

Print the sum of f(i, j) modulo (10^9+7).

Sample Input 1

1 1 2 2

Sample Output 1

14

For example, there are two paths from the point (0, 0) to the point (1, 1): (0,0) → (0,1) → (1,1) and (0,0) → (1,0) → (1,1), so f(1,1)=2.

Similarly, f(1,2)=3, f(2,1)=3, and f(2,2)=6. Thus, the sum is 14.

Sample Input 2

314 159 2653 589

Sample Output 2

602215194



Sample input:
1 1 2 2


Sample output:
14

Submission status: Wrong Answer

Solution code:
r1, c1, r2, c2 = map(int, input().split())
mod = 10**9+7

def np(m, n):
    count = [[0 for _ in range(m)] for _ in range(n)] 
    #print(count)

    for i in range(n): 
        count[i][0] = 1

    for j in range(m): 
        count[0][j] = 1
    
    for i in range(1, n): 
        for j in range(m):      
            count[i][j] = (count[i-1][j] + count[i][j-1])
    #print(count)
 
    return (count[n-1][m-1])%mod

print(np(r1+1, c1+1) + np(r1+1, c2+1) + np(r2+1, c1+1) + np(r2+1, c2+1))

Submission status: Wrong Answer

Solution code:
r1,c1,r2,c2 = map(int,input().split())
MOD = 10**9 + 7
MAX = 2 * (10**6) + 1

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]
fac[0] = 1
fac[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1

for i in range(2, MAX):
	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 com(n,k):
	if n < k:
		return 0
	if n < 0 or k < 0:
		return 0
	return fac[n] * (finv[k] * finv[n-k] % MOD)

ans = com(r1+c1, r1)
if r1 == r2 or c1 == c2:
	if r1 != r2:
		for r in range(r1+1, r2+1):
			ans = (ans + com(r+c1, r)) % MOD
	if c1 != c2:
		for c in range(c1+1, c2+1):
			ans = (ans + com(r1+c, r1)) % MOD
	print(ans)
	exit()

diff_c = c2 - c1
keisu = [com(diff_c+i, i+1) for i in range(r2 - r1)]
t_keisu = [0]
for k in keisu:
	t_keisu.append((t_keisu[-1] + k) % MOD)
for r in range(r1+1, r2+1):
	tmp = com(r+c1, r)
	ans = (ans + tmp + tmp * t_keisu[r1 - r]) % MOD

diff_r = r2 - r1
keisu = [com(diff_r+i, i+1) for i in range(c2 - c1)]
t_keisu = [0]
for k in keisu:
	t_keisu.append((t_keisu[-1] + k) % MOD)
for c in range(c1 + 1, c2 + 1):
	tmp = com(r1+c, c)
	ans = (ans + tmp + tmp * t_keisu[c1 - c]) % MOD

print(ans)

Submission status: Wrong Answer

Solution code:
r1,c1,r2,c2=map(int,input().split())
a=r2-r1+1
b=c2-c1+1
m=max(a,b)
n=min(a,b)
mod=10**9+7
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a
def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod
ans=0
c=m+n-1
if c%2==0:
    for i in range(0,c//2):
        ans+=(comb(r1+c1+i, r1, mod)+comb(r2+c2-i, r2, mod))*(i+1)
        ans%=mod
else:
    for i in range(0,c//2):
        ans+=(comb(r1+c1+i, r1, mod)+comb(r2+c2-i, r2, mod))*(i+1)
        ans%=mod
    ans+=comb(r1+c1+(c//2), r1, mod)*(n)
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
Q = 10**9+7
def getInv(N):#Qはmod
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

# def getFactorialInv(N):
#     inv = [0] * (N + 1)
#     inv[0] = 1
#     inv[1] = 1
#     ret = [1]*(N+1)
#     for i in range(2, N + 1):
#         inv[i] = (-(Q // i) * inv[Q%i]) % Q
#         ret[i] = ret[i-1]*inv[i]
#     return ret

def getFactorial(N):
    ret = [1]*(N+1)
    for i in range(2,N+1):
        ret[i] = ret[i-1]*i%Q
    return ret

def main():
    r1, c1, r2, c2 = map( int, input().split())
    F = getFactorial(2*(10**6))
    J = getInv(2*(10**6))
    I = [0]*(2*(10**6)+1)
    I[0] = 1
    I[1] = 1
    for i in range(2,2*(10**6)+1):
        I[i] = I[i-1]*J[i]%Q
    #print(F[5]*I[5]%Q)
    a = 0
    b = 0
    c = 0
    d = 0
    for i in range(1, c2+1):
        a += F[r2+i+1]*I[i+1]%Q*I[r2]%Q-1
#        print(F[r2+i+1]*I[i+1]%Q*I[r2]%Q-1)
        a %= Q
    if r1 == 1:
        b = 0
    else:
        for i in range(1, c2):
            b += F[r1+i]*I[i]%Q*I[r1]%Q-1
            b %= Q
    if c1 == 1:
        c = 0
    else:
        for i in range(1, c1):
            c += F[r2+i]*I[i]%Q*I[r2]%Q-1
            c %= Q
    if c1 == 1 or r1 == 1:
        d = 0
    else:
        for i in range(1, c1):
            d += F[r1+i]*I[i]%Q*I[r1]%Q-1
            d %= Q
#    print(a, b,c, d)
    print((a-b-c+d)%Q)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
r1,c1,r2,c2=map(int,input().split())
a=r2-r1+1
b=c2-c1+1
m=max(a,b)
n=min(a,b)
mod=10**9+7
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a
def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod
ans=0
c=m+n-1
if c%2==0:
    for i in range(0,c//2):
        ans+=(comb(r1+c1+i, r1, mod)+comb(r2+c2-i, r2, mod))*(i+1)
        ans%=mod
        print(ans)
else:
    for i in range(0,c//2):
        ans+=(comb(r1+c1+i, r1, mod)+comb(r2+c2-i, r2, mod))*(i+1)
        ans%=mod
        print(ans)
    ans+=comb(r1+c1+(c//2), r1, mod)*(n)
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
def xxx(X, Y):
    z = 1
    for x in range(X, Y + 1):
        z *= x
    return z


def main():
    r1, c1, r2, c2 = map(int, input().split(' '))
    x, y = r2 - r1, c2 - c1
    
    print((xxx(1, x + y) // (xxx(1, x) * xxx(1, y)) + xxx(1, r2 + c2) // (xxx(1, r2) * xxx(1, c2)) * 2))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

MOD = 1000000007

class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def permutation(n, x):
    print(n, x)
    # nPx
    # 順列
    # ex) permutaion(5, 2) = 20
    tmp = 1
    for i in range(n, n-x, -1):
        tmp = (tmp * i) % MOD
    return ModInt(tmp)

@lru_cache(maxsize=None)
def factorial(x):
    # x!
    # 階乗
    # ex) factorial(5) = 120
    tmp = 1
    for i in range(1, x+1):
        tmp = (tmp * i) % MOD
    return ModInt(tmp)


r1, c1, r2, c2 = map(int, input().split(" "))


print(sum(
    [
        factorial(i + j) / (factorial(i) * factorial(j))
        for i in range(r1, r2 + 1)
        for j in range(c1, c2 + 1)
        if i > j
    ]
))

Submission status: Wrong Answer

Solution code:
r1,c1,r2,c2 = map(int,input().split())

# 二項係数 mod P

mod = 10**9+7

m = r2+c2 +10 
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod


def g(r,c):
    ret = 0
    for i in range(0,r+1):
        ret += comb(i+c+1,i+1)
        ret %= mod
    return ret

ans = g(r2,c2) - g(r1-1,c2) - g(r2,c1-1) + g(r1-1,c1-1)
print(ans)

Submission status: Wrong Answer

Solution code:
inputf = input

def factorial(n):
    res = 1
    for i in range(1, n+1):
        res *= i
    return res

r1, c1, r2, c2 = [int(x) for x in inputf().split()]

res_mat1 = [0]*(r2-r1+1)
res_mat2 = [0]*(r2-r1+1)

res_mat1[0] = factorial(r1+c1)//(factorial(r1)*factorial(c1))

for i in range(1, r2-r1+1):
    res_mat1[i] = res_mat1[i-1]*(c1+(r1+i))//(r1+i)

res_sum = sum(res_mat1)
res_sum = res_sum%(int(10e9) + 7)
#print(res_mat1)

for i in range(1, c2-c1+1):
    c = c1+i
    if i%2==1:
        for j, num in enumerate(res_mat1):
            res_mat2[j] = num*(c+(r1+j))//c
        #print(i, res_mat2)
        res_sum += sum(res_mat2)
    else:
        for j, num in enumerate(res_mat2):
            res_mat1[j] = num*(c+(r1+j))//c
        res_sum += sum(res_mat1)
        #print(i, res_mat1)
    res_sum = res_sum%(int(10e9) + 7)
print(res_sum)

Submission status: Wrong Answer

Solution code:
bikkuri = [1]
mod = 10**9+7

for i in range(1,2*10**6+1000):
    bikkuri.append((bikkuri[-1]*i)%mod)
r1,c1,r2,c2 = map(int,input().split())

def F(r,c):
    tmp = (bikkuri[r+c+2]*pow(bikkuri[c+1],mod-2,mod)*pow(bikkuri[r+1],mod-2,mod) - 1)%mod
    return tmp

ans = F(r2,c2)-F(r1-1,c2)-F(r2,c1-1)+F(r1-1,c1-1)
print(ans)

Submission status: Wrong Answer

Solution code:
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
n_max=2*(10**6+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

def f(x,y):
  return comb(x+y+2,y+1)-1

print(f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))

Submission status: Wrong Answer

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

    mod = 1000000007
    r1, c1, r2, c2 = map(int, input().split())

    # comb init
    nmax = 2 * 10 ** 6 + 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

    def f(r, c):
        ret = 0
        for i in range(r+1):
            ret = (ret + comb(i+1+c, c))%mod
        return ret

    print((f(r2, c2) - f(r2, c1-1) - f(c2, r1-1) + f(r1-1, c1-1))%mod)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

r1,c1,r2,c2 = list(map(int, input().split()))
S = 0

def seki(k):
    c = 1
    for i in range(1,k+1):
        c *= i
    return c
def keiro(r,c):
    return (seki(r+c)%100000007/(seki(r)*seki(c)))

for i in range(r2-r1+1):
    for j in range(c2-c1+1):
        S += keiro(r1+i,c1+j)

print(S)

Submission status: Wrong Answer

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

    mod = 1000000007
    r1, c1, r2, c2 = map(int, input().split())

    # comb init
    nmax = 2 * 10 ** 6 + 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

    def f(r, c):
        ret = 0
        for i in range(r+1):
            ret = (ret + comb(i+1+c, c))%mod
        return ret

    print(((f(r2, c2) - f(r2, c1-1))%mod - (f(c2, r1-1) - f(r1-1, c1-1))%mod)%mod)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    mod = 1000000007
    r1, c1, r2, c2 = map(int, input().split())

    # comb init
    nmax = 2 * 10 ** 6 + 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

    def f(r, c):
        ret = 0
        for i in range(r+1):
            ret = (ret + comb(i+1+c, c))%mod
        return ret
    ans = 0
    print(((f(r2, c2) - f(r2, c1-1))%mod - (f(r1-1, c2) - f(r1-1, c1-1))%mod)%mod)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
x,y,X,Y = map(int,input().split())
u = math.factorial(x+y) % (10**9 + 7)
d = (math.factorial(x)*math.factorial(y)) % (10**9 + 7)
K = u/d
keisu = 0
for i in range(X-x+1):
    for j in range(Y-y+1):
        u = (math.factorial(i+j) % (10**9 + 7))
        d = (math.factorial(i) % (10**9 + 7))*(math.factorial(j) % (10**9 + 7))
        keisu += u/d
ans = ((K +1)* keisu - 1) % (10**9 + 7)
print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
MAX = (10 ** 6) * 2 + 1
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

def CoMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        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 COM(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

r1, c1, r2, c2 = map(int, input().split())
CoMinit()

ans = 0
ans += COM(r1 + c1, c1)
ans += COM(r1 + c2, c2)
ans += COM(r2 + c1, c1)
ans += COM(r2 + c2, c2)

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7  # 出力の制限

r1, c1, r2, c2 = list(map(int, input().split()))


# https://qiita.cmb/derodero24/items/91b6468e66923a87f39f
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


N = 2 * 10**6 + 10**5
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)

print(cmb(c1 + r1, r1) - cmb(1 + c2 + r1, r1) -
      cmb(1 + c1 + r2, 1 + r2) + cmb(2 + c2 + r2, 1 + r2))

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7  # 出力の制限

r1, c1, r2, c2 = list(map(int, input().split()))


# https://qiita.cmb/derodero24/items/91b6468e66923a87f39f
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


N = 2 * 10**6 + 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)

print(cmb(c1 + r1, r1) - cmb(1 + c2 + r1, r1) -
      cmb(1 + c1 + r2, 1 + r2) + cmb(2 + c2 + r2, 1 + r2))

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7
def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;finv[1]=1;inv[1]=1
    for i in range(2,N+1):
        fac[i]=fac[i-1]*i%MOD
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i]=finv[i-1]*inv[i]%MOD
    return fac,finv,inv

def COM(n,r):
    if n<r or r<0:
        return 0
    else:
        return ((fac[n]*finv[r])%MOD*finv[n-r])%MOD
        
r1,c1,r2,c2=map(int,input().split())

fac,finv,inv=facinv(r2+c2+1)

ans=0

for i in range(r1,r2+1):
    ans=(ans+COM(c2+i+1,i+1)-COM(c1+i,i+1)+MOD)%MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
r1, c1, r2, c2 = map(int, input().split())
fa = [1] * (r2 + c2 + 3)
fi = [1] * (r2 + c2 + 3)
for i in range(1, r2 + c2 + 3):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
def ans(r, c):
    return fa[r + c + 2] * fi[r + 1] * fi[c + 1] % mod - 1
print((ans(r2, c2) - ans(r2, c1 - 1) - ans(r1 - 1, c2) + ans(r1 - 1, c1 - 1)) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce
from operator import mul
from typing import Callable, ClassVar, Sequence, Type, TypeVar



T = TypeVar('T', bound='ModIntBase')


class ModIntBase:
    value: int
    mod: ClassVar[int]
    fac: ClassVar[Sequence[int]] = ()
    inv: ClassVar[Sequence[int]] = ()
    finv: ClassVar[Sequence[int]] = ()

    def __init__(self, value: int) -> None:
        self.value = value % self.mod

    def __hash__(self) -> int:
        return hash((self.value, self.mod))

    def __eq__(self, other) -> bool:
        if isinstance(other, self.__class__):
            return self.value == other.value
        else:
            return NotImplemented

    def __ne__(self, other) -> bool:
        if isinstance(other, self.__class__):
            return self.value != other.value
        else:
            return NotImplemented

    # TODO: Add type hints
    def __add__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__((self.value + other.value) % self.mod)
        else:
            return NotImplemented

    def __sub__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__((self.value - other.value) % self.mod)
        else:
            return NotImplemented

    def __mul__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__(self.value * other.value % self.mod)
        else:
            return NotImplemented

    def __truediv__(self, other):
        if isinstance(other, self.__class__):
            a = other.value
            b = self.mod
            u = 1
            v = 0
            while b:
                t = a // b
                a, b = b, a - t * b
                u, v = v, u - t * v
            return self.__class__(self.value * u % self.mod)
        else:
            return NotImplemented

    def __pow__(self, other):
        if isinstance(other, self.__class__):
            v = 1
            a = self.value
            b = other.value
            mod = self.mod
            while b > 0:
                if b & 1:
                    v = v * a % mod
                a = a * a % mod
                b >>= 1
            return self.__class__(v)
        else:
            return NotImplemented

    @classmethod
    def comb(cls, n: int, k: int):
        if n < k:
            return cls(0)
        if n < 0 or k < 0:
            return cls(0)

        if n < len(cls.fac):
            return cls(cls.fac[n] * (cls.finv[k] * cls.finv[n - k] % cls.mod) % cls.mod)
        else:
            k = min(k, n - k)
            a = reduce(mul, map(cls, range(n - k + 1, n + 1)), cls(1))
            b = reduce(mul, map(cls, range(1, k + 1)), cls(1))
            return a / b

    def __repr__(self) -> str:
        return f'{self.__class__.__name__}({self.value!r})'

    def __str__(self) -> str:
        return str(self.value)


def mod_comb_init(max_: int) -> Callable[[Type[T]], Type[T]]:
    def _mod_comb_init(cls: Type[T]) -> Type[T]:
        mod: int = cls.mod
        assert max_ < mod

        fac = cls.fac = [0] * max_
        finv = cls.finv = [0] * max_
        inv = cls.inv = [0] * max_

        fac[0] = fac[1] = 1
        finv[0] = finv[1] = 1
        inv[1] = 1
        for i in range(2, max_):
            fac[i] = fac[i - 1] * i % mod
            inv[i] = mod - inv[mod % i] * (mod // i) % mod
            finv[i] = finv[i - 1] * inv[i] % mod

        return cls
    return _mod_comb_init


@mod_comb_init(2 * 10 ** 6 + 1)
class ModInt(ModIntBase):
    mod = 1000000007  # 10 ** 9 + 7


def resolve(in_):
    r1, c1, r2, c2 = map(int, next(in_).strip().split())
    # ans = f(r2+1, c2+1) - f(r2+1, c1) - f(r1, c2+1) + f(r1, c1)
    ans = (
        ModInt.comb((r2 + 1) + (c2 + 1), c2 + 1)
        - ModInt.comb((r2 + 1) + c1, c1)
        - ModInt.comb(r1 + (c2 + 1), c2 + 1)
        + ModInt.comb(r1 + c1, c1)
    )

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce
from operator import mul
from typing import Callable, ClassVar, Sequence, Type, TypeVar



T = TypeVar('T', bound='ModIntBase')


class ModIntBase:
    value: int
    mod: ClassVar[int]
    fac: ClassVar[Sequence[int]] = ()
    inv: ClassVar[Sequence[int]] = ()
    finv: ClassVar[Sequence[int]] = ()

    def __init__(self, value: int) -> None:
        self.value = value % self.mod

    def __hash__(self) -> int:
        return hash((self.value, self.mod))

    def __eq__(self, other) -> bool:
        if isinstance(other, self.__class__):
            return self.value == other.value
        else:
            return NotImplemented

    def __ne__(self, other) -> bool:
        if isinstance(other, self.__class__):
            return self.value != other.value
        else:
            return NotImplemented

    # TODO: Add type hints
    def __add__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__((self.value + other.value) % self.mod)
        else:
            return NotImplemented

    def __sub__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__((self.value - other.value) % self.mod)
        else:
            return NotImplemented

    def __mul__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__(self.value * other.value % self.mod)
        else:
            return NotImplemented

    def __truediv__(self, other):
        if isinstance(other, self.__class__):
            a = other.value
            b = self.mod
            u = 1
            v = 0
            while b:
                t = a // b
                a, b = b, a - t * b
                u, v = v, u - t * v
            return self.__class__(self.value * u % self.mod)
        else:
            return NotImplemented

    def __pow__(self, other):
        if isinstance(other, self.__class__):
            v = 1
            a = self.value
            b = other.value
            mod = self.mod
            while b > 0:
                if b & 1:
                    v = v * a % mod
                a = a * a % mod
                b >>= 1
            return self.__class__(v)
        else:
            return NotImplemented

    @classmethod
    def comb(cls, n: int, k: int):
        if n < k:
            return cls(0)
        if n < 0 or k < 0:
            return cls(0)

        if n < len(cls.fac):
            return cls(cls.fac[n] * (cls.finv[k] * cls.finv[n - k] % cls.mod) % cls.mod)
        else:
            k = min(k, n - k)
            a = reduce(mul, map(cls, range(n - k + 1, n + 1)), cls(1))
            b = reduce(mul, map(cls, range(1, k + 1)), cls(1))
            return a / b

    def __repr__(self) -> str:
        return f'{self.__class__.__name__}({self.value!r})'

    def __str__(self) -> str:
        return str(self.value)


def mod_comb_init(max_: int) -> Callable[[Type[T]], Type[T]]:
    def _mod_comb_init(cls: Type[T]) -> Type[T]:
        mod: int = cls.mod
        assert max_ < mod

        fac = cls.fac = [0] * max_
        finv = cls.finv = [0] * max_
        inv = cls.inv = [0] * max_

        fac[0] = fac[1] = 1
        finv[0] = finv[1] = 1
        inv[1] = 1
        for i in range(2, max_):
            fac[i] = fac[i - 1] * i % mod
            inv[i] = mod - inv[mod % i] * (mod // i) % mod
            finv[i] = finv[i - 1] * inv[i] % mod

        return cls
    return _mod_comb_init


@mod_comb_init(10 ** 6 + 1)
class ModInt(ModIntBase):
    mod = 1000000007  # 10 ** 9 + 7


def resolve(in_):
    r1, c1, r2, c2 = map(int, next(in_).strip().split())
    # ans = f(r2+1, c2+1) - f(r2+1, c1) - f(r1, c2+1) + f(r1, c1)
    ans = (
        ModInt.comb((r2 + 1) + (c2 + 1), c2 + 1)
        - ModInt.comb((r2 + 1) + c1, c1)
        - ModInt.comb(r1 + (c2 + 1), c2 + 1)
        + ModInt.comb(r1 + c1, c1)
    )

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
a1,b1,a2,b2=map(int,input().split())

import sys
sys.setrecursionlimit(2000000000)

p = 10 ** 9 + 7
N = a2+b2+2  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
  fact.append((fact[-1] * i) % p)
  inv.append((-inv[p % i] * (p // i)) % p)
  factinv.append((factinv[-1] * inv[-1]) % p)

def comb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fact[n] * factinv[r] * factinv[n-r] % p



score=comb(a2+b2+2,a2+1,p)-comb(a2+b1+1,a2+1,p)-comb(a1+b2+1,a1,p)+comb(a1+b1,a1,p)
print(score%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

a1,b1,a2,b2=map(int,input().split())
score=comb(a2+b2+2,a2+1)-comb(a2+b1+1,a2+1)-comb(a1+b2+1,a1)+comb(a1+b1,a1)
print(score%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
r1,c1,r2,c2=map(int,input().split())
MOD=10**9+7

from scipy.special import comb

def comb_mod(n,k):
  return comb(n,k,exact=True)%MOD

ans=comb_mod(r2+c2+2,r2+1)+comb_mod(r1+c1,r1)-comb_mod(c1+r2+1,c1)-comb_mod(c2+r1+1,r1)
ans%=MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:

class Combination:
    """
  O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
  n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
  使用例：
  comb = Combination(1000000)
  print(comb(5, 3))  # 10
  """

    def __init__(self, n_max, mod=10 ** 9 + 7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]

        facinv = [1]
        for i in range(1, n + 1):
            fac.append(fac[i - 1] * i % self.mod)
            facinv.append(facinv[i - 1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n + 1)
        modinv[1] = 1
        for i in range(2, n + 1):
            modinv[i] = self.mod - self.mod // i * \
                modinv[self.mod % i] % self.mod
        return modinv


MOD = 10**9 + 7

r1, c1, r2, c2 = map(int, input().split())
c = Combination(2000006)
ans = 0
for r in range(r1, r2 + 1):
    temp = c(c2 + r + 1, r + 1) - c(c1 + r + 1 - 1, r + 1)
    temp %= MOD
    ans += temp
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
r1,c1,r2,c2=map(int,input().split())

from scipy.special import comb
MOD=10**9+7

ans=0
ans+=comb(c1+r1,r1,exact=True)
ans%=MOD
ans-=comb(c1+r2+1,r2+1,exact=True)
ans%=MOD
ans-=comb(c2+r1+1,r1,exact=True)
ans%=MOD
ans+=comb(c2+r2+2,r2+1,exact=True)
ans%=MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
MOD_t_MAX = 2 * 10**6 + 100

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        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 MOD_COM(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

def main():
    r1, c1, r2, c2 = map(int, input().split())
    MOD_COM_init()
    a = MOD_COM(r2+1+c2+1, r2+1) - 1
    b = MOD_COM(r2+1+c1, c1) - 1
    c = MOD_COM(r1+c2+1, r1) - 1
    d = MOD_COM(r1+c1, c1) - 1
    ans = a - b - c + d
    print(ans % MOD)

if __name__ == "__main__":
    main()