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

Solution (Python):
import sys
read = sys.stdin.read
mod = 10 ** 9 + 7
r1, c1, r2, c2 = map(int, read().split())

def prepare(n, MOD):

    
    f = 1
    factorials = [1]  
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    
    inv = pow(f, MOD - 2, MOD)
    
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


fac, finv = prepare(2 * 10**6 + 10, mod)


def comb(n, k, mod=mod, fac=fac, finv=finv):
    '''
    二項係数の計算

    Parameters
    n : int
        元集合
    k : int
        元集合から選択する数
    mod : int
        あまり
    fac : list
        階乗のリスト
    finv : list
        逆元のリスト

    Returns
    c : int
        nCkの組み合わせの数
    '''
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


answer = comb(r2 + c2 + 2, r2 + 1) - comb(r1 + c2 + 1, r1) - \
    comb(c1 + r2 + 1, c1) + comb(r1 + c1, r1)
answer %= mod
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline().rstrip

"""
まず一般に剰余込みでの組み合わせの計算。
n!, (n!)^{-1} mod pの値を配列にまとめておき、nCr = (n!)/(r!)((n-r)!)をO(1)で計算する。

max = (用意する配列の最大長)
mod = （剰余）

(n!)^{-1}の計算は¥Prod_i i^{-1}を計算して求める。
i^{-1} mod pの計算はフェルマーの小定理より、mod pにおいて
0 = p = (p // i) * i + (p % i)
0 = (p // i) + (p % i) * i^{-1}
i^{-1} = -(p // i) * (p % i)^{-1}
"""

max = 10**6 * 2 + 3 
mod = 10**9+7
fact = [1, 1] 
factinv = [1, 1] 
inv = [0, 1] 

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

def cmb(n, r):
    if r < 0 or r > n:
        return 0
    else:
        r = min(r, n-r)
        return fact[n] * factinv[r] * factinv[n-r] % mod


"""
いよいよ本題。
まずは¥Sum_{0¥le i¥le x, 0¥le j¥le y} _{i+j}C_iを計算する。
実際今回の問題は容易にこれに帰着可能。

¥Sum_{0¥le i¥le x, 0¥le j¥le y} _{i+j}C_i
    = ¥Sum_i (¥Sum_j _{i+j}C_i)
    = ¥Sum_i {(T+1)^i + (T+1)^{i+1} + ... + (T+1)^{i+y})のT^iの係数}
    = ¥Sum_i {¥frac{(1+T)^{i+y+1} - (1+T)^i}{T}のT^iの係数}
    = ¥Sum_i _{i+y+1}C_{i+1}

    = ¥Sum_i _{i+y+1}C_y
    = _{y+1}C_y + _{y+2}C_y + ... + _{y+x+1}C_y
    = {(1+T)^{y+1} + (1+T)^{y+2} + ... (1+T)^{y+x+1}のT^yの係数}
    = {¥frac{(1+T)^{x+y+2} - (1+T)^{y+1}}{T}のT^yの係数}
    = _{x+y+2}C_{y+1} - 1
"""
r1, c1, r2, c2 = map(int, input().split())
a = cmb(r2+c2+2, c2+1) - 1
b = cmb(r1+c2+1, c2+1) - 1
c = cmb(r2+c1+1, r2+1) - 1
d = cmb(r1+c1, r1) - 1
ans = a - b - c + d
print(ans % mod)

Solution (Python):

from operator import mul
from functools import reduce

r1, c1, r2, c2 = [int(i) for i in input().split()]
mod = 10**9 + 7


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

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

def f(rr,cc):
    
    
    
    
    return (fact[rr+cc+2]%mod * pow(fact[rr+1]*fact[cc+1], mod-2, mod)) % mod -1

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

Solution (Python):
r1,c1,r2,c2=map(int,input().split())
MOD=10**9+7
idx=r2+c2+2
perm=[1]*(idx+1)
perm_inv=[1]*(idx+1)
for i in range(1,idx+1):
    perm[i]=perm[i-1]*i
    perm[i]%=MOD
def inv_mod(a):
  return pow(a,MOD-2,MOD)
perm_inv[-1]=inv_mod(perm[-1])
for i in range(idx-1,-1,-1):
    perm_inv[i]=perm_inv[i+1]*(i+1)
    perm_inv[i]%=MOD
