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 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(rf, cf, rcf):
    return rcf * modinv((rf * cf) % MOD, MOD)


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

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

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

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

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


main()

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def f(r,c):
    d = c
    prod = 1
    div = 1
    divacc = 1
    for i in range(r-1):
        prod = (prod*d)%R
        divacc = (divacc*div)%R
        d += 1
        div += 1
    ret = (prod*modinv2(divacc,R))%R
    
    return ret

r1,c1,r2,c2 = inm()
r1 += 1
c1 += 1
r2 += 1
c2 += 1
print((f(r2+1,c2+1)-f(r2+1,c1)-f(r1,c2+1)+f(r1,c1))%R)

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict

con = 10 ** 9 + 7

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

class Combination(object):
	def __init__(self, N, con):
		self.fac = [0] * (N + 1)
		self.inv = [0] * (N + 1)
		self.finv = [0] * (N + 1)
		self.fac[0], self.fac[1] = 1, 1
		self.inv[1] = 1
		self.finv[0], self.finv[1] = 1, 1

		
		for i in range(2, N + 1):
			self.fac[i] = self.fac[i - 1] * i % con
			self.inv[i] = self.inv[con % i] * (con - (con // i)) % con
			self.finv[i] = self.finv[i - 1] * self.inv[i] % con

	def com(self, N, k):
		return (self.fac[N] * self.finv[k] * self.finv[N - k]) % con


def main():
	r1, c1, r2, c2 = getlist()
	Com1 = Combination(r1 + c2 + 1, con)
	Com2 = Combination(r1 + c1, con)
	ans = 0
	val1 = Com1.com(r1 + c2 + 1, r1 + 1)
	val2 = Com2.com(r1 + c1, r1 + 1)
	ans += val1 - val2
	for R in range(r1, r2):
		inv = pow(R + 2, con - 2, con)
		val1 = (val1 * (R + c2 + 2) * inv) % con
		val2 = (val2 * (R + c1 + 1) * inv) % con
		ans += val1 - val2
		ans %= con
	
	ans %= con
	print(ans)
	 


	


if __name__ == '__main__':
	main()

Solution (Python):
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def f(i, j):
    Fij = modFacts[i + j]
    Ii = invs[i]
    Ij = invs[j]
    rst = (Fij * Ii * Ij) % MOD
    return rst


def g(r1, r2, y):
    rst = 0
    for x in range(r1, r2 + 1):
        rst += f(x + 1, y)
        rst %= MOD
    return rst


r1, c1, r2, c2 = map(int, input().split())
modFacts, invs = prepare(max(r1, c1, r2, c2) * 2 + 1)


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


print(ans % MOD)

Solution (Python):
def main():
    mod=1000000007
    r1,c1,r2,c2=map(int,input().split())
    Fact=[1] 
    n=r2+c2+1
    for i in range(1,n+1):
        Fact.append(Fact[i-1]*i%mod)
    Finv=[0]*(n+1) 
    Finv[-1]=pow(Fact[-1],mod-2,mod)
    for i in range(n-1,-1,-1):
        Finv[i]=Finv[i+1]*(i+1)%mod
    def comb(n,r):
        if n<r:
            return 0
        return Fact[n]*Finv[r]*Finv[n-r]%mod
    def f(r,c):
        ret=0
        for i in range(r+1):
            ret+=comb(c+i+1,c)
            ret%=mod
        return ret
 
    print((f(r2,c2)-f(r2,c1-1)-f(c2,r1-1)+f(r1-1,c1-1))%mod)
    
if __name__=='__main__':
    main()

Solution (Python):
def ncr(n, r): 
    p = 10**9 + 7
    
    
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p
    return (num * pow(den,  
            p - 2, p)) % p
  
r1, c1, r2, c2 = [int(i) for i in input().split()]
r1 += 1
c1 += 1
r2 += 1
c2 += 1
print((ncr(r2 + c2, c2) - ncr(r2 + c1 -1, c1-1) - ncr(c2+r1-1, r1-1) + ncr(r1+c1-2, c1-1))%(10**9+7))

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

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

Solution (Python):
MOD = 10**9 + 7

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

def getFact(n, MOD):
    fact = 1
    for i in range(1, n+1):
        fact = (fact * i) % MOD
    return fact
def getFacts(n, MOD):
    facts = [1] * (n+1)
    for x in range(2, n+1):
        facts[x] = (facts[x-1] * x) % MOD
    return facts
def getInvFacts(n, MOD):
    invFacts = [0] * (n+1)
    invFacts[n] = pow(getFact(n, MOD), MOD-2, MOD)
    for x in reversed(range(n)):
        invFacts[x] = (invFacts[x+1] * (x+1)) % MOD
    return invFacts

facts = getFacts(2*10**6+3, MOD)
invFacts = getInvFacts(10**6+3, MOD)

def f(r, c):
    ans = facts[r+c] * invFacts[r] * invFacts[c]
    return ans % MOD


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

print(ans)

Solution (Python):
r, c, R, C = [int(_) for _ in input().split()]
mod = 10**9 + 7

f = [1] * (2 * 10**6 + 10)
for i in range(1, 2 * 10**6 + 10):
    f[i] = i * f[i - 1] % mod
fi = {}


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


a1 = (C + 2) * f[c + 1] * f[C + R + 2] - (c + 1) * f[C + 2] * f[c + R + 1]
a1 *= inv(f[c + 1]) * inv(f[C + 2]) * inv(f[R + 1])
a2 = (C + 2) * f[c + 1] * f[C + r + 1] - (c + 1) * f[C + 2] * f[c + r]
a2 *= inv(f[c + 1]) * inv(f[C + 2]) * inv(f[r])
ans = a1 - a2
ans %= mod
print(ans)

Solution (Python):
r, c, R, C = [int(_) for _ in input().split()]
mod = 10**9 + 7

f = [1] * (3 * 10**6 + 10)
for i in range(1, 3 * 10**6 + 10):
    f[i] = i * f[i - 1] % mod
fi = {}


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


a1 = (C + 2) * f[c + 1] * f[C + R + 2] - (c + 1) * f[C + 2] * f[c + R + 1]
a1 *= inv(f[c + 1]) * inv(f[C + 2]) * inv(f[R + 1])
a2 = (C + 2) * f[c + 1] * f[C + r + 1] - (c + 1) * f[C + 2] * f[c + r]
a2 *= inv(f[c + 1]) * inv(f[C + 2]) * inv(f[r])
ans = a1 - a2
ans %= mod
print(ans)

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

fact = [1]*(n+1)
rfact = [1]*(n+1)
r = 1
for i in range(1, n+1):
  fact[i] = r = r * i % mod
rfact[n] = r = pow(fact[n], mod-2, mod)
for i in range(n, 0, -1):
  rfact[i-1] = r = r * i % mod

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

ans = 0
for r in range(r1,r2+1):
  mini = (((c2+1) * comb(r + c2 + 1, r) - c1 * comb(c1+r,r)) * pow(r+1,mod-2,mod)) % mod
  ans = (ans + mini) % mod
print(ans % mod)

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

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

ans = com(r1+c1, r1)
if r1 == r2 or c1 == c2:
	if r1 != r2:
		for r in range(r1+1, r2+1):
			ans = (ans + com(r+c1, r)) % MOD
	if c1 != c2:
		for c in range(c1+1, c2+1):
			ans = (ans + com(r1+c, r1)) % MOD
	print(ans % MOD)
	exit()

diff_c = c2 - c1
keisu = [com(diff_c+i, i+1) for i in range(r2 - r1)]
t_keisu = [0]
for k in keisu:
	t_keisu.append((t_keisu[-1] + k) % MOD)
for r in range(r1+1, r2+1):
	tmp = com(r+c1, r)
	ans = (ans + tmp + tmp * t_keisu[r1 - r]) % MOD

diff_r = r2 - r1
keisu = [com(diff_r+i, i+1) for i in range(c2 - c1)]
t_keisu = [0]
for k in keisu:
	t_keisu.append((t_keisu[-1] + k) % MOD)
for c in range(c1 + 1, c2 + 1):
	tmp = com(r1+c, c)
	ans = (ans + tmp + tmp * t_keisu[c1 - c]) % MOD

print(ans)

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

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

    
    nmax = 2 * 10 ** 6 + 5  
    fac = [0] * nmax
    finv = [0] * nmax
    inv = [0] * nmax
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2, nmax):
        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, r):
        if n < r:
            return 0
        else:
            return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod

    def f(r, c):
        ret = 0
        for i in range(r+1):
            ret = (ret + comb(i+1+c, c))%mod
        return ret

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


