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: Runtime Error

Solution code:
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: Runtime Error

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


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: Runtime Error

Solution code:
r1,c1,r2,c2=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 = 10**6+5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

Submission status: Runtime Error

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 ** 6 + 1  # 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: Runtime Error

Solution code:
mod = 10**9+7


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    # a*x+y*mod = 1
    return (mod+x % mod) % mod


max_num = 2*10**6+1
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

for i in range(2, max_num):
    fact[i] = fact[i-1] * i % mod
    ifact[i] = ifact[i-1] * inv(i, mod) % mod


def cmb(x, y):
    return fact[x] * ifact[y] * ifact[x-y] % mod


def solve(r, c):
    ans = 0
    for i in range(r+1):
        ans += cmb(c+i+1, c)
        ans %= mod
    return ans


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

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

print(ans)

Submission status: Runtime Error

Solution code:
r1,c1,r2,c2=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 = 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 )
print((cmb(c2+r2+2,c2+1,mod)-cmb(c2+r1+1,c2+1,mod)-cmb(c1+r2+1,c1,mod)+cmb(c1+r1,c1,mod)+mod)%mod)

Submission status: Runtime Error

Solution code:
mod = 10**9+7


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    # a*x+y*mod = 1
    return (mod+x % mod) % mod


max_num = 10**6+1
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

for i in range(2, max_num):
    fact[i] = fact[i-1] * i % mod
    ifact[i] = ifact[i-1] * inv(i, mod) % mod


def cmb(x, y):
    return fact[x] * ifact[y] * ifact[x-y] % mod


def solve(r, c):
    ans = 0
    for i in range(r+1):
        ans += cmb(c+i+1, c)
        ans %= mod
    return ans


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

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

print(ans)

Submission status: Runtime Error

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 ** 4
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: Runtime Error

Solution code:
import sys
from math import factorial

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
K = ir()
length = len(str(N))

def F(length, K, N):
    if length < K:
        return 0
    if K == 0:
        return 1
    if length == 1: #この時、Kも1
        return N
    ret = 0
    top = int(str(N)[0])
    if length-K >= 1:
        ret += factorial(length-1) // factorial(K) // factorial(length-K-1) * 9 ** K # 一個前まで    
    ret += factorial(length-1) // factorial(K-1) // factorial(length-K) * (top-1) * 9 ** (K-1) # 一桁目がtopより小さい数  
    # 一桁目がtopと同じ数
    if K > 1: 
        N = int(str(N)[1:])
        length = len(str(N))
        ret += F(length, K-1, N)
    else:
        ret += 1 # 2000のような数
    return ret

answer = F(length, K, N)
print(answer)

Submission status: Runtime Error

Solution code:
r1,c1,r2,c2=map(int,input().split())
a=r2-r1+1
b=c2-c1+1
m=max(a,b)
n=min(a,b)
mod=10**9+7
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a
def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod
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: Runtime Error

Solution code:
mod = 10**9+7


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    # a*x+y*mod = 1
    return (mod+x % mod) % mod


max_num = 2*10**5+1
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

for i in range(2, max_num):
    fact[i] = fact[i-1] * i % mod
    ifact[i] = ifact[i-1] * inv(i, mod) % mod


def cmb(x, y):
    return fact[x] * ifact[y] * ifact[x-y] % mod


def solve(r, c):
    ans = 0
    for i in range(r+1):
        ans += cmb(c+i+1, c)
        ans %= mod
    return ans


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

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

print(ans)

Submission status: Runtime Error

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

size = 101000*2
f_list = [1]*(size)
for i in range(1,size):
    f_list[i] = (f_list[i-1]*i)%MOD

def func(r,c):
    return (f_list[r+c]*pow(f_list[r],MOD-2,MOD)*pow(f_list[c],MOD-2,MOD))

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

Submission status: Runtime Error

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 ** 6  # 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+c1+1,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: Runtime Error

Solution code:

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

mod = 10 ** 9 + 7
MAX = (10**6)*2 + 1
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

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



def cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()

ans = 0
for c in range(c1, c2+1):
    ans += ((r2+1)*fac[r1]*fac[c+r2+1]-r1*fac[r2+1]*fac[c+r1])*finv[c]*finv[r1]*finv[r2+1]*inv[c+1]
    ans %= mod
    
print(ans)

Submission status: Runtime Error

