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:
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 or c == c1:
      memo[(r, c)] = combinations_count(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:
m=10**9+7
def f(r,c,s=1):
 for i in range(c):s=s*(r+c-i)*pow(i+1,m-2,m)%m
 return s
a,b,c,d=map(int,input().split())
print((f(a,b)-f(c+1,b)-f(a,d+1)+f(c+1,d+1))%m)

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
  d*=pow((i+1)*f[i]*f[r1]*f[r2+1],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]
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=0
  for i in range(r+c+1):
    ans+=pow(2,i,mod)
    ans%=mod
  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
# 組み合わせ(高速，フェルマーの小定理を利用)
def cmb(n, r, mod):
    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 ** 7
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())
R = r2 - r1 + 1
C = c2 - c1 + 1
ans = cmb(r1+c1, r1, mod)

rc = [[0] * C for _ in range(R)]
rc[0][0] = ans

for r in range(1, R):
    rc[r][0] = cmb(r1 + c1 + r, c1, mod)

for c in range(1, C):
    rc[0][c] = cmb(r1 + c1 + c, r1, mod)

for r in range(1, R, 1):
    for c in range(1, C, 1):
        tmp = rc[r-1][c] + rc[r][c-1]
        rc[r][c] = tmp
        ans += tmp

##print(rc)
for r in range(1, R):
    ans += rc[r][0]

for c in range(1, C):
    ans += rc[0][c]

print(ans % mod)

Submission status: Time Limit Exceeded

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

def nCr_mod_p(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

p = 10 ** 9 + 7
N = 10 ** 7  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p), 0! = 1! = 1
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p), 0! = 1! = 1
inv = [0, 1]  # inv[n] = n^(-1) mod p, 0! = 1　だけど便宜上inv[0]=0にしてる

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)

sum22 = nCr_mod_p(r2+1+c2+1,r2+1,p) - 1
sum21 = nCr_mod_p(r2+1+c1,r2+1,p) - 1
sum12 = nCr_mod_p(r1+c2+1,c2+1,p) - 1
sum11 = nCr_mod_p(r1+c1,c1,p) - 1