if __name__ == '__main__':
    main()

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

def getInvs(n, MOD):
    invs = [0] * (n+1)
    invs[1] = 1
    for x in range(2, n+1):
        invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
    return invs
invs = getInvs(c2+r2+1, MOD)

combi_c2 = []
combi_c1_1 = []
for i in range(c2+r2+2):
    if i <= c2:
        combi_c2.append(int(i == c2))
    else:
        c = combi_c2[-1]
        combi_c2.append((c * i * invs[i-c2+1]) % MOD)
    if i <= c1-1:
        combi_c1_1.append(int(i == c1-1))
    else:
        c = combi_c1_1[-1]
        combi_c1_1.append((c * i * invs[i-c1]) % MOD)

ans = 0
t = 1
b = 1
for x in range(r2+2, c2+r2+2):
    t *= x
    t %= MOD
for x in range(1, c2+1):
    t *= invs[x]
    t %= MOD
for x in range(r2+2, c1+r2+1):
    b *= x
    b %= MOD
for x in range(1, c1):
    b *= invs[x]
    b %= MOD

ans = t - b
ans %= MOD
for i in range(r2, r1, -1):
    t = (t * ((i+c2+1)-c2) * invs[(i+c2+1)]) % MOD
    b = (b * ((i+c1-1+1)-(c1-1)) * invs[i+c1]) % MOD
    ans += t - b
    ans %= MOD