def comb(i,j):
    buf=perm[i+j+2]
    buf*=perm_inv[i+1]
    buf%=MOD
    buf*=perm_inv[j+1]
    buf%=MOD
    return buf
res=comb(r2,c2)
res-=comb(r2,c1-1)
res-=comb(r1-1,c2)
res+=comb(r1-1,c1-1)
print(res%MOD)

Solution (Python):
r1,c1,r2,c2=map(int,input().split())
MOD=10**9+7
idx=r2+c2+3
perm=[1]*(idx+1)
for i in range(1,idx+1):
    perm[i]=perm[i-1]*i
    perm[i]%=MOD
def inv_mod(a):
  return pow(a,MOD-2,MOD)

def comb(n,m,p=10**9+7):
    if n < m : return 0
    if n < 0 or m < 0:return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p
def g(i,j):
    return comb(i+j+2,i+1,MOD)
def s(n,m):
    return comb(n+m+2, m+1, MOD)
res=g(r2,c2)-g(r2,c1-1)-g(r1-1,c2)+g(r1-1,c1-1)
res%=MOD

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

Solution (Python):
m = 1000000007


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

nf = 10 ** 6 * 2 + 100
fact = [0] * (nf + 1)
fact[0] = 1
for i in range(nf):
    fact[i + 1] = fact[i] * (i + 1) % m


def F(r, c):
    path = (fact[r + c + 2] % m) * pow(fact[r + 1] * fact[c + 1], m - 2, m) % m
    return path - 1


r1 -= 1
c1 -= 1

ans = F(r2, c2)
ans -= F(r1, c2)
ans -= F(r2, c1)
ans += F(r1, c1)
ans = ans % m

print(ans)

Solution (Python):


mod = 10**9+7

def chs(a,b):
    a+=1;b+=1
    a+=b
    res = 1
    for i in range(a,a-b,-1):
        res *= i 
        res%=mod
    for i in range(1,b+1):
        res *= rev[i]
        
        res %=mod 
    return res


r1,c1,r2,c2 = map(int, input().split( ))
r1 -=1;c1-=1
if c2>r2:
    r2,c2 = c2,r2
    r1,c1= c1,r1
rev = [pow(i,mod-2,mod) for i in range(c2+5)]
ans = chs(r2,c2)-chs(r1,c2)-chs(r2,c1)+chs(r1,c1)
ans%=mod


print(ans)

Solution (Python):
r1,c1,r2,c2=map(int, raw_input().split())

N=r2+c2+1
mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, N+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod

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

print ans

Solution (Python):
r1,c1,r2,c2=map(int, raw_input().split())

N=r2+c2+1
mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, N+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod

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

print ans

Solution (Python):
MOD = 10**9+7
p= []
rp = []

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

def f(r,c):
    return (p[r+c] * rp[r] * rp[c]) % MOD

def extgcd(a,b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2]//w[2]
        ra = w
        wa = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = ra
        w = wa
    
    return [w[0], w[1]]

def mod_inv(a,m):
    x = extgcd(a, m)[0]
    return (m+x%m)%m

r1,c1, r2,c2 = map(int,input().split())
p = [0 for _ in range(r2+c2+3)]
rp = [0 for _ in range(max(r2,c2)+2)]

p[0] = 1
p[1] = 1
rp[0] = 1
rp[1] = 1
for i in range(2,c2+r2+3):
    p[i] = (p[i-1] * i) % MOD

for i in range(2,max(r2,c2)+2):
    rp[i] = mod_inv(p[i], MOD)

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

Solution (Python):
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 LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))




def fact_all(n,M=mod):
    f = [1]*(n+1)
    ans = 1
    for i in range(1,n+1):
        ans = (ans*i)%M
        f[i] = ans
    return f


def fact_inv_all(fact_all,M=mod):
    N = len(fact_all)
    finv = [0]*N
    finv[-1] = pow(fact_all[-1],M-2,M)
    for i in range(N-1)[::-1]:
        finv[i] = finv[i+1]*(i+1)%M
    return finv


def nCk(n,k,fact_list=[],inv_list=[],M=mod):
    
    def fact(a,M=mod):
        ans = 1
        for i in range(2,a+1):
            ans = (ans*i)%M
        return ans

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

    
    def mod_inv(a,M=mod):
        x = extgcd(a,M)[0]
        return (M+x%M)%M
    
    if fact_list and inv_list:
        return (((fact_list[n]*inv_list[k])%M)*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)%M*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+1)
