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

Solution code:
###################
# AC:1102 ms(PyPy)
###################

MOD = 10**9+7
fac = [1, 1]
f_inv = [1, 1]
inv = [0, 1]

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)


def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def f(r, c):
    return modcmb(r+c, r, MOD)


def main():
    prepare(2*10**6+10, MOD)
    r1,c1,r2,c2 = map(int, input().split())

    ans = 0
    for c in range(c1,c2+1):
        ans += ((r2+1) * modcmb(c+r2+1, r2+1, MOD) - r1 * modcmb(c+r1, r1, MOD)) * pow(c+1, MOD-2, MOD)
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

mod = 10**9+7
fc = [0]*(2*10**6+2)
fc[0] = 1

for i in range(1, 2*10**6+2):
    fc[i] = fc[i-1]*i%mod
    
inv = [1]*(2*10**6+2)
lst = 2*10**6+1
inv[lst] = pow(fc[lst], mod-2, mod)

for i in range(lst, 0, -1):
    inv[i-1] = (inv[i]*i)%mod

def comb(n, r):
    return ((fc[n]*inv[r])%mod)*inv[n-r]%mod

cum=0
for i in range(r1, r2+1):
    d1 = comb(i+1+c2, c2)
    d2 = comb(i+c1, c1-1)
    cum = (cum+(d1-d2))%mod

print(cum)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    r1, c1, r2, c2 = map(int, input().split())
    
    # Combination calculation
    p = 10 ** 9 + 7
    N = r2 + c2 + 2
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    
    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):
        return fact[n] * factinv[r] * factinv[n - r] % p
    
    def f(i, j):
        return comb(i + j, i)
    
    def g(i, j):
        return f(i + 1, j + 1) - 1
    
    ans = g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)
    
    print(ans % p)

solve()

Submission status: Time Limit Exceeded

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

p = 10 ** 9 + 7

from math import factorial
def comb(n, r):
    a = factorial(n)
    b = pow(factorial(n - r), p - 2, p)
    c = pow(factorial(r), p - 2, p)
    return a * b * c % p

def f(i, j):
    return comb(i + j, i)

def g(i, j):
    return f(i + 1, j + 1) - 1

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

print(ans)

Submission status: Time Limit Exceeded

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

# Combination calculation
p = 10 ** 9 + 7
N = r2 + c2 + 2
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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):
    return fact[n] * factinv[r] * factinv[n - r] % p

def f(i, j):
    return comb(i + j, i)

def g(i, j):
    return f(i + 1, j + 1) - 1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def inpl():
    return list(map(int, input().split()))


def cmb(n, r):
    # combination
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    return (over[n] * under[r] * under[n - r]) % MOD


# 互いに素なx, yについて、a * x + b * y = 1の解の一つを求める。
def extGCD(x, y):
    r = [1, 0, x]
    w = [0, 1, y]
    # print(r, w)
    while w[2] != 1:
        # print(r, w)
        q = r[2] // w[2]
        w_tmp = [r[0] - q * w[0], r[1] - q * w[1], r[2] % w[2]]
        r, w = w, w_tmp

    return w[:2]


def mod_inv(a, m):
    x, _ = extGCD(a, m)
    return (x + m) % m


def g(x, y):
    return (cmb(x + y + 2, x + 1) - 1 + MOD) % MOD


r1, c1, r2, c2 = inpl()

MOD = 10**9 + 7

over = [1]
under = [1]
for i in range(r2 + c2 + 2):
    over.append(over[-1] * (i + 1) % MOD)
    under.append(under[-1] * mod_inv(i + 1, MOD) % MOD)