print(ans)

Solution (Python):
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):
    return nCr(r+c+2,c+1)-1
    
print((f(r2,c2) - f(r2,c1-1) - f(r1-1,c2) + f(r1-1,c1-1)) % MOD)

Solution (Python):
a,b,c,d=map(int,input().split())
m=10**9+7
s=[pow(i,m-2,m)for i in range(10**6+2)]
def f(x,y):
    p,q=x,x
    for i in range(2,y+1):
        q=(q*(x+i-1)*s[i])%m
        p=(p+q)%m
    return p
print((f(c+1,d+1)-f(a,d+1)-f(c+1,b)+f(a,b))%m)

Solution (Python):
r1,c1,r2,c2 = map(int,input().split())
mod = 10**9 + 7
def factorial(N,MOD,r=True):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1,N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N],MOD-2,MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    if r:
        return fact,rfact
    else:
        return fact
fact,rfact = factorial(r2+c2+1,mod)
def perm(n,k): 
    return fact[n]*rfact[n-k]%mod
def comb(n,k): 
    return fact[n]*rfact[k]*rfact[n-k]%mod
ans = comb(r1+c1,r1)

for i in range(r1+1,r2+1):
    ans += comb(i+c1,c1)*comb(r2-c1+c2+1-i,r2-i+1)
    ans %= mod
    

for i in range(c1+1,c2+1):
    ans += comb(i+r1,r1)*comb(c2-r1+r2+1-i,c2-i+1)
    ans %= mod
    

print(ans)

Solution (Python):
def examA():
    S, T = LSI()
    A, B = LI()
    U = SI()
    if S==U:
        print(A-1,B)
    else:
        print(A,B-1)
    return

def examB():
    S = SI()
    N = len(S)
    ans = ""
    for i in range(N):
        ans += "x"
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    d = defaultdict(int)
    for a in A:
        d[a] += 1
        if d[a]>=2:
            print("NO")
            return
    print("YES")
    return

def examD():
    N, K = LI()
    P = LI()
    S = [0]*(N+1)
    for i in range(N):
        S[i+1] = S[i]+(P[i]+1)/2
    ans = 0
    for i in range(N-K+1):
        cur = S[i+K]-S[i]
        ans = max(ans,cur)
    print(ans)
    return