Solution code:
r1,c1,r2,c2=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 = 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 )
print(cmb(c2+r2+2,c2+1,mod)-cmb(c2+r1+1,c2+1,mod)-cmb(c1+r2+1,c1,mod)+cmb(c1+r1,c1,mod))

Submission status: Runtime Error

Solution code:

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

mod = 10 ** 9 + 7
MAX = 10**6+10
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

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



def cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()

ans = 0
for c in range(c1, c2+1):
    ans +=((r2+1)*fac[r1]*fac[c+r2+1]-r1*fac[r2+1]*fac[c+r1])*finv[c]*finv[r1]*finv[r2+1]*inv[c+1]
    ans %= mod
    
print(ans)

Submission status: Runtime Error

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

memo = {}
def route(r, c):
  if r == 0 or c == 0:
    return 1
  if (r, c) not in memo:
    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: Runtime Error

Solution code:

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

mod = 10 ** 9 + 7
MAX = 10**6+10
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

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



def cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()

ans = 0
for c in range(c1, c2+1):
    tmp = ((r2+1)*fac[r1]*fac[c+r2+1]-r1*fac[r2+1]*fac[c+r1])*finv[c]*finv[r1]*finv[r2+1]*inv[c+1]
    ans += tmp
    
ans %= mod
print(ans)