inv_list = fact_inv_all(fact_list)

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

Solution (Python):
r1, c1, r2, c2 = map(int, input().split())
mod = int(1e+9) + 7
def inved(x):
  a, b, c, d, k, l = 1, 0, 0, 1, x, mod
  while l != 0:
    a, b, c, d = c, d, a - c * (k // l), b - d * (k // l)
    k, l = l, k % l
  return a % mod
frac = [1]
for i in range(r2 + c2 + 2):
  frac.append(((i+1) * frac[i]) % mod)
fracr2c2 = frac[r2 + c2 + 2]
fracr1c2 = frac[r1 + c2 + 1]
fracr2c1 = frac[r2 + c1 + 1]
fracr1c1 = frac[r1 + c1]
fracr2 = frac[r2 + 1]
fracr1 = frac[r1]
fracc2 = frac[c2 + 1]
fracc1 = frac[c1]
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)

Solution (Python):
from operator import mul
from functools import reduce

def comb(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 = 3 * 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 = [int(i) for i in input().split()]
 
def calc(r, c):
    a = comb(r + c + 2, r + 1, mod) - 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)
result %= mod
if result < 0:
  result += mod
print(result)

Solution (Python):
import sys
import socket

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('f1.in')


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


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


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


def read_str():
    return input()


M = 10 ** 9 + 7
f = [1] * (2*10**6+4)
for i in range(1, 2*10**6+3):
  f[i] = f[i-1] * i
  f[i] %= M


def g(r, s):
  res = 1
  frs = f[r+s+2]
  fs = f[s+1]
  fr = f[r+1]

  res *= pow(fr, M-2, M)
  res *= pow(fs, M-2, M)

  res *= frs
  res %= M
  return res


def main():
    r1, c1, r2, c2 = read_int_list()
    res = 0
    res += g(r2, c2) - g(r2, c1-1) - g(r1-1, c2) + g(r1-1, c1-1)
    res %= M
    print(res)


main()

Solution (Python):
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)

Solution (Python):
MOD = 10**9+7
def inv_mod(a,p=MOD):
    def inv_mod_sub(a,p):
        if a == 1:
            return 1,0
        else:
            d,r = p//a,p%a
            x,y = inv_mod_sub(r,a)
            return y-d*x,x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n,k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD

def f(a,b):
  return comb_mod(a+b,b)

r1,c1,r2,c2 = map(int,input().split())
f_mod=[1]*(3*10**6)
f_mod_inverse=[1]*(3*10**6)
for i in range(1,3*10**6):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD
print((f(r2+1,c2+1)-f(r1,c2+1)-f(r2+1,c1)+f(r1,c1))%MOD)

Solution (Python):

r_1, c_1, r_2, c_2 = map(int, input().split())


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)

Solution (Python):
import sys
import numpy as np

sys.setrecursionlimit(10 ** 7)

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




def cumprod(arr, MOD):
    L = len(arr)
    Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]
        arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]
        arr[n] %= MOD
    return arr.ravel()[:L]


def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv


MOD = 10 ** 9 + 7
U = 10**6 * 2 + 10
fact, fact_inv = make_fact(U, MOD)


def mod_comb_k(n, k, mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n - k] % mod


def calc_rc(r, c):
    a = mod_comb_k(r + c + 2, r + 1, MOD)
    b = 1
    return a-b


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

print(ans)

Solution (Python):

import sys
INF = float("inf")

MOD = 1000000007  


