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:
r1, c1, r2, c2 = map(int,input().split())
s = [1]*(c2+1)
t = 0
for x in range(1,r2+1):
  for y in range(1,c2+1):
    s[y] = (s[y]+s[y-1])%(10**9+7)
  if x >= r1:
    t = (t+sum(s[c1:(c2+1)]))%(10**9+7)
print(t)

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

print(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:
import math
r1,c1,r2,c2 = map(int,input().split())

def comb(x, y):
    return math.factorial(x+y) // (math.factorial(x)*math.factorial(y))

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

print(ans%(1000000007))

Submission status: Time Limit Exceeded

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

import itertools
ans=0
for i in range(r1,r2+1):
    for j in range(c1,c2+1):
        ans+= len(list(itertools.combinations(range(i+j),i)))

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

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d= 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
M = 10 ** 7  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, M + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

cnt = 0
for i in range(a,c+1,1):
    for j in range(b,d+1,1):
        cnt += cmb(i+j,min(i,j),p)
print(cnt%p)

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 - 1, LARGE)
        res_right = ncr * (2 * 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 * (2 * pow2 - 1)
            res_right %= LARGE

        # go away for up
        ncr = 1
        pow2 = pow(2, r - 1, LARGE)
        res_up = ncr * (2 * 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 * (2 * 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:
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 = 2*10**6+2
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

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

Submission status: Time Limit Exceeded

Solution code:
r_1,c_1,r_2,c_2=map(int,input().split())
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 = 2*10**6
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 )
s=0
for r in range(r_1,r_2+1):
  for c in range(c_1,c_2+1):
    s+=cmb(r+c,c,mod)
print(s%(10**9+7))

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
finv = [1]*M
p = 1
for i in range(1, M):
    p = p*i%mod
    f[i] = p
    finv[i] = pow(p, mod-2, mod)

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:
import math

memo = {}


def frc(r, c):
    n = r + c
    r = c
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def get_cache(r, c):
    if r in memo and c in memo[r]:
        return memo[r][c]
    else:
        return None


def set_cache(r, c, val):
    if r in memo:
        memo[r][c] = val
    else:
        memo[r] = {c: val}


def totalf(i, j):
    c = get_cache(i, j)
    if c is not None:
        return c

    cache_i = get_cache(i - 1, j)
    cache_j = get_cache(i, j - 1)
    if cache_i is not None:
        return cache_i * (i + j) // i
    if cache_j is not None:
        return cache_j * (i + j) // j

    raise ValueError('hoge')


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

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

    total = 0

    set_cache(r1, c1, frc(r1, c1))

    for i in range(r1, r2 + 1):
        for j in range(c1, c2 + 1):
            v = totalf(i, j)
            set_cache(i, j, v)
            total += v

    print(total % div)


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 - 1, LARGE)
        res_right = ncr * (2 * 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 * (2 * pow2 - 1)
            res_right %= LARGE

        # go away for up
        ncr = 1
        pow2 = pow(2, r - 1, LARGE)
        res_up = ncr * (2 * 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 * (2 * 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:
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)


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

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

Submission status: Time Limit Exceeded

Solution code:
r1, c1, r2, c2 = map(int,input().split())
s = [1]*(c2+1)
t = 0
for x in range(1,r2+1):
  for y in range(1,c2+1):
    s[y] = (s[y]+s[y-1])%(10**9+7)
    if x >= r1 and y >= c1:
      t = (t+s[y])%(10**9+7)
print(t)

Submission status: Time Limit Exceeded

Solution code:
r1, c1, r2, c2 = list(map(int, input().split()))
s = 0
n = r2 + c2
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):
    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()
for i in range(r1, r2 + 1):
    for j in range(c1, c2 + 1):
        s += comb(i + j, j)
        s %= mod
print(s)

Submission status: Time Limit Exceeded

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

#O(10**12) orz

from scipy.misc import comb
mod=10**9+7
tret=0
for i in range(r1,r2+1):
    for j in range(c1,c2+1):
        # print(i,j)
        tret+=comb(i+j,i,exact=True)
        tret%=mod
        
print(tret)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial


m = 1000000007


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


def F(r, c):
    path = (factorial(r + c) % m) * pow(factorial(r) * factorial(c), m - 2, m) % m
    return path


ans = 0
for i in range(r1, r2 + 1):
    for j in range(c1, c2 + 1):
        ans = (ans + F(i, j)) % m
print(ans)

Submission status: Time Limit Exceeded

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

dp = [[float("inf")]*(r2+1) for _ in range(c2+1)]
for i in range(r2+1):
    dp[0][i] = 1
for i in range(c2+1):
    dp[i][0] = 1
for i in range(1,c2+1):
    for j in range(1,r2+1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]

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

# print(dp)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
a, b, c, d = map(int, input().split())
l = [[0 for i in range(d + 1)] for j in range(c + 1)]
ans = 0
for i in range(c + 1):
    for j in range(d + 1):
        if i == 0 and j == 0:
            l[i][j] = 0
        elif i == 0:
            l[i][j] = 1
        elif j == 0:
            l[i][j] = 1
        else:
            l[i][j] = l[i - 1][j] + l[i][j - 1]
            if i >= a and j >= b:
                ans += l[i][j]
print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
r1, c1, r2, c2 = map(int,input().split())
s = [1]*(c2+1)
t = 0
for x in range(1,r2+1):
  for y in range(1,c2+1):
    s[y] += s[y-1]
    s[y] = s[y]%(10**9+7)
  if x >= r1:
    t += sum(s[c1:(c2+1)])
    t = t%(10**9+7)
print(t)

Submission status: Time Limit Exceeded

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
sum = 0
r1, c1, r2, c2 = input().split(" ")
r1 = int(r1)
c1 = int(c1)
r2 = int(r2)
c2 = int(c2)
for r in range(r1, r2+1):
  for c in range(c1, c2+1):
    a = comb(r+c,r)
    sum += a
    
print(sum)

Submission status: Time Limit Exceeded

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

max_r = max(r1, r2)
max_c = max(c1, c2)


dp = [ 1 for c in range(max_c + 1)]


myans = 0
for r in range(1, max_r+1):
    dp[0] = 1
    for c in range(1, max_c+1):
        #print(c,dp[c-1], dp[c] )
        dp[c] = dp[c-1] +dp[c]
        if r1 <= r <= r2 and c1<= c <= c2:
            myans += dp[c]
            #print(r,c,myans)
    #print(dp)
print(myans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
r1, c1, r2, c2 = map(int,input().split())
s = [1]*(c2+1)
t = 0
for x in range(1,r2+1):
  for y in range(1,c2+1):
    s[y] += s[y-1]
  if x >= r1:
    t += sum(s[c1:(c2+1)])
    t = t%(10**9+7)
print(t)

Submission status: Time Limit Exceeded

Solution code:
class combnk_mod(object):
    # pが素数かつaとpが互いに素であるとき
    # フェルマーの小定理より以下が成り立つ.
    # 1 / a = a ** (p - 2) (mod p)
    # これを使って (1 / k!) mod p を計算する.
    def __init__(self, maxn, p):
        self.maxn = maxn
        self.p = p
        self.x = [1] # 分母にあたる数 1 / n! mod p
        self.y = [1] # 分子にあたる数. n! mod p
        for i in range(1, self.maxn + 1):
            self.x.append(self.x[-1] * pow(i, self.p - 2, self.p) % self.p)
            self.y.append(self.y[-1] * i % self.p)

    def combnk(self, n, k):
        if n < k:
            return 0
        return (self.x[n - k] * self.x[k] * self.y[n]) % self.p

r1, c1, r2, c2 = map(int, input().split())
MOD = 10 ** 9 + 7
C = combnk_mod(r2 + c2, MOD)
ans = 0
for r in range(r1, r2 + 1):
    for c in range(c1, c2 + 1):
        ans += C.combnk(r + c, r)
        ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

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

def nCr(n,r):
    return fact[n] * ifact[r] * ifact[n-r] % MOD

def f(r,c):
    temp = [nCr(k,c) for k in range(c+1,r+c+2)]
    return sum(temp) % MOD
    
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]

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

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7


def nCr(n, r):
    num = den = 1
    for i in range(r):
        num = num * (n - i)
        den = den * (i + 1)
    return num // den


def hockey(n, m):
    # sum i=0 to m of nCr(n + i, i) == nCr(n + m + 1, m)
    return nCr(n + m + 1, m)


if False:

    def f(r, c):
        return nCr(r + c, c)

    tot = 0
    for r in range(r1, r2 + 1):
        innerLoopSum = 0
        for c in range(c1, c2 + 1):
            innerLoopSum += f(r, c)
        # Via hockey stick identity
        assert innerLoopSum == nCr(r + c2 + 1, c2) - nCr(r + c1 - 1 + 1, c1 - 1)
        assert innerLoopSum == nCr(r + c2 + 1, r + 1) - nCr(r + c1, r + 1)
        tot += innerLoopSum
    print(tot)
    
    tot1 = 0
    for r in range(r1 + 1, r2 + 2):
        tot1 += nCr(r + c2, r)
    assert tot1 == hockey(c2, r2 + 1) - hockey(c2, r1)
    tot2 = 0
    for r in range(r1 + 1, r2 + 2):
        tot2 += nCr(r + c1 - 1, r)
    assert tot2 == hockey(c1 - 1, r2 + 1) - hockey(c1 - 1, r1)
    print((tot1 - tot2) % MOD)
else:
    tot1 = hockey(c2, r2 + 1) - hockey(c2, r1)
    tot2 = hockey(c1 - 1, r2 + 1) - hockey(c1 - 1, r1)
    print((tot1 - tot2) % MOD)

Submission status: Time Limit Exceeded

Solution code:
PRIME = 10 ** 9 + 7

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

fac = [1 for i in range(maximum + 1)]
finv = [1 for i in range(maximum + 1)]
inv = [1 for i in range(maximum + 1)]

for i in range(2, maximum + 1):
    fac[i] = fac[i - 1] * i % PRIME
    inv[i] = PRIME - inv[PRIME % i] * (PRIME // i) % PRIME
    finv[i] = finv[i - 1] * inv[i] % PRIME

ans = 0
for x in range(r1, r2 + 1):
  for y in range(c1, c2 + 1):
    ans = (ans + fac[x + y] * (finv[x] * finv[y] % PRIME) % PRIME) % PRIME

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
import math

MOD = 10**9 + 7


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


def pathes(x, y):
    # xf = None
    # yf = None
    # xyf = None
    # temp = 1
    # for i in range(1, x + y + 1):
    #     temp *= i % MOD
    #     if i == x:
    #         xf = temp
    #     if i == y:
    #         yf = temp
    #     if i == x + y:
    #         xyf = temp
    xf = math.factorial(x) % MOD
    yf = math.factorial(y) % MOD
    xyf = math.factorial(x + y) % MOD

    return xyf * modinv(xf * yf % MOD, MOD)


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

    a = (pathes(r1, c1) - 1) % MOD
    b = (pathes(r1, c2 + 1) - 1) % MOD
    c = (pathes(r2 + 1, c1) - 1) % MOD
    d = (pathes(r2 + 1, c2 + 1) - 1) % MOD

    print((d - c - b + a) % MOD)


main()

Submission status: Time Limit Exceeded

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

r = (r2 + 1)
l = (r1)
ans = 0

for i in range(0, c2):
    r *= (r2 + 1 + (i + 1))
    r *= pow((i + 2), MOD - 2, MOD)
    l *= (r1 + (i + 1))
    l *= pow((i + 2), MOD - 2, MOD)
    r %= MOD
    l %= MOD
    if i >= c1 - 1:
        ans += r
        ans -= l
    ans %= MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
A = list(map(int, input().split()))
s=0
def cor(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact
for i in range(A[0],A[2]+1):
    s=s+((A[3]+1)*cor(A[1])*cor(A[3]+1+i)-A[1]*cor(A[3]+1)*cor(A[1]+i))//((i+1)*cor(A[1])*cor(A[3]+1)*cor(i))
print(s%(10**9))

Submission status: Time Limit Exceeded

Solution code:
import math

def comb(r, c):
    return math.factorial(r+c) // (math.factorial(r) * math.factorial(c))
  

data = list(map(int, input().split()))

const = 10**9 + 7

answer = 0
for r in range(data[0], data[2]+1):
  for c in range(data[1], data[3]+1):
    answer += comb(r, c) % const

print(answer % const)

Submission status: Time Limit Exceeded

Solution code:
import math

def comb(r, c):
    return math.factorial(r+c) // (math.factorial(r) * math.factorial(c))
  

data = list(map(int, input().split()))

const = 10**9 + 7

answer = 0
for r in range(data[0], data[2]+1):
  for c in range(data[1], data[3]+1):
    answer += comb(r, c) % const

print(answer)

Submission status: Time Limit Exceeded

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


    # 階乗 & 逆元計算
    factorial = [1]
    inverse = [1]
    for i in range(1, r2 + c2 + 10):
        factorial.append(factorial[-1] * i % MOD)
        inverse.append(pow(factorial[-1], MOD - 2, MOD))


    # 組み合わせ計算
    def nCr(n, r):
        if n < r or r < 0:
            return 0
        elif r == 0:
            return 1
        return factorial[n] * inverse[r] * inverse[n - r] % MOD


    ans = 0
    for r in range(r1, r2 + 1):
        ans += ((nCr(r + c2 + 1, r + 1) % MOD) - (nCr(r + c1, r + 1) % MOD)) % MOD
        ans %= MOD

    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d = map(int,input().split())
if c > d:
    a,b = b,a
    c,d = d,c


dp = [[1 for i in range(d+1)] for j in range(c+1)]
dp[0][0] = 0

mod = 10**9+7
#print(dp)
ans = 0
for i in range(1,c+1):
    for j in range(i,d+1):
        dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod
        if j<=c:
            dp[j][i] = dp[i][j]
        # if i >= a and j >= b:
        #     ans += dp[i][j]
        #     if i>=b and j >=a:
        #         ans += dp[i][j]

# print(ans%mod)


ans = 0
for i in range(a,c+1):
    for j in range(b,d+1):
        ans += dp[i][j]
        ans %=mod
        #print(dp[i+1][j+1])
#print(dp)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
r1,c1,r2,c2 = map(int,input().split())
mod = 10**9+7
fact = [1]*(3*10**6)

for n in range(3*10**6-1):
    fact[n+1] = ((n+1)*fact[n])%mod

def comb(n,k):
    return (fact[n]*pow(fact[k],mod-2,mod)*pow(fact[n-k],mod-2,mod))%mod

def fs(r,c):
    res = 0
    for i in range(1,c+1):
        res += comb(i+1+r,r)-1
    return res

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

Submission status: Time Limit Exceeded

Solution code:
"""
F
"""
import sys
input=sys.stdin.readline
mod=10**9+7
MAX=2*10**6+100

g1=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    
def cmb(n,r):
    return (g1[n]*pow(g1[r],mod-2,mod)%mod)*pow(g1[n-r],mod-2,mod)%mod

r1,c1,r2,c2=map(int,input().split())
if r2-r1<c2-c1:
    c1,r1=r1,c1
    c2,r2=r2,c2

S=cmb(r1+c1,r1)
ans=S
table1=[]
table2=[]
num1=c1+1
num2=r1+1
for i in range(c2-c1):
    S=((2*S+cmb(num1+i+r1-1,r1-1))%mod+cmb(num2+i+c1-1,c1-1))%mod
    ans=(ans+S)%mod  
    
num1=r1
num2=r1+c2-c1+1
for i in range(r2-(r1+c2-c1)):
    S=((2*S-cmb(num1+i+c2,c2))%mod+cmb(num2+i+c1-1,c1-1))%mod
    ans=(ans+S)%mod  
    
num1=c1
num2=r2-(c2-c1)
for i in range(c2-c1):
    S=((2*S-cmb(num1+i+r2,r2))%mod-cmb(num2+i+c2,c2))%mod
    ans=(ans+S)%mod  

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
 
arr = list(map(int,input().split()))
 
count = 0
for i in range(arr[0],arr[2]+1):
    for j in range(arr[1],arr[3]+1):
        count+=math.factorial(i+j) // (math.factorial(i) * math.factorial(j))
 
 
if (count < (10**9 + 7)):
  print(count)
else:
  print(count % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

MOD = 10**9 + 7


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


def pathes(x, y):
    xf = None
    yf = None
    xyf = None
    temp = 1
    for i in range(1, x + y + 1):
        temp *= i % MOD
        if i == x:
            xf = temp
        if i == y:
            yf = temp
        if i == x + y:
            xyf = temp

    return xyf * modinv(xf * yf % MOD, MOD)


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

    a = (pathes(r1, c1) - 1) % MOD
    b = (pathes(r1, c2 + 1) - 1) % MOD
    c = (pathes(r2 + 1, c1) - 1) % MOD
    d = (pathes(r2 + 1, c2 + 1) - 1) % MOD

    print((d - c - b + a) % MOD)


main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Feb  9 21:31:03 2020

@author: H_Hoshigi
"""
from scipy.misc import comb
#from scipy.special import comb

nCr_dict = {}
def combination(n, r):
    try:
        nCr_dict[(n-1, r)]
    except KeyError:
        nCr_dict[(n-1, r)] = comb(n-1, r, exact=True)
    else:
        pass
    pass
    try:
        nCr_dict[(n-1, r-1)]
    except KeyError:
        nCr_dict[(n-1, r-1)] = comb(n-1, r-1, exact=True)
    else:
        pass
    nCr_dict[(n, r)] = nCr_dict[(n-1, r)] + nCr_dict[(n-1, r-1)]
    return nCr_dict[(n, r)]

r1, c1, r2, c2 = map(int, input().split())
answer = 0
for i in range(r1, r2+1):
    for j in range(c1, c2+1):
        answer += combination(i+j, j)

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

Submission status: Time Limit Exceeded

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

#処理
X=[[-1 for i in range(c2+1)] for j in range(r2+1)]
#内部関数
def f_1(r,c):
    if r==0 or c==0:
        X[r][c]=1
        return 1
    if X[r][c]==-1:
        try :
            if X[c][r]!=-1:
                X[r][c]=X[c][r]
                return X[r][c]
        except:
            pass
        X[r][c]=f_1(r-1,c)+f_1(r,c-1)
        return X[r][c]
    else:
        return X[r][c]
    
for i in range(r2+1):
    for j in range(c2+1):
        f_1(i,j)
#print(X)
t=0
for i in range(r1,r2+1):
    t+=sum(X[i][c1:c2+1])
print(t%(10**9+7))

Submission status: Time Limit Exceeded

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

r1,c1,r2,c2=map(int,input().split())
total=0
for r in range(r1,r2+1):
  for c in range(c1,c2+1):
    total+=combinations_count(r+c,r)%(10**9+7)
print(total%(10**9+7))