ans = sum22 - sum21 - sum12 + sum11
ans %= p

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(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=0
  for i in range(r+c+1):
    ans+=2**i
    ans%=mod
  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
  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
  ans=(ans+(mod-d))%mod
  return ans

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

Submission status: Time Limit Exceeded

Solution code:


def pow_mod(x, y):
    MOD = 1000000007
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD

def main():
  MOD = 1000000007
  r1, c1, r2, c2 = map(int, input().split()) 

  points = {r2 + c2 + 2, r2 + 1, c2 + 1, r2 + c1 + 1, c1, r1 + c2 + 1, r1, r1 + c1}

  factorial_map = {0: 1}
  factorial_inv_map = {0: 1}
  for i in range(1, r2 + c2 + 3):
    factorial_map[i] = (factorial_map[i - 1] * i) % MOD
    factorial_inv_map[i] = (factorial_inv_map[i - 1] * pow_mod(i, MOD - 2)) % MOD
    if i > 1 and (i - 2) not in points:
      del factorial_map[i-2]
      del factorial_inv_map[i-2]

  a = 1
  a *= factorial_map[r2 + c2 + 2]
  a %= MOD
  a *= factorial_inv_map[r2 + 1]
  a %= MOD
  a *= factorial_inv_map[c2 + 1]
  a %= MOD

  b = 1
  b *= factorial_map[r2 + c1 + 1]
  b %= MOD
  b *= factorial_inv_map[r2 + 1]
  b %= MOD
  b *= factorial_inv_map[c1]
  b %= MOD

  c = 1
  c *= factorial_map[r1 + c2 + 1]
  c %= MOD
  c *= factorial_inv_map[r1]
  c %= MOD
  c *= factorial_inv_map[c2 + 1]
  c %= MOD

  d = 1
  d *= factorial_map[r1 + c1]
  d %= MOD
  d *= factorial_inv_map[r1]
  d %= MOD
  d *= factorial_inv_map[c1]
  d %= MOD

  ans = a
  ans -= b
  ans %= MOD
  ans -= c 
  ans %= MOD
  ans += d
  ans %= MOD

  print(ans)


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

MOD = 1000000007

def pow_mod(x, y):
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD

points = {r2 + c2 + 2, r2 + 1, c2 + 1, r2 + c1 + 1, c1, r1 + c2 + 1, r1, r1 + c1}

factorial_map = {0: 1}
factorial_inv_map = {0: 1}
for i in range(1, r2 + c2 + 3):
  factorial_map[i] = (factorial_map[i - 1] * i) % MOD
  factorial_inv_map[i] = (factorial_inv_map[i - 1] * pow_mod(i, MOD - 2)) % MOD
  if i > 1 and (i - 2) not in points:
    del factorial_map[i-2]
    del factorial_inv_map[i-2]


a = 1
a *= factorial_map[r2 + c2 + 2]
a %= MOD
a *= factorial_inv_map[r2 + 1]
a %= MOD
a *= factorial_inv_map[c2 + 1]
a %= MOD

b = 1
b *= factorial_map[r2 + c1 + 1]
b %= MOD
b *= factorial_inv_map[r2 + 1]
b %= MOD
b *= factorial_inv_map[c1]
b %= MOD

c = 1
c *= factorial_map[r1 + c2 + 1]
c %= MOD
c *= factorial_inv_map[r1]
c %= MOD
c *= factorial_inv_map[c2 + 1]
c %= MOD

d = 1
d *= factorial_map[r1 + c1]
d %= MOD
d *= factorial_inv_map[r1]
d %= MOD
d *= factorial_inv_map[c1]
d %= MOD

ans = a
ans -= b
ans %= MOD
ans -= c 
ans %= 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]
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=0
  for i in range(r+c+1):
    ans+=2**i
    ans%=mod
  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
  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
  ans=(ans+(mod-d))%mod
  return ans

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

Submission status: Time Limit Exceeded

Solution code:
import sys


TEST_INPUT = [
    """
    1 1 2 2
    """,
    """
    314 159 2653 589
    """
]
ANSWER = [
    "14",
    "602215194"
]


class InputHandler:

    def __init__(self, text_lines="", is_test=False):
        self.data = list(text_lines.split("\n"))
        self.index = 0
        self.is_test = is_test

    def input(self):
        if self.is_test:
            self.index += 1
            return self.data[self.index].strip()
        else:
            return sys.stdin.readline().rstrip()


LARGE = 10 ** 9 + 7


def solve_special(r, c):

    if r > 0 and c > 0:
        r, c = max(r, c), min(r, c)
        # res = (r + c + 2) C (c + 1)
        inv_large = [0] * (c + 2)
        for i in range(1, c + 2):
            inv_large[i] = pow(i, LARGE - 2, LARGE)

        res = 1

        for i in range(1, c + 2):
            res *= (r + i + 1)
            res %= LARGE
            res *= inv_large[i]
            res %= LARGE
        return (res - 1) % LARGE
    else:
        return r + c + 1


def solve(r1, c1, r2, c2):
    res = solve_special(r2, c2) - solve_special(r1 - 1, c2) - solve_special(r2, c1 - 1) + solve_special(r1 - 1, c1 - 1)
    return res % LARGE


def input_and_solve(ih):
    r1, c1, r2, c2 = map(int, ih.input().split())
    res = solve(r1, c1, r2, c2)
    return res


def main():
    ih = InputHandler()
    res = input_and_solve(ih)
    print(res)


def test():
    for test_input, ans in zip(TEST_INPUT, ANSWER):
        ih = InputHandler(test_input, True)
        res = input_and_solve(ih)
        # print(res, ans)
        assert str(res) == str(ans)


if __name__ == "__main__":
    # test()
    main()