class Combination(object):

    def __init__(self, N, mod=10**9+7):
        fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
        fac[:2] = 1, 1
        finv[:2] = 1, 1
        inv[1] = 1
        for i in range(2, N+1):
            fac[i] = fac[i-1]*i % mod
            inv[i] = -inv[mod % i]*(mod//i) % mod
            finv[i] = finv[i-1]*inv[i] % mod
        self.N = N
        self.MOD = mod
        self.fac = fac
        self.finv = finv
        self.inv = inv

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


def solve(r: "List[int]", c: "List[int]"):

    cmb = Combination(r[1]+c[1]+2, mod=MOD)

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

    ans = g(r[1], c[1])-g(r[0]-1, c[1])-g(r[1], c[0]-1)+g(r[0]-1, c[0]-1)
    print(ans % MOD)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    r = [int()] * (2)  
    c = [int()] * (2)  
    for i in range(2):
        r[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(r, c)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
INF = float("inf")

MOD = 1000000007  


class Combination(object):

    def __init__(self, N, mod=10**9+7):
        fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
        fac[:2] = 1, 1
        finv[:2] = 1, 1
        inv[1] = 1
        for i in range(2, N+1):
            fac[i] = fac[i-1]*i % mod
            inv[i] = -inv[mod % i]*(mod//i) % mod
            finv[i] = finv[i-1]*inv[i] % mod
        self.N = N
        self.MOD = mod
        self.fac = fac
        self.finv = finv
        self.inv = inv

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


def solve(r: "List[int]", c: "List[int]"):

    cmb = Combination(r[1]+c[1]+1, mod=MOD)

    def f(x, y):
        return cmb(x+y, y)

    def g(x, y):
        return f(x+1, y)+f(x, y+1)-1

    ans = g(r[1], c[1])-g(r[0]-1, c[1])-g(r[1], c[0]-1)+g(r[0]-1, c[0]-1)
    print(ans % MOD)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    r = [int()] * (2)  
    c = [int()] * (2)  
    for i in range(2):
        r[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(r, c)


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10
















def solve():
    def cmb(n, k):
        return fact[n] * invfact[k] * invfact[n-k] % mod
    maxn = int(3e6 + 10)
    r1, c1, r2, c2 = LI()
    ans = 0
    fact = [i for i in range(maxn)]
    fact[0] = 1
    invfact = [i+1 for i in range(maxn)]
    invfact[0] = 1
    for i in range(1, maxn-1):
        fact[i + 1] *= fact[i]
        fact[i + 1] %= mod
    invfact[-1] = pow(fact[-1], mod - 2, mod)
    invr1 = pow(r1, mod - 2, mod)
    for i in range(maxn - 2, -1, -1):
        invfact[i] *= invfact[i + 1]
        invfact[i] %= mod
    acc = list(map(lambda x: x % mod, itertools.accumulate(fact)))
    for c in range(c1, c2 + 1):
        ans += cmb(c + r2 + 1, c + 1) - cmb(c + r1 , c + 1)
        ans %= mod
    print(ans)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
M=1000000007
r1,c1,r2,c2=map(int,input().split())
n=r2+c2+2
fac=[1]+[0]*n
for i in range(1,n+1):fac[i]=fac[i-1]*i%M
f=lambda r,c:fac[r+c+2]*pow(fac[c+1],M-2,M)*pow(fac[r+1],M-2,M)-1
print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%M)

Solution (Python):
def comb(n,m,p=10**9+7):
    if n < m : return 0
    if n < 0 or m < 0:return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p

def s(n,m):
    return comb(n+m+2, m+1, mod)

mod = 10**9+7

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

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

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


class Combination:
    def __init__(self, N: int, MOD: int):
        fac = [0 for _ in range(N + 1)]
        fac[0] = 1
        for i in range(1, N + 1):
            fac[i] = fac[i - 1] * i % MOD
        self.fac = fac
        self.N = N
        self.MOD = MOD

    def _modpow(self, x: int, n: int) -> int:
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * x % self.MOD
            x = x * x % self.MOD
            n >>= 1
        return ret

    def _modinv(self, x: int) -> int:
        return self._modpow(x, self.MOD - 2)

    def combination(self, n: int, k: int) -> int:
        if n < k:
            return 0
        return self.fac[n] * self._modinv(self.fac[k]) % self.MOD * self._modinv(self.fac[n - k]) % self.MOD

MOD = 1000000007
comb = Combination(2 * 1000000 + 10, MOD)

ans = (2 * MOD + comb.combination(r1 + c1, r1) - comb.combination(r1 + c2 + 1, r1) - comb.combination(r2 + c1 + 1, r2 + 1) + comb.combination(r2 + c2 + 2, r2 + 1)) % MOD
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline

mod=10**9+7
MAX=2*10**6+100

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

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

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

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

Solution (Python):

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

Solution (Python):
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[0]*(n+1)
  fac[0]=1
  for i in range(1,n+1):fac[i]=fac[i-1]*i%M
  pr1=pow(fac[r1],M-2,M)
  pc1=pow(fac[c1],M-2,M)
  pr2=pow(fac[r2+1],M-2,M)
  pc2=pow(fac[c2+1],M-2,M)
  a=fac[r2+c2+2]*pr2*pc2
  a-=fac[r2+c1+1]*pr2*pc1
  a-=fac[r1+c2+1]*pr1*pc2
  a+=fac[r1+c1]*pr1*pc1
  print(a%M)
main()

Solution (Python):
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[0]*(n+1)
  fac[0]=val=1
  for i in range(1,n+1):fac[i]=val=val*i%M
  pr1=pow(fac[r1],M-2,M)
  pc1=pow(fac[c1],M-2,M)
  pr2=pow(fac[r2+1],M-2,M)
  pc2=pow(fac[c2+1],M-2,M)
  print((fac[r2+c2+2]*pr2*pc2-fac[r2+c1+1]*pr2*pc1-fac[r1+c2+1]*pr1*pc2+fac[r1+c1]*pr1*pc1)%M)
main()

Solution (Python):
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[0]*(n+1)
  fac[0]=val=1
  for i in range(1,n+1):fac[i]=val=val*i%M
  pr1=pow(fac[r1],M-2,M)
  pc1=pow(fac[c1],M-2,M)
  pr2=pow(fac[r2+1],M-2,M)
  pc2=pow(fac[c2+1],M-2,M)
  a=fac[r2+c2+2]*pr2*pc2
  a-=fac[r2+c1+1]*pr2*pc1
  a-=fac[r1+c2+1]*pr1*pc2
  a+=fac[r1+c1]*pr1*pc1
  print(a%M)
main()

Solution (Python):
M=10**9+7
r1,c1,r2,c2=map(int,input().split())
n=r2+c2+2
fac=[0]*(n+1)
fac[0]=val=1
for i in range(1,n+1):fac[i]=val=val*i%M
pr1=pow(fac[r1],M-2,M)
pc1=pow(fac[c1],M-2,M)
pr2=pow(fac[r2+1],M-2,M)
pc2=pow(fac[c2+1],M-2,M)
a=fac[r2+c2+2]*pr2*pc2
a-=fac[r2+c1+1]*pr2*pc1
a-=fac[r1+c2+1]*pr1*pc2
a+=fac[r1+c1]*pr1*pc1
print(a%M)

Solution (Python):
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 = f(r+1, c+1) - 1 + mod
    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)

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

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

def func(r, c):
    if c == 0:
        return r + 1
    return comb(r + c + 2, c + 1, MOD)

def comb(n, r, mod):
    return (g1[n] * g2[r] * g2[n - r]) % mod

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

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

Solution (Python):
mod = 10**9+7
MAX_N = 20000000+5

fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%mod)

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


def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

x,p,y,q = map(int,input().split())
 
res = mod_comb_k(p+x,x,mod) - mod_comb_k(p+y+1,y+1,mod) - mod_comb_k(q+x+1,x,mod) + mod_comb_k(q+y+2,y+1,mod)
print(res%mod)

Solution (Python):
mod=1000000007
fact=[1 for i in range(3000000)]
for i in range(1,3000000):
    fact[i]=(fact[i-1]*i)%mod

def inv(a):
    a%=mod
    b=mod
    u=0
    v=1
    while a!=0:
        t=b//a
        b-=t*a
        a,b=b,a
        u-=t*v
        u,v=v,u
    if u<0:
        u+=mod
    return u

def c(n,r):
    return (fact[n]*inv(fact[n-r])*inv(fact[r]))%mod

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

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

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

f    = [1]*M
p = 1
for i in range(1, M):
    p = p*i%mod
    f[i] = p
    

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

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

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

def count(R,C):
    ret = g[R+C+1] % mod

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

    for r in range(R):
        x1 = comb(C+r, r)
        x2 = g[R-r]
        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)

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