Submission status: Runtime Error

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**5*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: Runtime Error

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] * max(r, c)
        for i in range(1, max(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: Runtime Error

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

Submission status: Runtime Error

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] * max(r + c)
        for i in range(1, max(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: Runtime Error

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
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

ans = 0

while r2 != r1 or c2 != c1:
    print(r1,c1,r2,c2)
    num = min(r2-r1,c2-c1)
    ans += cmb(r1+c1,min(c1,r1),mod)
    if num != 0:
        ans += cmb(r1+c1+2*num,min(c1,r1)+num,mod)*(num+1)
    ans %= mod
    if c2-c1 == 0:
        r1 += 1
    elif r2-r1 == 0:
        c1 += 1
    else:
        if r2-r1 > c2-c1:
            r1 = min(r2,r1+num+1)
        elif r2-r1 < c2-c1:
            c1 = min(c2,c1+num+1)
        else:
            r1 =r2
            c1 += c2
print(ans)

Submission status: Runtime Error

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

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

for i in range(c2):
    for j in range(r2):
        if i == 0 or j == 0:
            dp[i][j] = 1
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

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

print(ans)

Submission status: Runtime Error

Solution code:
def cmb(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


mod = 10**9 + 7

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

first = cmb(r1+c1, r1)
ans = 0
d = r2 - r1
count = 0
for i in range(c1, c2+1):
    count += 1
    tmp = 0
    tmp = ((first + first + (r1 * d)) * (d+1)) // 2

    tmp += (d * (d - 1)) // 2
    ans += tmp
    ans %= mod
    first = first * ((r1 + i) / i)
print(int(ans))

Submission status: Runtime Error

Solution code:
r1,c1,r2,c2=map(int,input().split())
Ans=0
def G(r,c):
	import math
	T=math.factorial(r+c)/(math.factorial(r)*math.factorial(c))
	return T

for n in range(r1,r2+1):
	for p in range(c1,c2+1):
		Ans+=G(n,p)
print(Ans)

Submission status: Runtime Error

Solution code:
from math import factorial
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = False
show_flg = True

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

# MOD 組み合わせ
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


def main():
    M = 10 ** 4
    r1, c1, r2, c2 = MI()
    n_points = (abs(r2 - r1) + 1) * (abs(c2 - c1) + 1)
    # print(n_points)

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

    # print(cmb(r2+c1, r2, MOD))
    # print(cmb(r1+c2, r1, MOD))
    # print(cmb(r1+c1, r1, MOD))
    if r2 - r1 == 1 or c2 - c1 == 1:
        a = math.factorial(3)
        b = cmb(r1+c1, r1, MOD)
        print(a * b + b)
    else:
        a = cmb(r2+c2+1-r1-c1, r2-r1, MOD)
        b = cmb(r1+c1, r1, MOD)
        print(a * b + b)
    # print((r2 + c2 - r1 - c1))
    # total = 2 ** (r2 + c2 - r1 - c1) % MOD
    # m = cmb(r2+c2+1, r2, MOD)
    # print(total * m % MOD)

    # for r2 in range(4):
    #     for c2 in range(4):
    #         print(r2, c2, cmb(r2+c2, r2, MOD))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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 = r+c
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: Runtime Error

Solution code:

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

mod = 10 ** 9 + 7
MAX = 10**6+10
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

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



def cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()

ans = 0
f = fac[r1+c1]*finv[r1]*finv[c1]
for r in range(r1,r2+1):
    for c in range(c1,c2+1):
       ans += fac[r+c]*finv[r]*finv[c]
       
ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
from math import factorial as f
def c(n,r):
  if n<r:
    return 0
  else:
    return f(n)//(f(n-r)*f(r))
a,b,c,d=map(int,input().split())
print(c(c-a+d-b,c-a))

Submission status: Runtime Error

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

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

ans=0
for i in range(r1,r2+1):
    ans+=cmb(i+c1-1,i)*cmb(r2-i+1+c2-c1+1,c2-c1+1)

for j in range(c1,c2+1):
    ans+=cmb(i+r1-1,i)*cmb(c2-i+1+r2-r1+1,r2-r1+1)

ans%=1000000007
ans-=1
print(ans)

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce

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


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

a=combinations_count(r1+c1, r1)
X=[combinations_count(c1+x, x) for x in range(r1+1, r2+1)]
Y=[combinations_count(r1+x, x) for x in range(c1+1, c2+1)]
KX=[x*(c2-c1)*(r2-x+1) for x in range(r1+1, r2+1)]
KY=[x*(r2-r1)*(c2-x+1) for x in range(c1+1, c2+1)]
NX=len(X)
NY=len(Y)
ans=a%Y
for i in range(NX):
    ans+=X[i]*KX[i]%Y
for i in range(NY):
    ans+=Y[i]*KY[i]%Y
print (ans%Y)

Submission status: Runtime Error

Solution code:
import math
r_1,c_1,r_2,c_2=input().split()
r_1=int(r_1)
r_2=int(r_2)
c_1=int(c_1)
c_2=int(c_2)

count=0
def total(r,c):
  return math.factorial(r+c)/(math.factorial(r)*math.factorial(c))
  
count+=total(r_1,c_1)
count+=total(r_1,c_2)
count+=total(r_2,c_1)
count+=total(r_2,c_2)

if count <(pow(10,9)+7):
	print(int(count))
else:
	print(int(count%(pow(10,9)+7)))

Submission status: Runtime Error

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

dp=[]
for i in range(r2+1):
  dp.append([0]*(c2+1))
#dp[0][0]=1
for r in range(r2+1):
  dp[r][0]=1
for c in range(c2+1):
  dp[0][c]=1

#print(dp)
for r in range(1,r2+1):
  for c in range(1,c2+1):    
    dp[r][c]=dp[r-1][c]+dp[r][c-1]
    
#print(dp)
answer=0
for r in range(r1,r2+1):
  for c in range(c1,c2+1):
    answer+=dp[r][c]
    answer%=MOD
    
print(answer)

Submission status: Runtime Error

Solution code:
#154 f
nCr = {}
def cmb(n, r):
    if r == 0 or r == n:
         return 1
    if r == 1:
        return n
    if (n,r) in nCr:
        return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


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

Submission status: Runtime Error

Solution code:
r1, c1, r2, c2 = map(int, input().split())
r1 += 1
c1 += 1
r2 += 1
c2 += 1
m = [[1] * r2]
l = [[0] * r2 for _ in range(c2 - 1)]
m.extend(l)
for i in range(c2):
    m[i][0] = 1
ans = 0
for i in range(1, c2):
    for j in range(1, r2):
        m[i][j] = m[i][j - 1] + m[i - 1][j]
        if r1 - 1 <= j <= r2 - 1 and c1 - 1 <= i <= c2 - 1:
            ans += m[i][j]
print(ans % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
x1, y1, x2, y2 = map(int,input().split())
mod = 10**9+7


T = [[1]*(x2+1) for i in range(y2+1)]

def ref(x,y):
    if x>y:
        return T[y][x]
    else:
        return T[x][y]

ans = 0
for i in range(1,y2+1):
    for j in range(i,x2+1):
        T[i][j] = (ref(i-1,j)+ref(i,j-1))%mod
        if x1<=i<=x2 and y1<=j<=y2:
            ans = (ans + T[i][j])%mod
        if i!=j and x1<=j<=x2 and y1<=i<=y2:
            ans = (ans + T[i][j])%mod
print(ans)