print((g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
  U = 2*10**6+2
  MOD = 10**9+7

  fact = [1]*(U+1)
  fact_inv = [1]*(U+1)

  for i in range(1,U+1):
      fact[i] = (fact[i-1]*i)%MOD
  fact_inv[U] = pow(fact[U], MOD-2, MOD)

  for i in range(U,0,-1):
      fact_inv[i-1] = (fact_inv[i]*i)%MOD

  def comb(n, k):
      if k < 0 or k > n:
          return 0
      z = fact[n]
      z *= fact_inv[k]
      z %= MOD
      z *= fact_inv[n-k]
      z %= MOD
      return z

  ans = 0
  r1, c1, r2, c2 = map(int, input().split())
  for i in range(c1, c2+1):
    ans += comb(i+r2+1, i+1) - comb(i+r1, i+1)
    ans %= MOD
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
U = 2*10**6+2
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
ans = 0
r1, c1, r2, c2 = map(int, input().split())
for i in range(c1, c2+1):
  ans += comb(i+r2+1, i+1) - comb(i+r1, i+1)
  ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

def f(n,k,p):
    n1, k = n+1, min(k, n-k)
    numer = denom = 1
    for i in range(1,k+1):
        numer = numer*(n1-i)
        denom = denom*i
    return numer*pow(denom,p-2,p)%p

r1,c1,r2,c2 = map(int,input().split(" "))
ans = f(r2+c2+2,c2+1,mod)-f(r2+c1+1,c1,mod)-f(r1+c2+1,c2+1,mod)+f(r1+c1,c1,mod)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
MAX_N = 2 * 10**6 + 1
 
# Construct factorial table
fac = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * (i) % MOD
 
fac_inv = [1] + [0] * MAX_N
# Femrmat's little theorem says a**(p-1) mod p == 1
# then, a * a**(p-2) mod p == 1
# it means that a**(p-2) is the inverse element
# Here, Get 1 / n! first
fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD
 
def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD
 
def get_rect_sum(r, c):
    total = 0
    for i in range(1, c+2):
        total += mod_nCr(r + i, r)
        total %= MOD
    return total
 
r1, c1, r2, c2 = [int(item) for item in input().split()]
ans = get_rect_sum(r2, c2)
ans += get_rect_sum(r1 - 1, c1 - 1)
ans -= get_rect_sum(r2, c1 - 1)
ans -= get_rect_sum(r1 - 1, c2)
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
MAX_N = 2 * 10**6 + 1
 
# Construct factorial table
fac = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * (i) % MOD
 
fac_inv = [1] + [0] * MAX_N
# Femrmat's little theorem says a**(p-1) mod p == 1
# then, a * a**(p-2) mod p == 1
# it means that a**(p-2) is the inverse element
# Here, Get 1 / n! first
fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD
 
def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD
 
def get_rect_sum(r, c):
    total = 0
    for i in range(1, c+2):
        total += mod_nCr(r + i, r)
    return total
 
r1, c1, r2, c2 = [int(item) for item in input().split()]
ans = get_rect_sum(r2, c2)
ans += get_rect_sum(r1 - 1, c1 - 1)
ans -= get_rect_sum(r2, c1 - 1)
ans -= get_rect_sum(r1 - 1, c2)
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
fac = [1, 1]
f_inv = [1, 1]
inv = [0, 1]

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)


def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def f(r, c):
    return modcmb(r+c, r, MOD)


def main():
    prepare(2*10**6+10, MOD)
    r1,c1,r2,c2 = map(int, input().split())

    ans = 0
    for i in range(1,c2+2):
        ans += f(r2, i)
        ans %= MOD

    for i in range(1,c2+2):
        ans -= f(r1-1, i)
        ans %= MOD

    for i in range(1,c1+1):
        ans -= f(r2, i)
        ans %= MOD

    for i in range(1,c1+1):
        ans += f(r1-1, i)
        ans %= MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

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

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] * ifac[com_n - com_r]

def s(r, c):
    return nCr(r + c + 2, r + 1)

r1, c1, r2, c2 = MI()
md = 10**9+7
n_max = r2+c2+5
fac = [mint(1)]
for i in range(1, n_max + 1): fac.append(fac[-1] * i)
ifac = [1] * (n_max + 1)
ifac[n_max] = fac[n_max] ** (md - 2)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1)

def main():
    ans=s(r2,c2)-s(r1-1,c2)-s(r2,c1-1)+s(r1-1,c1-1)
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

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

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] * ifac[com_n - com_r]