M=2*(10**6+1)
fac=[0]*(M+1)
ifac=[0]*(M+1)
fac[0]=1
for i in range(1,M+1):
    fac[i]=fac[i-1]*i%MOD
ifac[M]=pow(fac[M],MOD-2,MOD)
for i in range(M-1,0,-1):
    ifac[i]=ifac[i+1]*(i+1)%MOD

def comb(a,b): return fac[a]*ifac[a-b]*ifac[b]%MOD

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

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

Solution (Python):
def main():
  import sys
  M=10**9+7
  r1,c1,r2,c2=map(int,sys.stdin.buffer.readline().split())
  n=r2+c2+2
  val=1
  fac=[val]
  append=fac.append
  for i in range(1,n+1):
    val=val*i%M
    append(val)
  pr1=pow(fac[r1],M-2,M)
  pc1=pow(fac[c1],M-2,M)
  pr2=pow(fac[r2+1],M-2,M)
  pc2=pow(fac[c2+1],M-2,M)
  print((fac[r2+c2+2]*pr2*pc2-fac[r2+c1+1]*pr2*pc1-fac[r1+c2+1]*pr1*pc2+fac[r1+c1]*pr1*pc1)%M)
main()

Solution (Python):
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  val=1
  fac=[val]
  append=fac.append
  for i in range(1,n+1):
    val=val*i%M
    append(val)
  pr1=pow(fac[r1],M-2,M)
  pc1=pow(fac[c1],M-2,M)
  pr2=pow(fac[r2+1],M-2,M)
  pc2=pow(fac[c2+1],M-2,M)
  a=fac[r2+c2+2]*pr2*pc2
  a-=fac[r2+c1+1]*pr2*pc1
  a-=fac[r1+c2+1]*pr1*pc2
  a+=fac[r1+c1]*pr1*pc1
  print(a%M)