Submission status: Time Limit Exceeded

Solution code:
r1, c1, r2, c2 = map(int, input().split())
import copy
l1 = [0] * (c2+1)
l2 = [0] * (r2+1)
for i in range(c2+1):
    l1[i] = copy.copy(l2)
l1[0][0] = 1
for i in range(c2 + 1):
    for j in range(r2 + 1):
        if i == 0 and j > 0:
            l1[0][j] = l1[0][j - 1]
        elif i > 0 and j == 0:
            l1[i][0] = l1[i - 1][0]
        elif i > 0 and j > 0:
            l1[i][j] = l1[i][j - 1] + l1[i - 1][j]
ans = 0
for i in range(r1, r2+1):
    for j in range(c1, c2+1):
        ans += l1[j][i]
print(int(ans % (10 ** 9 + 7)))

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

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

dp = [[1 for _ in range(r2+1)] for _ in range(c2+1)]

for j in range(c2):
    for i in range(r2):
        dp[j+1][i+1] = dp[j+1][i] + dp[j][i+1]

ans = 0
for j in range(c1, c2+1):
    ans += sum(dp[j][r1:r2+1]) % MOD
    ans = 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]
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=0
  for i in range(r+c+1):
    ans+=2**i
    ans%=mod
  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
  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
  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:
r1, c1, r2, c2 = map(int, input().split()) 

MOD = 1000000007

def pow_mod(x, y):
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD

factorial_map = {0: 1}
factorial_inv_map = {0: 1}
for i in range(1, r2 + c2 + 3):
  factorial_map[i] = (factorial_map[i - 1] * i) % MOD
  factorial_inv_map[i] = (factorial_inv_map[i - 1] * pow_mod(i, MOD - 2)) % MOD


a = 1
a *= factorial_map[r2 + c2 + 2]
a %= MOD
a *= factorial_inv_map[r2 + 1]
a %= MOD
a *= factorial_inv_map[c2 + 1]
a %= MOD

b = 1
b *= factorial_map[r2 + c1 + 1]
b %= MOD
b *= factorial_inv_map[r2 + 1]
b %= MOD
b *= factorial_inv_map[c1]
b %= MOD

c = 1
c *= factorial_map[r1 + c2 + 1]
c %= MOD
c *= factorial_inv_map[r1]
c %= MOD
c *= factorial_inv_map[c2 + 1]
c %= MOD

d = 1
d *= factorial_map[r1 + c1]
d %= MOD
d *= factorial_inv_map[r1]
d %= MOD
d *= factorial_inv_map[c1]
d %= MOD

ans = a
ans -= b
ans %= MOD
ans -= c 
ans %= 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]
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=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=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:
import sys


TEST_INPUT = [
    """
    1 1 2 2
    """,
    """
    314 159 2653 589
    """
]
ANSWER = [
    "14",
    "602215194"
]


class InputHandler:

    def __init__(self, text_lines="", is_test=False):
        self.data = list(text_lines.split("\n"))
        self.index = 0
        self.is_test = is_test

    def input(self):
        if self.is_test:
            self.index += 1
            return self.data[self.index].strip()
        else:
            return sys.stdin.readline().rstrip()


LARGE = 10 ** 9 + 7


def solve_special(r, c):

    if r > 0 and c > 0:
        r, c = max(r, c), min(r, c)
        inv_large = [0] * (c + 2)
        for i in range(1, c + 2):
            inv_large[i] = pow(i, LARGE - 2, LARGE)

        ncr = 1
        res = 0

        for i in range(1, c + 2):
            ncr *= (r + i)
            ncr %= LARGE
            ncr *= inv_large[i]
            ncr %= LARGE
            res += ncr
        return res % LARGE
    else:
        return r + c + 1


def solve(r1, c1, r2, c2):
    res = solve_special(r2, c2) - solve_special(r1 - 1, c2) - solve_special(r2, c1 - 1) + solve_special(r1 - 1, c1 - 1)
    return res % LARGE