md = 10**9+7
n_max = 10**6+5
fac = [mint(1)]
for i in range(1, n_max + 1): fac.append(fac[-1] * i)
ifac = [1] * (n_max + 1)
ifac[n_max] = fac[n_max] ** (md - 2)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1)

def main():
    def s(r,c):
        return nCr(r+c+2,r+1)

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

main()

Submission status: Time Limit Exceeded

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

mod = 1000000007

# return an integer k s.t. (a * k) % p = 1 and 0 <= k < p.
def inversion(a, p):
    b = p
    u, v = 1, 0
    while b >= 1:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= p
    if u < 0:
        u += p
    return u

# return nCr % p.
def combination(n, r, p):
    if n < r:
        return 0
    r = min(n - r, r)
    nCr = 1
    for d in range(1, r + 1):
        nCr *= n
        nCr %= p
        n -= 1
        nCr *= inversion(d, p)
        nCr %= p
    return nCr

answer = 0
answer += combination(r2 + c2 + 2, r2 + 1, mod)
answer -= combination(r2 + c1 + 1, r2 + 1, mod)
answer -= combination(r1 + c2 + 1, c2 + 1, mod)
answer += combination(r1 + c1    , c1    , mod)

answer %= mod

if answer < 0:
    answer += mod

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

r1, c1, r2, c2 = [0] * 4

def format_input(filename = None):
	global r1, c1, r2, c2
	if filename == None:
		r1, c1, r2, c2 = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		r1 = rng(1, 10**6)
		c1 = rng(1, 10**6)
		r2 = rng(r1, 10**6)
		c2 = rng(c1, 10**6)

def combination(r, c):
	return factorial(r + c) // (factorial(r) * factorial(c))