main()

Solution (Python):
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[1]
  val=1
  append=fac.append
  for i in range(1,n+1):
    val=val*i%M
    append(val)
  f=lambda r,c:fac[r+c+2]*pow(fac[c+1],M-2,M)*pow(fac[r+1],M-2,M)-c-r-2
  print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%M)
main()

Solution (Python):
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[0]*(n+1)
  fac[0]=val=1
  for i in range(1,n+1):fac[i]=val=val*i%M
  f=lambda r,c:fac[r+c+2]*pow(fac[c+1],M-2,M)*pow(fac[r+1],M-2,M)-c-r-2
  print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%M)
main()

Solution (Python):
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[1]
  val=1
  append=fac.append
  for i in range(1,n+1):
    val=val*i%M
    append(val)
  f=lambda r,c:fac[r+c+2]*pow(fac[c+1],M-2,M)*pow(fac[r+1],M-2,M)-c-r-2
  print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%M)
main()

Solution (Python):
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[0]*(n+1)
  fac[0]=before=1
  for i in range(1,n+1):fac[i]=before=before*i%M
  f=lambda r,c:fac[r+c+2]*pow(fac[c+1],M-2,M)*pow(fac[r+1],M-2,M)-c-r-2
  print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%M)
main()

Solution (Python):
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[0]*(n+1)
  fac[0]=1
  for i in range(1,n+1):fac[i]=fac[i-1]*i%M
  f=lambda r,c:fac[r+c+2]*pow(fac[c+1],M-2,M)*pow(fac[r+1],M-2,M)-c-r-2
  print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%M)
main()

Solution (Python):
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[1]+[0]*n
  for i in range(1,n+1):fac[i]=fac[i-1]*i%M
  f=lambda r,c:fac[r+c+2]*pow(fac[c+1],M-2,M)*pow(fac[r+1],M-2,M)-c-r-2
  print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%M)
main()

Solution (Python):
def main():
  M=10**9+7
  a,b,c,d=map(int,input().split())
  n=c+d+2
  fac=[0]*(n+1)
  fac[0]=lt=1
  for i in range(1,n+1):fac[i]=lt=lt*i%M
  inv=lambda n:pow(fac[n],M-2,M)
  f=lambda r,c:fac[r+c+2]*inv(c+1)*inv(r+1)-c-r-2
  print((f(c,d)-f(c,b-1)-f(a-1,d)+f(a-1,b-1))%M)
main()

Solution (Python):
def main():
  M=10**9+7
  a,b,c,d=map(int,input().split())
  n=c+d+2
  fac=[0]*(n+1)
  fac[0]=lt=1
  for i in range(1,n+1):fac[i]=lt=lt*i%M
  inv=[0]*(n+1)
  inv[n]=lt=pow(fac[n],M-2,M)
  for i in range(n,0,-1):inv[i-1]=lt=lt*i%M
  comb=lambda n,k:fac[n]*inv[n-k]*inv[k]
  f=lambda r,c:fac[r+c+2]*inv[c+1]*inv[r+1]-c-r-2
  print((f(c,d)-f(c,b-1)-f(a-1,d)+f(a-1,b-1))%M)
main()