def examE():
    def ketadp(a,K):
        n = len(a)
        C = [i for i in range(K+1)]
        dp = defaultdict(int)
        dp[0, 0, 0] = 1
        for i, less, k in itertools.product(range(n), (0, 1), C):
            max_d = 9 if less else int(a[i])
            for d in range(max_d + 1):
                less_ = less or d < max_d
                if d==0:
                    dp[i + 1, less_, k] += dp[i, less, k]
                elif k<K:
                    dp[i + 1, less_, k+1] += dp[i, less, k]

        ans = sum(dp[n, less, K] for less in (0, 1))
        return ans
    N = SI()
    K = I()
    ans = ketadp(N,K)
    print(ans)
    return

def examF():
    class combination():
        
        def __init__(self, n, mod):
            self.n = n
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r, mod):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % mod
    r1, c1, r2, c2 = LI()
    C = combination(r2+c2+2,mod)
    H = [0]*(c2+2)
    W = [0]*(c2+2)
    for i in range(c2+1):
        H[i+1] = H[i] + C.comb(r2+i+1,i+1,mod)
        W[i + 1] = W[i] + C.comb(r1-1 + i + 1, i + 1, mod)


    ans = H[c2+1] - H[c1] - W[c2+1] + W[c1]
    ans = (ans+mod)%mod
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examF()

"""

"""

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

MOD = 10 ** 9 + 7


def modInverse(x, p):
    
    return pow(x, p - 2, p)


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


def hockey(n, m):
    
    return nCr(n + m + 1, m, MOD)


tot1 = hockey(c2, r2 + 1) - hockey(c2, r1)
tot2 = hockey(c1 - 1, r2 + 1) - hockey(c1 - 1, r1)
print((tot1 - tot2) % MOD)

Solution (Python):

r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
N=2*(10**6)+10
def inv(x):
    return pow(x,mod-2,mod)
Fact=[0 for i in range(N+1)]
Fact[0]=1;
for i in range(N):
    Fact[i+1]=(i+1)*Fact[i]
    Fact[i+1]%=mod
def C(n,k):
    res=Fact[n]*inv(Fact[n-k])
    res%=mod
    res*=inv(Fact[k])
    res%=mod
    return res
ans1=(((r2+2)*inv(c2+1))%mod)*C(c2+r2+2,r2+2)
ans2=(((r2+2)*inv(c1))%mod)*C(c1+r2+1,r2+2)
ans3=(((r1+1)*inv(c2+1))%mod)*C(c2+r1+1,r1+1)
ans4=(((r1+1)*inv(c1))%mod)*C(c1+r1,r1+1)
ans1%=mod
ans2%=mod
ans3%=mod
ans4%=mod
print((ans1-ans2-ans3+ans4)%mod)

Solution (Python):
r, c, R, C = [int(_) for _ in input().split()]
mod = 10**9 + 7

f = [1] * (3 * 10**6 + 10)
for i in range(1, 3 * 10**6 + 10):
    f[i] = i * f[i - 1] % mod
fi = {}


def comb(n, r):
    if r not in fi:
        fi[r] = pow(f[r], mod - 2, mod)
    if n - r not in fi:
        fi[n - r] = pow(f[n - r], mod - 2, mod)
    return (f[n] * fi[r] * fi[n - r]) % mod


a1 = (C + 2) * f[c + 1] * f[C + R + 2] - (c + 1) * f[C + 2] * f[c + R + 1]
a1 *= pow(R + 1, mod - 2, mod) * pow(f[c + 1], mod - 2, mod) * pow(
    f[C + 2], mod - 2, mod) * pow(f[R], mod - 2, mod)
a2 = (C + 2) * f[c + 1] * f[C + r + 1] - (c + 1) * f[C + 2] * f[c + r]
a2 *= pow(r, mod - 2, mod) * pow(f[c + 1], mod - 2, mod) * pow(
    f[C + 2], mod - 2, mod) * pow(f[r - 1], mod - 2, mod)
ans = a1 - a2
ans %= mod
print(ans)