def input_and_solve(ih):
    r1, c1, r2, c2 = map(int, ih.input().split())
    res = solve(r1, c1, r2, c2)
    return res


def main():
    ih = InputHandler()
    res = input_and_solve(ih)
    print(res)


def test():
    for test_input, ans in zip(TEST_INPUT, ANSWER):
        ih = InputHandler(test_input, True)
        res = input_and_solve(ih)
        # print(res, ans)
        assert str(res) == str(ans)


if __name__ == "__main__":
    # test()
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


TEST_INPUT = [
    """
    1 1 2 2
    """,
    """
    314 159 2653 589
    """
]
ANSWER = [
    "14",
    "602215194"
]


class InputHandler:

    def __init__(self, text_lines="", is_test=False):
        self.data = list(text_lines.split("\n"))
        self.index = 0
        self.is_test = is_test

    def input(self):
        if self.is_test:
            self.index += 1
            return self.data[self.index].strip()
        else:
            return sys.stdin.readline().rstrip()


LARGE = 10 ** 9 + 7


def solve_special(r, c):

    if r > 0 and c > 0:
        r, c = max(r, c), min(r, c)
        inv_large = [0] * (c + 2)
        for i in range(1, c + 2):
            inv_large[i] = pow(i, LARGE - 2, LARGE)

        ncr = 1
        res = 0

        for i in range(1, c + 2):
            ncr *= (r + i)
            ncr %= LARGE
            ncr *= inv_large[i]
            ncr %= LARGE
            res += ncr
        return res % LARGE
    else:
        return r + c + 1


def solve(r1, c1, r2, c2):
    res = solve_special(r2, c2) - solve_special(r1 - 1, c2) - solve_special(r2, c1 - 1) + solve_special(r1 - 1, c1 - 1)
    return res % LARGE


def input_and_solve(ih):
    r1, c1, r2, c2 = map(int, ih.input().split())
    res = solve(r1, c1, r2, c2)
    return res


def main():
    ih = InputHandler()
    res = input_and_solve(ih)
    print(res)


