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:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  
r1, c1, r2, c2 = [int(i) for i in input().split()]

def calc(r, c):
    a = comb(r + c + 2, r + 1) - r - c - 2
    b = r * (r + 3) / 2

    if c == 1:
        return b
    else:
        return a

result = calc(r2, c2) - calc(r2, c1 - 1) - calc(r1 - 1, c2) + calc(r1 - 1, c1 - 1)

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

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

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

ans = 0

for c in range(c1, c2 + 1):
    ans = (ans + comb.ncr(r2 + c + 1, c + 1) - comb.ncr(r1 + c, c + 1)) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

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

ans = 0

for c in range(c1, c2 + 1):
    ans = (ans + comb.ncr(r2 + c + 1, c + 1) - comb.ncr(r1 + c, c + 1)) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import socket

hostnames = ['N551J', 'F551C', 'X553M']
input_file = 'f1.in'
if socket.gethostname() in hostnames:
    sys.stdin = open(input_file)


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


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()

M = 10 ** 9 + 7
MAX = 10 ** 6 + 2
inv = [0] * MAX
inv[1] = 1
for i in range(2, MAX):
    inv[i] = - inv[M % i] * (M // i)
    inv[i] %= M

def f(r, c):
    res = 1
    for k in range(c + 1):
        res *= r + c + 2 - k    
        res %= M
        res *= inv[k + 1]
        res %= M
    res -= 1
    res %= M
    return res

N = 3
b = [[1] * N for _ in range(N)]
for i in range(1, N):
    for j in range(1, N):
        b[i][j] = (b[i - 1][j - 1] + b[i - 1][j]) % M


def f_exact_but_slow(r, c):
    res = 0
    for i in range(r + 1):
        for j in range(c + 1):
            res += b[i][j]
            res %= M
    return res


def solve():
    r1, c1, r2, c2 = read_int_list()
    res = f(r2, c2) 
    res -= f(r1 - 1, c2) 
    res -= f(r2, c1 - 1) 
    res += f(r1 - 1, c1 - 1)
    res %= M
    return res


def main():
    res = solve()
    print(res)


def find_mismatch():
    for r in range(20):
        for c in range(20):
            expected = f_exact_but_slow(r, c)
            output = f(r, c)
            if output == expected:
                continue
            print('r, c, expected, output:', end=' ')
            print(r, c, expected, output)


if __name__ == '__main__':
    main()
    # find_mismatch()

Submission status: Time Limit Exceeded

Solution code:
import sys
import socket

hostnames = ['N551J', 'F551C', 'X553M']
input_file = 'f1.in'
if socket.gethostname() in hostnames:
    sys.stdin = open(input_file)


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


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()

M = 10 ** 9 + 7
MAX = 2 * 10 ** 6
inv = [0] * MAX
inv[1] = 1
for i in range(2, MAX):
    inv[i] = - inv[M % i] * (M // i)
    inv[i] %= M

def f(r, c):
    res = 1
    for k in range(c + 1):
        res *= r + c + 2 - k    
        res %= M
        res *= inv[k + 1]
        res %= M
    res -= 1
    return res


def solve():
    r1, c1, r2, c2 = read_int_list()
    res = f(r2, c2) 
    res -= f(r1 - 1, c2) 
    res -= f(r2, c1 - 1) 
    res += f(r1 - 1, c1 - 1)
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
q=list(map(int,input().split()))

r=[q[0],q[2]+1]
c=[q[1],q[3]+1]

dp=[]
dp.append(list(range(1,c[1]+1)))
for i in range(1,r[1]):
    dp.append([i+1]+[0]*(c[1]-1))
#列,行の順番に注意


sumsum=0
for i in range(r[1]):
    for j in range(c[1]):
        if(i!=0 or j!=0):
            dp[i][j]=dp[i-1][j]+dp[i][j-1]
            if(dp[i][j]>1000000007):
                dp[i][j]=dp[i][j]%1000000007
        if((i>=r[0] and i<=r[1]) and(j>=c[0] and j<=c[1])):
            sumsum+=dp[i][j]
            if(sumsum>1000000007):
                sumsum=sumsum%1000000007
#for i in dp:
#    print(i)
print(sumsum)

Submission status: Time Limit Exceeded

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

div=10**9+7
def g(r,c):
    sum=0
    for i in range(c+1):
        sum+= f(r,i)
    for j in range(r+1):
        sum+= f(j,c)
    return int(sum)%div

def cmb(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]
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 f(r,c):
    return cmb(r+c,c,p)
#def f(r,c):
#    RC=math.factorial(r+c)
#    R=math.factorial(r)
#    C=math.factorial(c)
#    ans=int(RC//(R*C))%div
#    return ans

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

Submission status: Time Limit Exceeded

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

div=10**9+7
def g(r,c):
    sum=0
    for i in range(c+1):
        sum+= f(r,i)
    for j in range(r+1):
        sum+= f(j,c)
    return int(sum)%div

def cmb(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 ** 12  # N は必要分だけ用意する
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 f(r,c):
    return cmb(r+c,c,p)
#def f(r,c):
#    RC=math.factorial(r+c)
#    R=math.factorial(r)
#    C=math.factorial(c)
#    ans=int(RC//(R*C))%div
#    return ans

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

Submission status: Time Limit Exceeded

Solution code:
n = 1000000007
 
def comb(p,q):
    r = 1
    for i in range(q):
        r = r * (p-i) // (1+i)
    return r%n
    
    
r1,c1,r2,c2 = list(map(int,input().split()))
 
 
y = comb(r2+c2+2,c2+1) - comb(r2+c1+1,c1) - comb(r1+c2+1,c2+1) + comb(r1+c1,c1)
print(y % n)

Submission status: Time Limit Exceeded

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

#output
mod = 10**9 + 7

n_ = 2*10**6 + 1
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

answer = 0
for j in range(c_1, c_2+1):
    answer += cmb(r_2+j+1, j+1) % mod - cmb(r_1+j, j+1) % mod

print(answer % mod)

Submission status: Time Limit Exceeded

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

#output
mod = 10**9 + 7

n_ = 10**7 + 3
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

answer = 0
for j in range(c_1, c_2+1):
    answer += cmb(r_2+j+1, j+1) % mod - cmb(r_1+j, j+1) % mod

print(answer % mod)

Submission status: Time Limit Exceeded

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

div=10**9+7
def g(r,c):
    sum=0
    for i in range(c+1):
        sum+= f(r,i)
    for j in range(r+1):
        sum+= f(j,c)
    return int(sum)%div

def f(r,c):
    RC=math.factorial(r+c)
    R=math.factorial(r)
    C=math.factorial(c)
    ans=int(RC//(R*C))%div
    return ans

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

Submission status: Time Limit Exceeded

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

div=10**9+7
def g(r,c):
    sum=0
    for i in range(c+1):
        sum+= f(r,i)%div
    for j in range(r+1):
        sum+= f(j,c)%div
    return int(sum)%div

def f(r,c):
    RC=math.factorial(r+c)
    R=math.factorial(r)
    C=math.factorial(c)
    ans=int(RC//(R*C))%div
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)


r1, c1, r2, c2 = map(int, input().split())
MOD = 1e9 + 7
score = [0]
database = [[0 for i in range(c2+1)] for j in range(r2+1)]


def dp(x, y):
    if database[x][y]:
        return database[x][y]
    if not any((x, y)):
        return 0
    if x == 0:
        return 1
    if y == 0:
        return 1
    r = (dp(x - 1, y) + dp(x, y - 1)) % MOD
    database[x][y] = r
    if r1 <= x <= r2 and c1 <= y <= c2:
        score[0] = (score[0] + r) % MOD
        # print(x, y, r)
    return r


dp(r2, c2)
print(int(score[0]))

Submission status: Time Limit Exceeded

Solution code:
# F - Many Many Paths
def get_factorials(lim: int, MOD: int) -> list:
    """Compute a table of factorials (1-indexed)."""
    factorials = [1] * (lim + 1)
    x = 1
    for i in range(1, lim + 1):
        x *= i % MOD
        factorials[i] = x
    return factorials


def mod_comb_with_pow(n: int, k: int, MOD: int) -> int:
    """Compute nCr % MOD using pow(), not an inverse factorial table."""
    return fact[n] * pow(fact[k], MOD - 2, MOD) * pow(fact[n - k], MOD - 2, MOD) % MOD


def main():
    global fact
    MOD = 10 ** 9 + 7
    R1, C1, R2, C2 = map(int, input().split())
    fact = get_factorials(2 * 10 ** 6 + 10, MOD)
    f = lambda x, y: mod_comb_with_pow(x, y, MOD)
    ans = (f(C1 + R1, R1) - f(C1 + R2 + 1, R2 + 1) - f(C2 + R1 + 1, R1) + f(C2 + R2 + 2, R2 + 1)) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def comb(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
    for i in range(k):
        ans //= i+1
    return ans%(10**9+7)

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

r1, c1, r2, c2 = list(map(int, input().split()))
print((path(r2, c2)-path(r1-1, c2)-path(r2, c1-1)+path(r1-1, c1-1))%(10**9+7))

Submission status: Time Limit Exceeded

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

def cmb(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=2*10**6
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)

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

Submission status: Time Limit Exceeded

Solution code:
r1, c1, r2, c2 = map(int, input().split())
mod = int(1e+9) + 7
A = []
p = mod - 2
while p != 0:
  A = [p%2] + A[:]
  p //= 2
def inved(x):
  y = 1
  for i in range(len(A)):
    if A[i] == 1:
      y *= x
      y %= mod
    if i != len(A) - 1:
      y *= y
      y %= mod
  return y
fracr2c2 = 1
fracr1c2 = 1
fracr2c1 = 1
fracr1c1 = 1
fracr2 = 1
fracr1 = 1
fracc2 = 1
fracc1 = 1
for i in range(r2 + c2 + 2):
  if i < r1:
    fracr1 *= i + 1
    fracr1 %= mod
  if i < c1:
    fracc1 *= i + 1
    fracc1 %= mod
  if i < r2 + 1:
    fracr2 *= i + 1
    fracr2 %= mod
  if i < c2 + 1:
    fracc2 *= i + 1
    fracc2 %= mod
  if i < r1 + c1:
    fracr1c1 *= i + 1
    fracr1c1 %= mod
  if i < r1 + c2 + 1:
    fracr1c2 *= i + 1
    fracr1c2 %= mod
  if i < r2 + c1 + 1:
    fracr2c1 *= i + 1
    fracr2c1 %= mod
  if i < r2 + c2 + 2:
    fracr2c2 *= i + 1
    fracr2c2 %= mod
g = 0
g += (fracr2c2 * inved(fracr2) * inved(fracc2)) % mod
g %= mod
g += (fracr1c1 * inved(fracr1) * inved(fracc1)) % mod
g %= mod
g -= (fracr1c2 * inved(fracr1) * inved(fracc2)) % mod
g %= mod
g -= (fracr2c1 * inved(fracr2) * inved(fracc1)) % mod
g %= mod
print(g)

Submission status: Time Limit Exceeded

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

def cmb(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
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)

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

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9+7


def inv(x):
    return pow(x, mod - 2, mod)


r1, c1, r2, c2 = map(int, input().split())
fact, inv_fact = [1, 1], [1, 1]
for i in range(2, r2+c2+3):
    fact.append(fact[-1] * i % mod)
    inv_fact.append(inv(fact[-1]))


def nCr(n, r):
    return fact[n] * inv_fact[r] * inv_fact[n-r] % mod


def path_sum_sum(r, c):
    return ((r + 2) * nCr(c+r+2, r+2) % mod + mod - c - 1) * inv(c + 1) % mod


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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7


def make_combination_table(n):
    fact = [1]
    for i in range(1, n+1):
        fact.append(fact[i-1] * i % MOD)

    ifact = [0] * (n+1)
    ifact[n] = pow(fact[n], MOD-2, MOD)
    for i in range(n, 0, -1):
        ifact[i-1] = ifact[i] * i % MOD
    return (fact, ifact)


def mod_combination(n, r, table):
    if r > n:
        return 0
    return table[0][n] * table[1][n - r] * table[1][r] % MOD


def sum_rect(r, c, table):
    return (mod_combination(r+c+2, r+1, table)-1) % MOD


def main():
    r1, c1, r2, c2 = map(int, input().split())
    table = make_combination_table((r2+1)*(c2+1))
    r1 -= 1
    c1 -= 1

    ans = sum_rect(r2, c2, table)
    ans -= sum_rect(r2, c1, table)
    ans -= sum_rect(r1, c2, table)
    ans += sum_rect(r1, c1, table)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = 1000000007

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

    # DP定義
    dp = [[1 for i in range(r2+1)]] + [([1] + [0 for i in range(r2)]) for j in range(c2)]

    # DP埋め
    f(dp, r2, c2)
    # 解答
    ans = g(dp, r1, c1) % N
    print(ans)

def g(dp, r_s, c_s):
    target = dp[c_s:]
    sum_list = list(map(lambda x: sum(x[r_s:]), target))
    return sum(sum_list)

def f(dp, r, c):
    for i in range(1, c+1):
        for j in range(1, r+1):
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % N

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

MOD = 10**9+7
def inv(n):
    return pow(n,MOD-2,MOD)

def comb(n,r):
    r = min(r,n-r)
    ret = 1
    for i in range(r):
        ret *= (n-i)
        ret *= inv(i+1)
    ret %= MOD
    return ret

ans = 0
a = comb(r1+c1-1, r1)
b = comb(r1+c2, r1)
for r in range(r1,r2+1):
    iv = inv(r+1)
    a *= (r+c1) * iv
    b *= (r+c2+1) * iv
    ans += b-a
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
r1,c1,r2,c2=map(int,input().split())
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

z=0
for i in range(r1,r2+1):
    for j in range(c1,c2+1):
        z+=comb(i+j,j)

print(z)

Submission status: Time Limit Exceeded

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

MOD = 10**9+7
MAXN = 10**6+5
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD

def comb(n,r):
    r = min(r,n-r)
    ret = 1
    for i in range(r):
        ret *= (n-i)
        ret *= inv[i+1]
    ret %= MOD
    return ret

ans = 0
a = comb(r1+c1-1, r1)
b = comb(r1+c2, r1)
for r in range(r1,r2+1):
    a *= (r+c1) * inv[r+1]
    b *= (r+c2+1) * inv[r+1]
    ans += b-a
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

def inv(v, mod):
    return pow(v, mod-2, mod)
def main():
    r1, c1, r2, c2 = rip()

    MM = int(2e6+10)
    fact = [0] * MM
    finv = [0] * MM
    fact[0] = 1
    finv[0] = 1
    mod = int(1e9) + 7
    for i in range(1,MM): fact[i] = (fact[i-1] * i % mod)
    finv[MM-1] = inv(fact[MM-1], mod)
    for i in reversed(range(1,MM-1)):
        finv[i] = finv[i + 1] * (i + 1) % mod
    def sum(r, c):
        #[0, r) * [0, c)
        ret = 0
        for i in range(r):
            ret += fact[i + 1 + c - 1] * finv[i + 1] * finv[c - 1] % mod
        return ret
    ans = 0
    ans += sum(r2 + 1, c2 + 1)
    ans -= sum(r2 + 1, c1)
    ans -= sum(r1, c2 + 1)
    ans += sum(r1, c1)
    ans %= mod
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

from scipy.misc import comb

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# MOD = 998244353


R1, C1, R2, C2 = list(map(int, sys.stdin.buffer.readline().split()))


# 解説
# ある要素に注目して残りを選ぶ数を数えると分かる
# ncr(n, r) == ncr(n-1,r) + (n-1,r-1)
# nhr(n, r) == sum([nhr(n-1,k) for k in range(r)])

# g(r, c) を f(i, j) (0<=i<=r, 0<=j<=c) の総和とすると
# g(R2, C2) - g(R1-1, C2) - g(R2, C1-1) + g(R1-1, C1-1)

def f(n, r):
    return comb(n + r, r, exact=True)


# @debug
def g(r, c):
    # ret = 0
    # for i in range(1, c + 2):
    #     ret += f(r, i)
    #     ret %= MOD

    # f(r,k) (k=[1,c+1]) の和
    return f(r + 1, c + 1) - f(r, 0)


ans = g(R2, C2) - g(R1 - 1, C2) - g(R2, C1 - 1) + g(R1 - 1, C1 - 1)
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def MI(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [LI() for _ in range(N)]
        return map(list, zip(*read_all))

#################

#0!~(n-1)!をmodしつつ求める
def fact_all(n,M=mod):
    f = [1]*n
    ans = 1
    for i in range(1,n):
        ans = (ans*i)%M
        f[i] = ans
    return f


#a!をmodしつつ求める
def fact(a,M=mod):
    ans = 1
    for i in range(2,a+1):
        ans = (ans*i)%M
    return ans


#互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]


#aの逆元(mod M)を求める（aとMは互いに素）
def mod_inv(a,M=mod):
    x = extgcd(a,M)[0]
    return (M+x%M)%M


#nCkをmodしつつ返す
def nCk(n,k,fact_list=[],inv_list=[],M=mod):
    if fact_list and inv_list:
        return (fact_list[n]*inv_list[k]*inv_list[n-k])%M
    else:
        x = fact(n,M)
        y1 = mod_inv(fact(k,M),M)
        y2 = mod_inv(fact(n-k,M),M)
        return (x*y1*y2)%M


def g(r,c):
    retval = 0
    for i in range(r+1):
        retval += nCk(i+c+1,c,fact_list,inv_list)
        retval %= mod
    return retval

r1,c1,r2,c2 = LI()
fact_list = fact_all(r2+c2+2)
inv_list = [mod_inv(f) for f in fact_list]

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 comb(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
MAXN=10**6*2+10
g1=[1, 1]
g2=[1, 1]
inverse=[0, 1]

for i in range(2, MAXN+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())
s1=comb(r2+c2+2, r2+1)
s2=comb(r1+c2+1, r1)
s3=comb(r2+c1+1, r2+1)
s4=comb(r1+c1, r1)
print(s1-s2-s3+s4)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce


def cmb(n, r):
    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


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


def g(r, c):
    return cmb(r + c + 2, r + 1) - 1


r1 -= 1
c1 -= 1

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

Submission status: Time Limit Exceeded

Solution code:
# http://drken1215.hatenablog.com/entry/2020/02/09/225000

class Calc:
    def __init__(self, *, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def factorial(self, n):
        return self.fact[n]


def main():
    mod = 10 ** 9 + 7

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

    cl = Calc(max_value=r2 + c2 + 1, mod=mod)

    ret = 0
    for r in range(r1, r2 + 1):
        ret += cl.combination(r + c2 + 1, r + 1)
        ret -= cl.combination(r + (c1 - 1) + 1, r + 1)
        ret %= mod

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#from scipy.special import comb
r1, c1, r2, c2 = map(int, input().split())
#mod = 1000000007
#hole = (comb(r2 + c2 + 2, r2 + 1, exact=True) - 1) % mod
#rect1 = (comb(r2 + c1 - 1 + 2, r2 + 1, exact=True) - 1) % mod
#rect2 = (comb(r1 - 1 + c2 + 2, r1, exact=True) - 1) % mod
#duplicate = (comb(r1 + c1, r1, exact=True) - 1) % mod
#ans = (hole - rect1 - rect2 + duplicate) % mod

p = 10 ** 9 + 7
N = 1010000*2  # N は必要分だけ用意する
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 cmb(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

hole = (cmb(r2 + c2 + 2, r2 + 1, p) - 1)
rect1 = (cmb(r2 + c1 - 1 + 2, r2 + 1, p) - 1)
rect2 = (cmb(r1 - 1 + c2 + 2, r1, p) - 1)
duplicate = (cmb(r1 + c1, r1, p) - 1)
ans = (hole - rect1 - rect2 + duplicate) % p
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#from scipy.special import comb
r1, c1, r2, c2 = map(int, input().split())
#mod = 1000000007
#hole = (comb(r2 + c2 + 2, r2 + 1, exact=True) - 1) % mod
#rect1 = (comb(r2 + c1 - 1 + 2, r2 + 1, exact=True) - 1) % mod
#rect2 = (comb(r1 - 1 + c2 + 2, r1, exact=True) - 1) % mod
#duplicate = (comb(r1 + c1, r1, exact=True) - 1) % mod
#ans = (hole - rect1 - rect2 + duplicate) % mod

p = 10 ** 9 + 7
N = 10 ** 6  * 2 + 100# N は必要分だけ用意する
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 cmb(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

hole = (cmb(r2 + c2 + 2, r2 + 1, p) - 1)
rect1 = (cmb(r2 + c1 - 1 + 2, r2 + 1, p) - 1)
rect2 = (cmb(r1 - 1 + c2 + 2, r1, p) - 1)
duplicate = (cmb(r1 + c1, r1, p) - 1)
ans = (hole - rect1 - rect2 + duplicate) % p
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb
r1, c1, r2, c2 = map(int, input().split())
mod = 1000000007
hole = (comb(r2 + c2 + 2, r2 + 1, exact=True) - 1) % mod
rect1 = (comb(r2 + c1 - 1 + 2, r2 + 1, exact=True) - 1) % mod
rect2 = (comb(r1 - 1 + c2 + 2, r1, exact=True) - 1) % mod
duplicate = (comb(r1 + c1, r1, exact=True) - 1) % mod
ans = (hole - rect1 - rect2 + duplicate) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def pasc(p, q):
    a = p + q - 2
    b = min(p-1, q-1) 
    x = 1
    y = 1
    for i in range(max(b, a-b)+1, a+1):
        y *= i
    for i in range(1, min(b, a-b)+1):
        x *= i
    return y // x

r1, c1, r2, c2 = list(map(int, input().split()))
print((pasc(r2+2, c2+2) - pasc(r1+1, c2+2) - pasc(r2+2, c1+1) + pasc(r1+1, c1+1)) % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

mod = 10 ** 9 + 7

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

mc = ModComb(r2 + c2 + 10)
def f(i, j):
    return mc.nCk(i + j, i)

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

Submission status: Time Limit Exceeded

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

  mod = 10**9+7

  fact = [1,1]
  finv = [1,1]
  inv = [0,1]

  for i in range(2,2*10**6+1):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)

  def nCr(n,r,mod):
      if (r < 0) or (n < r):
          return 0
      r = min(r, n - r)
      return fact[n]*finv[r]*finv[n-r]%mod

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

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7


def pow(a, b, mod):
    if b == 0:
        return 1
    if b == 1:
        return a
    if b % 2 == 0:
        return (pow(a, b // 2, mod) ** 2) % mod
    else:
        return (a * pow(a, b // 2, mod) ** 2) % mod


def inv(x, mod):
    return pow(x, mod - 2, mod)


MAX = 2 * 10 ** 6 + 3
l = [1] * MAX
for i in range(1, MAX):
    l[i] = (l[i - 1] * i) % mod


def f(r, c):
    return (l[r + c] * inv(l[r], mod) * inv(l[c], mod)) % mod


def g(r, c):
    if r < 0 or c < 0:
        return 0
    ans = 0
    for i in range(r + 1):
        ans += f(i + 1, c)
    return ans % mod


r1, c1, r2, c2 = map(int, input().split())
print(((g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)) % mod + mod) % mod)

Submission status: Time Limit Exceeded

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

# 求めるものは
# sum[i,r1,r2]sum[j,c1,c2] f(i, j) ・・・ (1)
# g(x, y) = sum[i,0,x]sum[j,0,y](i+j)choose(i) とすると
# (1) = g(r2, c2) - g(r2, c1-1) - g(r1-1, c2) + g(r1-1, c1-1)
# と変形できる
# ここでsum[j,0,y](i+j)choose(i) = (i+y+1)choose(i+1)と変形できる
# これ解けた人って上記の変形を知識として知っていたんですか？その場で算出したんですか？後者ならすごすぎる・・・。
# 詳細はけんちょんさんのブログが凄くわかりやすいです
# よってg(x, y) = sum[i,0,x](i+y+1)choose(i+1)と変形できる

fac = [1]
inv = [1]
for i in range(1, r2 + c2 + 10) :
  fac.append(fac[-1] * i % mod)
  inv.append(pow(fac[-1], mod - 2, mod))

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

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

ret = g(r2, c2) - g(r2, c1-1) - g(r1-1, c2) + g(r1-1, c1-1)
ret %= mod

print(ret)

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 g(x, y):
    return ((y+2) * modcmb(x+y+2, x, MOD) - (x+1)) * pow(x+1, MOD-2, MOD)


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

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

    print(ans)


if __name__ == "__main__":
    main()