Solution (Python):
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
'''
p = 10 ** 9 + 7
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

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




x1,y1,x2,y2 = list(map(int, input().split()))


p = 10 ** 9 + 7
N = 2 * 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

def cmb2(a,b,p):
    return cmb(a+b+2,a+1,p)
    
print((cmb2(x2,y2,p) - cmb2(x1-1,y2,p) -cmb2(x2,y1-1,p) + cmb2(x1-1,y1-1,p))%p)

Solution (Python):

import sys
input = sys.stdin.readline
MOD = 10**9 + 7
MAX_N = 2 * 10**6 + 1


fac = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * (i) % MOD

fac_inv = [1] + [0] * MAX_N




fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD

def get_rect_sum(r, c):
    total = 0
    for i in range(1, c+2):
        total += mod_nCr(r + i, r)
    return total

r1, c1, r2, c2 = [int(item) for item in input().split()]
ans = get_rect_sum(r2, c2)
ans += get_rect_sum(r1 - 1, c1 - 1)
ans -= get_rect_sum(r2, c1 - 1)
ans -= get_rect_sum(r1 - 1, c2)
ans %= MOD
print(ans)

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


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

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


def comb_sum(i, j):
    return nck(i+j+2, i+1)

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

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



mod = 10**9+7

m = r2+c2 +10 
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

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


def g(r,c):
    ret = 0
    for i in range(0,r+1):
        ret += comb(i+c+1,i+1)
        ret %= mod
    return ret

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

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

    mod = 10 ** 9 + 7  
    N = 10 ** 4
    g1 = [1, 1]  
    g2 = [1, 1]  
    inverse = [0, 1]  

    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)

    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


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

    print(ans % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
MOD=10**9+7
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))
        )
r1,c1,r2,c2=map(int,input().split())
l=[1]*2000022
for i in range(1,2000022):
  l[i]=l[i-1]*ModInt(i)
def comb(a,b):
  c,d=int(a),int(b)
  if a==b or b==0 or a==0:return 1
  return l[c]/l[d]/l[c-d]
ans=((ModInt(r2)+2)*comb(c2+r2+2,r2+2)-ModInt(c2)-1)/(ModInt(c2)+1)-((ModInt(r1)+1)*comb(c2+r1+1,r1+1)-ModInt(c2)-1)/(ModInt(c2)+1)-((ModInt(r2)+2)*comb(c1+r2+1,r2+2)-ModInt(c1)-2)/ModInt(c1)+((ModInt(r1)+1)*comb(c1+r1,r1+1)-ModInt(c1)-2)/ModInt(c1)
print(ans)

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

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

factinv = [1]*(2*10**6+10)
for n in range(10**6+10):
    factinv[n] = pow(fact[n],mod-2,mod)

def comb(n,k):
    return (fact[n]*factinv[n-k]*factinv[k])%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)

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

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

    
    nmax = 2 * 10 ** 6 + 5  
    fac = [0] * (nmax + 1)
    finv = [0] * (nmax + 1)
    inv = [0] * (nmax + 1)
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2, nmax):
        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, r):
        if n < r:
            return 0
        else:
            return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod

    def f(r, c):
        ret = 0
        for i in range(r+1):
            ret = (ret + comb(i+1+c, c))%mod
        return ret

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


if __name__ == '__main__':
    main()

Solution (Python):
bikkuri = [1]
mod = 10**9+7

for i in range(1,2*10**6+1000):
    bikkuri.append((bikkuri[-1]*i)%mod)
r1,c1,r2,c2 = map(int,input().split())

def F(r,c):
    tmp = (bikkuri[r+c+2]*pow(bikkuri[c+1],mod-2,mod)*pow(bikkuri[r+1],mod-2,mod) - 1)%mod
    return tmp

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

Solution (Python):
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):
    gyaku = pow((i + 2), MOD - 2, MOD)
    r *= (r2 + 1 + (i + 1))
    r *= gyaku
    l *= (r1 + (i + 1))
    l *= gyaku
    r %= MOD
    l %= MOD
    if i >= c1 - 1:
        ans += r
        ans -= l
    ans %= MOD
print(ans % MOD)

Solution (Python):
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
n_max=2*(10**6+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

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

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

Solution (Python):
r1,c1,r2,c2=map(int,input().split())
INF=10**9+7
def modcomb(n,k,m):
    fac=[0]*(n+1)
    finv=[0]*(n+1)
    inv=[0]*(n+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,n+1):
        fac[i]=fac[i-1]*i%m
        inv[i]=m-inv[m%i]*(m//i)%m
        finv[i]=finv[i-1]*inv[i]%m
    return fac[n]*(finv[k]*finv[n-k]%m)%m
def modinv(a,m):
    b=m
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while not b==0:
        q=a//b
        (a,b)=(b,a%b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx%m
ans=modcomb(r1+c1,r1,INF)
c=modcomb(r2+c1,c1,INF)
for i in range(c1+1,c2+1):
    c=c*(i+r2)
    x=modinv(i,INF)
    c=(c*x)%INF
    ans=(ans+c)%INF
c=modcomb(r1+c2,r1,INF)
for i in range(r1+1,r2+1):
    c=c*(i+c2)
    x=modinv(i,INF)
    c=(c*x)%INF
    ans=(ans+c)%INF
print(ans)

Solution (Python):
class Factorial():
    def __init__(self,n,mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n+1)]
        self.inv = [0 for _ in range(n+1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i+1] = self.factorial[i]*(i+1)%mod
        self.inv[n] = pow(self.factorial[n],mod-2,mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i+1]*(i+1)%mod


    def comb(self,m,k): 
        return self.factorial[m]*self.inv[k]*self.inv[m-k]%self.mod

def solve():

    MOD = 1000000007

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

    f = Factorial(2000010,MOD)

    ans = 0

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

    print(ans)

solve()

Solution (Python):
def main():
    mod = 10**9+7
    fact = [1]
    fact_inv = [1]
    for i in range(2000005):
        new_fact = fact[-1]*(i+1)%mod
        fact.append(new_fact)


    def mod_comb_k(n,k,mod):
        return fact[n] * pow(fact[k],mod-2,mod) % mod * pow(fact[n-k],mod-2,mod) %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)

if __name__ == '__main__':
    main()

Solution (Python):


MOD = 10**9 + 7
list_size = 2000003

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

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

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

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

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

def f(x, y):
	if x * y == 0:
		return 0
	elif x == 1:
		return y * (y+3) // 2
	else:
		return comb(x+y+2, x+1) - x - y - 2


r1, c1, r2, c2 = list(map(int, input().split()))
ans = (f(r2, c2) + f(r1-1, c1-1) - f(r1-1, c2) - f(r2, c1-1)) % MOD
print(ans)

Solution (Python):
MOD = 10**9 + 7

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

def getFact(n, MOD):
    fact = 1
    for i in range(1, n+1):
        fact = (fact * i) % MOD
    return fact
def getFacts(n, MOD):
    facts = [1] * (n+1)
    for x in range(2, n+1):
        facts[x] = (facts[x-1] * x) % MOD
    return facts
def getInvFacts(n, MOD):
    invFacts = [0] * (n+1)
    invFacts[n] = pow(getFact(n, MOD), MOD-2, MOD)
    for x in reversed(range(n)):
        invFacts[x] = (invFacts[x+1] * (x+1)) % MOD
    return invFacts

facts = getFacts(2*10**6+3, MOD)
invFacts = getInvFacts(10**6+3, MOD)

def f(r, c):
    ans = facts[r+c] * invFacts[r] * invFacts[c]
    return ans % MOD


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

print(ans)

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

MOD = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci
frac, fraci = frac(2341398)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%MOD

def accumulate2d(X2):
    X = X2
    N = len(X)
    M = len(X[0])
    
    for i in range(N):
        for j in range(1, M):
            X[i][j] += X[i][j-1]
    
    for j in range(M):
        for i in range(1, N):
            X[i][j] += X[i-1][j]
    
    return X

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

def calc(R, C):
    if min(R, C) == 0:
        return 1
    res = R
    for i in range(1, C):
        res = (res + comb(R+i, i+1)) % MOD
    return res
r2 += 1
c2 += 1
print((calc(r2, c2)-calc(r2, c1)-calc(r1, c2)+calc(r1, c1))%MOD)