def test():
    for test_input, ans in zip(TEST_INPUT, ANSWER):
        ih = InputHandler(test_input, True)
        res = input_and_solve(ih)
        # print(res, ans)
        assert str(res) == str(ans)


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    divisor = int(1e9)+7
    def permute(n,r):
        res = 1
        for i in range(r, n+1):
            res *= i
        return res

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

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

    res_mat1[0] = permute(r1+c1, r1+1)//permute(c1, 1)

    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 %= divisor

    for i in range(1, c2-c1+1):
        c = c1+i
        if i%2==1:
            res_mat2 = [(num*(c+(r1+j))//c) for j, num in enumerate(res_mat1)]
            res_sum += sum(res_mat2)
        else:
            res_mat1 = [(num*(c+(r1+j))//c) for j, num in enumerate(res_mat2)]
            res_sum += sum(res_mat1)
        res_sum %= divisor
    print(res_sum)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    divisor = int(1e9)+7
    def permute(n,r):
        res = 1
        for i in range(r, n+1):
            res *= i
        return res

    r1, c1, r2, c2 = [int(x) for x in input().split()]
    
    if (r2-r1) > (c2-c1):
        c1, r1 = r1, c1
        c2, r2 = r2, c2

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

    res_mat1[0] = permute(r1+c1, r1+1)//permute(c1, 1)

    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 %= divisor

    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
            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)
        res_sum %= divisor
    print(res_sum)
if __name__ == '__main__':
    main()

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:
N=2*10**6+1
mod=10**9+7
fac=[1]*(N+1)
for i in range(1,N+1):
    fac[i]=fac[i-1]*i%mod
inv_fac=[1]*(N+1)
inv_fac[N]=pow(fac[N],mod-2,mod)
for i in range(N-1,0,-1):
    inv_fac[i]=inv_fac[i+1]*(i+1)%mod
def nCr(n,r):
    if n<=0 or r<0 or r>n:
        return 0
    return fac[n]*inv_fac[r]%mod*inv_fac[n-r]%mod

r1,c1,r2,c2=map(int,input().split())
w=r2-r1
h=c2-c1
ans=nCr(r1+c1,r1)
for i in range(r1+1,r2+1):
    ans=(ans+(nCr(i+c1,i)*nCr(r2-i+1+h,h)%mod))%mod
for i in range(c1+1,c2+1):
    ans=(ans+(nCr(i+r1,i)*nCr(c2-i+1+w,w)%mod))%mod
print(ans)

Submission status: Time Limit Exceeded

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

Solution code:
MOD = 10**9+7
list_size = (10**6+10)*4

f_list = [1]*list_size
f_r_list = [1]*list_size

for i in range(list_size - 1):
    f_list[i+1] = ((f_list[i] * (i+2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(-2, -list_size-1, -1):
    f_r_list[i] = ((f_r_list[i+1] * (list_size + 2 + i)) % MOD)



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

ans = f_list[(r2+c2)*2]*f_r_list[r2*2]*f_r_list[c2*2]
ans %= MOD
ans += f_list[(r1+c1)*2]*f_r_list[r1*2]*f_r_list[c1*2]
ans %= MOD
ans -= f_list[(r2+c1)*2]*f_r_list[r2*2]*f_r_list[c1*2]
ans %= MOD
ans -= f_list[(c2+r1)*2]*f_r_list[c2*2]*f_r_list[r1*2]
ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

M = r2+c2+10#1000010
mod = 10**9+7

f    = [1]*M
p = 1
for i in range(1, M):
    p = p*i%mod
    f[i] = p
    #finv[i] = pow(p, mod-2, mod)

finv = [1]*M
p = finv[-1] = pow(f[-1], mod-2, mod)
for i in range(M-2, 0, -1):
    p = p*(i+1)%mod
    finv[i] = p


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

def count(R,C):
    ret = ((1<<R+C+1)-1) % mod

    for c in range(C):
        x1 = comb(R+c, c)
        x2 = ((1<<C-c)-1) % mod
        ret = (ret-x1*x2) % mod

    for r in range(R):
        x1 = comb(C+r, r)
        x2 = ((1<<R-r)-1) % mod
        ret = (ret-x1*x2) % mod

    return ret

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
list_size = (10**6+10)*4

f_list = [1]*list_size
f_r_list = [1]*list_size

for i in range(list_size - 1):
    f_list[i+1] = ((f_list[i] * (i+2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(-2, -list_size-1, -1):
    f_r_list[i] = ((f_r_list[i+1] * (list_size + 2 + i)) % MOD)



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

ans = f_list[(r2+c2)*2]*f_r_list[r2*2]*f_r_list[c2*2]
ans %= MOD
ans += f_list[(r1+c1-2)*2]*f_r_list[r1*2-2]*f_r_list[c1*2-2]
ans %= MOD
ans -= f_list[(r2+c1)*2]*f_r_list[r2*2]*f_r_list[c1*2]
ans %= MOD
ans -= f_list[(c2+r1)*2]*f_r_list[c2*2]*f_r_list[r1*2]
ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 10**9 + 7
    r1, c1, r2, c2 = (int(i) for i in input().split())
    m = r2 + c2 + 1
    fac = [0] * m
    finv = [0] * m
    inv = [0] * m

    def COMBinitialize(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                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):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

    COMBinitialize(m)
    ans = 0
    # TLE
    for r in range(r1, r2+1):
        for c in range(c1, c2+1):
            ans += (fac[r+c]*finv[r]*finv[c]) % MOD
    """
    for i, v in enumerate(range(r1+c1, r2+c2+1)):
        print(i, v)
        for r in range(r1, min(r2+2, r1+(i+1))):
            c = v - r
            if c < c1 or c2 < c:
                break
            ans += (fac[v]*finv[r]*finv[c]) % MOD
            print("   ", r, c, (fac[v]*finv[r]*finv[c]) % MOD)
    """
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

@lru_cache(maxsize=None)
def get_path(i, j):
    return factorial(i + j) / (factorial(i) * factorial(j))

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

import numpy as np

print(np.sum(
    [
        get_path(i, j) if (i > j) else get_path(j, i)
        for i in range(r1, r2 + 1)
        for j in range(c1, c2 + 1)
    ]
))

Submission status: Time Limit Exceeded

Solution code:
def main():
    divisor = int(1e9)+7
    def permute(n,r):
        res = 1
        for i in range(r, n+1):
            res *= i
        return res

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

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

    res_mat1[0] = permute(r1+c1, r1+1)//permute(c1, 1)

    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 %= divisor

    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
            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)
        res_sum %= divisor
    print(res_sum)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


TEST_INPUT = [
    """
    1 1 2 2
    """,
    """
    314 159 2653 589
    """
]
ANSWER = [
    "14",
    "602215194"
]


class InputHandler:

    def __init__(self, text_lines="", is_test=False):
        self.data = list(text_lines.split("\n"))
        self.index = 0
        self.is_test = is_test

    def input(self):
        if self.is_test:
            self.index += 1
            return self.data[self.index].strip()
        else:
            return sys.stdin.readline().rstrip()


LARGE = 10 ** 9 + 7


def solve_special(r, c):

    if r > 0 and c > 0:
        inv_large = [0] * (r + c)
        for i in range(1, r + c):
            inv_large[i] = pow(i, LARGE - 2, LARGE)

        # go away for right
        ncr = 1
        pow2 = pow(2, c, LARGE)
        res_right = ncr * (pow2 - 1)

        for i in range(1, c):
            ncr *= (r + i)
            ncr %= LARGE
            ncr *= inv_large[i]
            ncr %= LARGE
            pow2 *= inv_large[2]
            pow2 %= LARGE

            res_right += ncr * (pow2 - 1)
            res_right %= LARGE

        # go away for up
        ncr = 1
        pow2 = pow(2, r, LARGE)
        res_up = ncr * (pow2 - 1)

        for i in range(1, r):
            ncr *= (c + i)
            ncr %= LARGE
            ncr *= inv_large[i]
            ncr %= LARGE
            pow2 *= inv_large[2]
            pow2 %= LARGE

            res_up += ncr * (pow2 - 1)
            res_up %= LARGE

        res = pow(2, r + c + 1, LARGE) - 1 - res_right - res_up
        # print(res_right, res_up)
        return res % LARGE
    else:
        return r + c + 1


def solve(r1, c1, r2, c2):
    res = solve_special(r2, c2) - solve_special(r1 - 1, c2) - solve_special(r2, c1 - 1) + solve_special(r1 - 1, c1 - 1)
    return res % LARGE


def input_and_solve(ih):
    r1, c1, r2, c2 = map(int, ih.input().split())
    res = solve(r1, c1, r2, c2)
    return res


def main():
    ih = InputHandler()
    res = input_and_solve(ih)
    print(res)


def test():
    for test_input, ans in zip(TEST_INPUT, ANSWER):
        ih = InputHandler(test_input, True)
        res = input_and_solve(ih)
        # print(res, ans)
        assert str(res) == str(ans)


if __name__ == "__main__":
    # test()
    main()

Submission status: Time Limit Exceeded

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))%mod)

Submission status: Time Limit Exceeded

Solution code:
r_1, c_1, r_2, c_2 = list(map(int, input().split()))

dp = [[1 for _ in range(c_2+1)] for _ in range(r_2+1)]
dp[0][0] = 0

for i in range(1, r_2+1):
    for j in range(1, c_2 + 1):
        dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
        dp[i][j] %= (10**9 + 7)

s = 0
for i in range(r_1, r_2 + 1):
    for j in range(c_1, c_2 + 1):
        s += dp[i][j]

print(s % (10**9 + 7))