def get_answer():
	cmb = []
	cmb.append([0])
	cmb[0][0] = combination(r1, c1)
	answer = 0
	for i in range(r2 - r1 + 1):
		for j in range (c2 - c1 + 1):
			answer += cmb[i][j]
			cmb[i].append(cmb[i][j] * (i + r1 + j + c1 + 1) // (j + c1 + 1))
			answer = answer % (10 ** 9 + 7)
		cmb.append([cmb[i][0] * (i + r1 + c1 + 1) // (i + r1 + 1)])
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	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**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 )

#入力
r1,c1,r2,c2 = map(int, input().split())

def g(r,c):
    gsum = 0
    for i in range(1,r+2):
        gsum += cmb(i+c,c)
    return gsum
'''
sum = 0
for r in range(r1,r2+1):
    for c in range(c1,c2+1):
        sum += cmb(r+c,r)
print(sum % mod)
'''
sum2 = g(r2,c2) - g(r1-1,c2) - g(r2,c1-1) + g(r1-1,c1-1)
print(sum2 % mod)

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

#入力
r1,c1,r2,c2 = map(int, input().split())

sum = 0
for r in range(r1,r2+1):
    for c in range(c1,c2+1):
        sum += cmb(r+c,r)

print(sum % mod)

Submission status: Time Limit Exceeded

Solution code:
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


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

def nasu(n, m):
  ans = (com.com(n + 2, m + 1) - 1)
  return ans
N = r2 + c2
com = comb(N + 3, MOD)

ans = nasu(N, r2)
ans = (ans + nasu(c1 + r1 - 2, min(c1, r1) - 1)) % MOD
ans = (ans - nasu(r2 + c1 - 1, c1 - 1))
ans = (ans - nasu(c2 + r1 - 1, r1 - 1))
while ans < 0: ans += MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
A=2*(10**6)+3
P=[0 for i in range(A+1)]
P[1]=1
for i in range(2,A):
    P[i]=P[i-1]*i%mod

dr2=pow(P[r2],mod-2,mod)
dr1=pow(P[r1-1],mod-2,mod)
def combr2(x):
    y=r2
    if y>x or x<=0:
        return(0)
    elif y==0:
        return(1)
    else:
        return(P[x]*pow(P[x-y],mod-2,mod)%mod*dr2%mod)

def combr1(x):
    y=r1-1
    if y>x or x<=0:
        return(0)
    elif y==0:
        return(1)
    else:
        return(P[x]*pow(P[x-y],mod-2,mod)%mod*dr1%mod)
count=0
for i in range(c1+1,c2+2):
    count=(count+combr2(i+r2)-combr1(i+r1-1))%mod
print(count%mod)

Submission status: Time Limit Exceeded

Solution code:
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
A=2*(10**6)+3
P=[0 for i in range(A+1)]
P[1]=1
for i in range(2,A):
    P[i]=P[i-1]*i%mod
def comb(x,y):
    if y>x or x<=0:
        return(0)
    elif y==0:
        return(1)
    else:
        return(P[x]*pow(P[x-y],mod-2,mod)%mod*pow(P[y],mod-2,mod)%mod)

count=0
for i in range(c1+1,c2+2):
    count=(count+comb(i+r2,r2)-comb(i+r1-1,r1-1))%mod
print(count%mod)

Submission status: Time Limit Exceeded

Solution code:
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
A=2*(10**6)+3
P=[0 for i in range(A+1)]

P[1]=1
for i in range(2,A):
    P[i]=P[i-1]*i%mod


def comb(x,y):
    if y>x or x<=0:
        return(0)
    elif y==0:
        return(1)
    else:
        return(P[x]*pow(P[x-y],mod-2,mod)%mod*pow(P[y],mod-2,mod)%mod)

count=0
for i in range(c1+1,c2+1 +1):
    count=(count+comb(i+r2,r2)-comb(i+r1-1,r1-1))%mod
print(count%mod)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
A=2*(10**6)+100
P=[0 for i in range(A+1)]

P[1]=1
for i in range(2,A):
    P[i]=P[i-1]*i%mod


def comb(x,y):
    if y>x or x<=0:
        return(0)
    elif y==0:
        return(1)
    else:
        return(P[x]*pow(P[x-y],mod-2,mod)%mod*pow(P[y],mod-2,mod)%mod)

count=0
for i in range(c1+1,c2+1 +1):
    count=(count+comb(i+r2,r2)-comb(i+r1-1,r1-1))%mod
print(count%mod)

Submission status: Time Limit Exceeded

Solution code:
def inpl():
    return list(map(int, input().split()))


def cmb(n, r):
    # combination
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    # print(n + r)
    return A[n] // (A[r] * A[n - r])


def g(x, y):
    return (cmb(x + y + 2, y + 1) - 1) % MOD


r1, c1, r2, c2 = inpl()

MOD = 10**9 + 7

A = [1]
for i in range(r2 + c2 + 2):
    A.append(A[-1] * (i + 1))
# print(A)
# print(g(r2, c2))
print((g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce


def inpl():
    return list(map(int, input().split()))


def cmb(n, r):
    # combination
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


def g(x, y):
    return (cmb(x + y + 2, y + 1) - 1) % MOD


r1, c1, r2, c2 = inpl()

MOD = 10**9 + 7

print((g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
r1, c1, r2, c2 = map(int, input().split())
n = 2 * 10 ** 6
from math import factorial

class Facts():
    # 階乗のメモ化
    # 組み合わせ数、順列数の計算を高速に行う
    def __init__(self, max_num=10**5, p=10**9 + 7):
        self.p = p
        self.max_num = max_num
        self.fact = [1] * (self.max_num + 1)
        for i in range(1, self.max_num + 1):
            self.fact[i] = self.fact[i-1] * i
            self.fact[i] %= self.p

    def comb(self, n, k):
        # nCk mod p を求める
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a = self.fact[n]
        b = self.fact[k]
        c = self.fact[n-k]
        return (a*self.power_func(b, self.p-2) *
                self.power_func(c, self.p-2)) % self.p

    def perm(self, n, k):
        # nPk mod p を求める
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a = self.fact[n]
        b = self.fact[n-k]
        return (a * self.power_func(b, self.p-2)) % self.p


    def power_func(self, a, b):
        # a^b mod p　を繰り返し二乗法で求める
        if b == 0:
            return 1
        if b % 2 == 0:
            d = self.power_func(a, b//2)
            return d*d % self.p
        if b % 2 == 1:
            return (a*self.power_func(a, b-1)) % self.p

class FLT:
    #フェルマーの小定理
    # a^(-1) = a^(m-2) mod p
    def __init__(self, mod=10**9+7):
        self.mod = mod

    def rep_sqr(self, base, k):
        if k == 0:
            return 1
        elif k % 2 == 0:
            return (self.rep_sqr(base, k // 2) ** 2) % self.mod
        else:
            return (self.rep_sqr(base, k - 1) * base) % self.mod

    def inv(self, a):
        # 逆元を取る
        return self.rep_sqr(a, self.mod-2)

fact = Facts(n)

def f(x, y):
    return fact.comb(x+y, y)

def g(x, y):
    s = 0
    for i in range(y+1):
        s += f(x, i+1)
        s %= MOD
    return s

print((g(r2, c2) - g(r2, c1-1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
def inv(x):
    return pow(x, MOD-2, MOD)

def C(n, r):
    return fact[n]*inv(fact[r])*inv(fact[n-r])
    
def g(r, c):
    res = 0
    
    for i in range(1, r+2):
        res += C(i+c, c)
        res %= MOD
    
    return res

r1, c1, r2, c2 = map(int, input().split())
MOD = 10**9+7
fact = [1]

for i in range(1, 2*10**6+100):
    fact.append(fact[-1]*i%MOD)

print((g(r2, c2)-g(r2, c1-1)-g(r1-1, c2)+g(r1-1, c1-1))%MOD)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

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

memo = {}
memo[(r1, c1)] = combinations_count(r1 + c1, r1)
def route(r, c):
  if (r, c) not in memo:
    if r == r1:
      memo[(r, c)] = route(r, c-1) * (r+c) // c
    elif c == c1:
      memo[(r, c)] = route(r-1, c) * (r+c) // r
    else:
      memo[(r, c)] = route(r - 1, c) + route(r, c - 1)
  return memo[(r, c)]

print(sum(route(r, c) for r in range(r1, r2+1) for c in range(c1, c2+1)) % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f.append(f[-1]*(i+1)%mod)
inv=[]
for i in range(len(f)):inv.append(pow(f[i],mod-2,mod)%mod)
def comb(a,b):return f[a]*inv[b]*inv[a-b]%mod
def F(r,c):
  ans=0
  for i in range(r+c+1):
    ans+=2**i
    ans%=mod
  #print(ans)
  d=0
  s=0
  for i in range(r-1,-1,-1):
    s+=comb((r-i-1)+c,c)
    d+=2**i*s
    s%=mod
    d%=mod
  #print(d)
  ans=(ans+(mod-d))%mod
  d=0
  s=0
  for i in range(c-1,-1,-1):
    s+=comb((c-i-1)+r,r)
    d+=2**i*s
    s%=mod
    d%=mod
  #print(d)
  ans=(ans+(mod-d))%mod
  return ans
"""
"""
ans=F(r2,c2)
ans=(ans+(mod-F(r2,c1-1)))%mod
ans=(ans+(mod-F(r1-1,c2)))%mod
ans+=F(r1-1,c1-1)
print(ans%mod)
"""
print(F(4,3))
"""

Submission status: Time Limit Exceeded

Solution code:
r1, c1, r2, c2 = list(map(int, input().split()))
s = 0
n = r2 + c2 + 2
mod = 10 ** 9 + 7
fac = {0: 1, 1: 1}
finv = {0: 1, 1: 1}
inv = {1: 1}

def comb_init():
    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

def comb(n, k):
    n, k = n + k + 2, k + 1
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod

comb_init()
ans = comb(r2, c2) - comb(r1 - 1, c2) -  comb(r2, c1 - 1) + comb(r1 - 1, c1 - 1)
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
inv=[]
for i in range(len(f)):inv+=[pow(f[i],mod-2,mod)%mod]
def comb(a,b):return f[a]*inv[b]*inv[a-b]%mod
def F(r,c):
  ans=0
  for i in range(r+c+1):
    ans+=2**i
    ans%=mod
  #print(ans)
  d=0
  s=0
  for i in range(r-1,-1,-1):
    s+=comb((r-i-1)+c,c)
    d+=2**i*s
    s%=mod
    d%=mod
  #print(d)
  ans=(ans+(mod-d))%mod
  d=0
  s=0
  for i in range(c-1,-1,-1):
    s+=comb((c-i-1)+r,r)
    d+=2**i*s
    s%=mod
    d%=mod
  #print(d)
  ans=(ans+(mod-d))%mod
  return ans
"""
"""
ans=F(r2,c2)
ans=(ans+(mod-F(r2,c1-1)))%mod
ans=(ans+(mod-F(r1-1,c2)))%mod
ans+=F(r1-1,c1-1)
print(ans%mod)
"""
print(F(4,3))
"""

Submission status: Time Limit Exceeded

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

mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod

def F(r,c):
  ans=pow(2,r+c+1,mod) -1
  d=0
  s=0
  for i in range(r-1,-1,-1):
    s+=comb((r-i-1)+c,c)
    d+=pow(2,i,mod)*s
    s%=mod
    d%=mod
  ans=(ans+(mod-d))%mod
  d=0
  s=0
  for i in range(c-1,-1,-1):
    s+=comb((c-i-1)+r,r)
    d+=pow(2,i,mod)*s
    s%=mod
    d%=mod
  ans=(ans+(mod-d))%mod
  
  return ans

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x -= MOD-other.x if isinstance(other, mint) else MOD-other.x
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other.x
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other.x
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

class comb():
    # class <mint> should be imported
    def __init__(self, n):
        self.n = n
        fact = [0]*(n+1) # 1-indexed
        ifact = [0]*(n+1) # 逆元
        fact[0] = mint(1)
        for i in range(1, n+1):
            fact[i] = fact[i-1]*i
        ifact[-1] = pow(fact[-1], MOD-2)
        for i in range(n, 0, -1):
            ifact[i-1] = ifact[i]*i
        self.fact = fact
        self.ifact = ifact
    def calc(self, n, k):
        if k<0 or k>n:
            return 0
        return self.fact[n]*self.ifact[k]*self.ifact[n-k]

r1,c1,r2,c2 = map(int, input().split())
ans=0
cb=comb(r2+c2)
acr=[0]
acc=[0]
for i in range(1,r2-r1+1):
    acr.append(acr[-1]+cb.calc(i+c2-c1-1,i))

for i in range(1,c2-c1+1):
    acc.append(acc[-1]+cb.calc(i+r2-r1-1,i))

for r in range(r1+1,r2+1):
    ans+=cb.calc(c1+r, r)
    ans+=acr[r2-r1-(r-r1-1)]*cb.calc(c1+r, r)

for c in range(c1+1,c2+1):
    ans+=cb.calc(c+r1, r1)
    ans+=acc[c2-c1-(c-c1-1)]*cb.calc(c+r1, c)

ans+=cb.calc(c1+r1, c1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
ans=0
for i in range(c1,c2+1):
  d=((r2+1)*f[i+r2+1]%mod)*f[r1]
  d%=mod
  d=(d+(mod-((r1*f[r2+1]%mod)*f[i+r1])%mod))%mod
  d*=pow((((i+1)*f[i]%mod)*f[r1]%mod)*f[r2+1]%mod,mod-2,mod)
  d%=mod
  ans+=d
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
ans=0
for i in range(c1,c2+1):
  d=(r2+1)*f[i+r2+1]*f[r1]
  d%=mod
  d=(d+(mod-(r1*f[r2+1]*f[i+r1])%mod))%mod
  d*=pow((i+1)*f[i]*f[r1]*f[r2+1],mod-2,mod)
  d%=mod
  ans+=d
  ans%=mod
print(ans)