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

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

MAX = 2 * 10 ** 6 + 1
MOD = 10 ** 9 + 7


fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1


inv = [0] * (MAX + 1)
inv[1] = 1


finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

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


def f(r, c):
    return fac[r + c] * finv[r] * finv[c] % MOD


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

Solution (Python):
'''
研究室PCでの解答
解説AC
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    r1,c1,r2,c2 = map(int,ipt().split())
    
    N = r2+c2+2
    g1 = [1, 1] 
    g2 = [1, 1] 
    inverse = [0, 1] 
    def cmb(n,r,mod=(10**9+7)):
        if r<0 or r>n :
            return 0
        r = min(r,n-r)
        return g1[n]*g2[r]*g2[n-r]%mod
    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(r2+c2+2,r2+1)+cmb(r1+c1,r1)-cmb(r2+c1+1,r2+1)-cmb(r1+c2+1,r1))%mod)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
'''
研究室PCでの解答
解説AC
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    r1,c1,r2,c2 = map(int,ipt().split())
    
    N = r2+c2+2
    g1 = [1, 1] 
    g2 = [1, 1] 
    inverse = [0, 1] 
    def cmb(n,r,mod=(10**9+7)):
        if r<0 or r>n :
            return 0
        r = min(r,n-r)
        return g1[n]*g2[r]*g2[n-r]%mod
    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(r2+c2+2,r2+1)+cmb(r1+c1,r1)-cmb(r2+c1+1,r2+1)-cmb(r1+c2+1,r1))%mod)

    return None

if __name__ == '__main__':
    main()

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

def func(r, c):
    return f[r+c] * i[r] % MOD * i[c] % MOD

MOD = 10**9+7
f, i = prepare(2*10**6 + 2, MOD)


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

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

Solution (Python):
import copy


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

def func(r, c):
    return f[r+1+c+1] * i[r+1] % MOD * i[c+1] % MOD

MOD = 10**9+7
f, i = prepare(2*10**6 + 2, MOD)


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

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

Solution (Python):
class Combination:
    """
  O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
  n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
  使用例：
  comb = Combination(1000000)
  print(comb(5, 3))  
  """

    def __init__(self, n_max, mod=10 ** 9 + 7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]

        facinv = [1]
        for i in range(1, n + 1):
            fac.append(fac[i - 1] * i % self.mod)
            facinv.append(facinv[i - 1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n + 1)
        modinv[1] = 1
        for i in range(2, n + 1):
            modinv[i] = self.mod - self.mod // i * \
                modinv[self.mod % i] % self.mod
        return modinv


MOD = 10**9 + 7

r1, c1, r2, c2 = map(int, input().split())
c = Combination(2000006)
ans = 0
for r in range(r1, r2 + 1):
    temp = c(c2 + r + 1, r + 1) - c(c1 + r + 1 - 1, r + 1)
    temp %= MOD
    ans += temp
    ans %= MOD
print(ans)

Solution (Python):
a,b,c,d=map(int,input().split())
m=10**9+7
def f(r,c):
 s=t=1
 for i in range(c):s=s*(r+c-i)%m;t=t*-~i%m
 return s*pow(t,m-2,m)
print((f(a,b)-f(c+1,b)-f(a,d+1)+f(c+1,d+1))%m)

Solution (Python):
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()



class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo


show_flg=False
show_flg=True

ans=0


a,b,c,d=LI()

cm=Comb(a+b+c+d+10)

def f(r,c):
    rt=0
    for i in range(r+1):
        rt+=cm.comb(i+c+1,c)
        rt%=mo
    return rt

print((f(c,d)-f(a-1,d)-f(c,b-1)+f(a-1,b-1))%mo)

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

mod = 10**9+7
MAX_N = 3*10**6

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 comb(n,k,mod):
    if n<k:return 0
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

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

print(ans)

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

mod = 10**9+7
MAX_N = 3*10**6

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 comb(n,k,mod):
    if n<k:return 0
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

ans=0
ans+=comb(c1+r1,r1,mod)
ans%=mod
ans-=comb(c1+r2+1,r2+1,mod)
ans%=mod
ans-=comb(c2+r1+1,r1,mod)
ans%=mod
ans+=comb(c2+r2+2,r2+1,mod)
ans%=mod

print(ans)

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

mod = 10**9+7
MAX_N = 3*10**6

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 comb(n,k,mod):
    if n<k:return 0
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

ans=0
ans+=comb(c1+r1,r1,mod)
ans%=mod
ans-=comb(c1+r2+1,r2+1,mod)
ans%=mod
ans-=comb(c2+r1+1,r1,mod)
ans%=mod
ans+=comb(c2+r2+2,r2+1,mod)
ans%=mod

print(ans)

Solution (Python):


class Combination:
    def __init__(self, n_max, mod=10 ** 9 + 7):
        
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max + 1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod - 2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    
    

    def __call__(self, n, r):  
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

    def nCr(self, n, r):
        if not 0 <= r <= n:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

def resolve():
    def f(r, c):
        return cmb.nCr(r+c+2, r+1) - 1

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

    cmb = Combination(r2+c2+5)
    ans = f(r2, c2)
    ans -= f(r1, c2)
    ans -= f(r2, c1)
    ans += f(r1, c1)
    print(ans % MOD)


if __name__ == "__main__":
    resolve()

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

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_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 MOD_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) % MOD

def main():
    r1, c1, r2, c2 = map(int, input().split())
    MOD_COM_init()
    a = MOD_COM(r2+1+c2+1, r2+1) - 1
    b = MOD_COM(r2+1+c1, c1) - 1
    c = MOD_COM(r1+c2+1, r1) - 1
    d = MOD_COM(r1+c1, c1) - 1
    ans = a - (b + c) + d
    print(ans % MOD)

if __name__ == "__main__":
    main()

Solution (Python):
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
def comb(n,k,mod):
  if n<k:
    return 0
  if n-k<k:
    k=n-k
  c=1
  for x in range(n-k+1,n+1):
    c=(c*x)%mod
  d=1
  for x in range(1,k+1):
    d=(d*x)%mod
  c=c*pow(d,mod-2,mod)
  return c%mod
def f(i,j):
  return comb(i+j,i,mod)
ans=f(r2+1,c2+1)-f(r2+1,c1)-f(r1,c2+1)+f(r1,c1)
ans%=mod
print(ans)

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

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

def getComb(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

def f(i, j):
    return getComb(i+j, j, 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
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

M = 10**9+7 
N = 2*10**6+4 

g1 = [None] * (N+1) 
g2 = [None] * (N+1) 
inverse = [None] * (N+1) 
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

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

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M

ans = 0
r1,c1,r2,c2 = map(int, input().split())
for c in range(c1, c2+1):
    ans += cmb(r2+c, r2, M) - cmb(r1-1+c, r1-1, M)
for r in range(r1, r2+1):
    ans += cmb(c2+r, c2, M) - cmb(c1-1+r, c1-1, M)
    











print(ans%M)

Solution (Python):
def comb(n, r, p):
    x, y = 1, 1
    for i in range(n, n - r, -1):
        x *= i
        y *= i + r - n
        x %= p
        y %= p
    return pow(y, p - 2, p) * x % p

r1, c1, r2, c2 = map(int, input().split())
mod = pow(10, 9) + 7
s1, s2 = c1 + r1, c1 + r2 + 1
t1, t2 = min(c1 + 1, r1 - 1), min(c1 + 1, r2)
comb1 = comb(s1, t1, mod)
comb2 = comb(s2, t2, mod)
u1, u2 = s1 - r1 + 1, s2 - r2
ans = comb2 - comb1
for i in range(1, c2 - c1 + 1):
    comb1 = comb1 * (s1 + i) * pow(u1 + i, mod - 2, mod)
    comb1 %= mod
    comb2 = comb2 * (s2 + i) * pow(u2 + i, mod - 2, mod)
    comb2 %= mod
    ans += comb2
    ans -= comb1
    ans %= mod
print(ans)

Solution (Python):
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def ns(): return stdin.readline().rstrip()  




def modPow(a, n, p):
    if n == 1:
        return a
    if n % 2 == 1:
        return (a * (modPow(a, n // 2, p) ** 2)) % p
    else:
        return (modPow(a, n // 2, p) ** 2) % p


def modInverse(a, p):
    
    
    return modPow(a, p - 2, p)


def modBinomial(n, k, p):
    

    numerator = 1  
    for i in range(k):
        numerator = (numerator * (n - i)) % p

    denominator = 1  
    for i in range(1, k + 1):
        denominator = (denominator * i) % p

    
    return (numerator * modInverse(denominator, p)) % p


r1, c1, r2, c2 = na()
mod = 10 ** 9 + 7
print((modBinomial(r2 + c2 + 2, r2 + 1, mod) + modBinomial(r1 + c1, r1, mod) -
       modBinomial(r1 + c2 + 1, r1, mod) - modBinomial(r2 + c1 + 1, c1, mod)) % mod)

Solution (Python):
r1,c1,r2,c2 = map(int, input().split())
def find_power(n,mod=10**9+7):
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n,mod=10**9+7):
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

mod = 10**9+7
NUM = (2*10**6)+100
p_lis=find_power(NUM,mod)
ip_lis=find_inv_power(NUM,mod)

def comb(n,r,mod=10**9+7):
    if n<r:
        return 0
    elif n>=r:
        return (p_lis[n]*ip_lis[r]*ip_lis[n-r])%(mod)
def g(x,y):
    return comb(x+y+2,y+1)-1

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

Solution (Python):
r1, c1, r2, c2 = map(int, input().split())
N = 10 ** 7
MOD = 10 ** 9 + 7
def createFacArr(n, mod):
    '''
    二項係数計算用の配列の作成

    Parameters
    n : int
        配列のサイズ
    mod : int
        あまり

    Returns
    fac : list
        階乗のリスト
    finv : list
        modの逆元のリスト
    ivn : list
    '''
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, n):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
    return fac, finv
fac, finv = createFacArr(N+100, MOD)

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

    Parameters
    n : int
        元集合
    k : int
        元集合から選択する数
    mod : int
        あまり
    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

ans = 0

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

print(ans)

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

    MOD = 10**9+7
    n = r2+c2+2
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
      fac[i] = i*fac[i-1]%MOD
      rev[i] = pow(fac[i], MOD-2, MOD)
    
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD
    f = lambda r,c:comb(r+c+2, c+1)

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


if __name__ == "__main__":
    solve()

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

    MOD = 10**9+7
    n = r2+c2+2
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
      fac[i] = i*fac[i-1]%MOD
      rev[i] = pow(fac[i], MOD-2, MOD)
    
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

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

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

    print(ans)


if __name__ == "__main__":
    solve()

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

n = r2 + c2 + 3
mod = 10 ** 9 + 7
f = [1 for _ in range(n)]
f_inv = [1 for _ in range(n)]
for i in range(1, n):
    f[i] = f[i-1] * i % mod
    f_inv[i] = pow(f[i], mod-2, mod)

def comb(n, k):
    return f[n] * f_inv[k] * f_inv[n-k] % mod
def g(r, c):
    return comb(r+c+2, c+1) - 1

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

print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  

def calc_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD

def make_facts(n):
    '''
        make factorials
        0!(=1), 1!, 2!, 3! .... n!
    '''
    fact = [1]
    for i in range(n):
        fact.append((fact[i] * (i + 1)) % MOD)
    return fact

def make_combs(n, k):
    '''
        make [C(0, k), C(1, k), C(2, k) ..... C(n, k)]
    '''
    fact = [1] * (n + 1)
    for i in range(2, n + 1):
        fact[i] = (fact[i - 1] * i) % MOD

    ret = [0] * (n + 1)
    for i in range(k, n + 1):
        a = fact[i]
        b = (fact[k] * fact[i - k]) % MOD
        ret[i] = calc_fraction_mod(a, b)
    return ret


def solve(r: "List[int]", c: "List[int]"):
    
    ret = 0
    x = make_combs(r[1] + c[1] + 2, r[1])
    y = make_combs(r[0] + c[1] + 2, r[0] - 1)
    for i in range(c[0], c[1] + 1):
        ret += x[r[1] + i + 1]
        ret -= y[r[0] + i]
        ret %= MOD
    print(ret)
    return ret
    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):
def createFacArr(n, mod):
    '''
    二項係数計算用の配列の作成

    Parameters
    n : int
        配列のサイズ
    mod : int
        あまり

    Returns
    fac : list
        階乗のリスト
    finv : list
        modの逆元のリスト
    ivn : list
    '''
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, n):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
    return fac, finv

def comb(n ,k, mod, fac, 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
MOD = 10 ** 9 + 7
fac, finv =  createFacArr(10**7, MOD)

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

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

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

def main():
    r1,c1,r2,c2 = LI()

    r = 0
    t1 = 1
    u1 = c2 + 1
    t2 = 1
    u2 = c1
    for i in range(1, r2+2):
        t1 *= u1
        t1 %= mod
        u1 += 1
        t1 *= inv(i)
        t1 %= mod
        t2 *= u2
        t2 %= mod
        u2 += 1
        t2 *= inv(i)
        t2 %= mod
        if i > r1:
            r += t1 - t2
            r %= mod

    return r

print(main())

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

class Combination:
    def __init__(self, n, mod):

        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)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.MOD


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(R1, C1, R2, C2):
    C = Combination(2*10**6+1, 10**9+7)
    M = Mod(10**9+7)
    ans = 0
    for r in range(R1, R2+1):
        a = C(C2+r+1, r+1)
        b = C(C1-1+r+1, r+1)
        ans = M.add(ans, M.sub(a, b))
    return ans



def main():
    R1, C1, R2, C2 = read_int_n()
    print(slv(R1, C1, R2, C2))


if __name__ == '__main__':
    main()

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

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

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

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

    def nHr(self, n, r):
        return self.nCr(n - 1 + r, r)


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

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

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

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


if __name__ == '__main__':
    main()

Solution (Python):
mod = 1000000007

class combination():
    def __init__(self, n):
        self.fact = [1] * (n+1)
        self.ifact = [1] * (n+1)
        for i in range(1, n+1):
            self.fact[i] = self.fact[i-1]*i % mod
        self.ifact[n] = pow(self.fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            self.ifact[i-1] = self.ifact[i]*i % mod
    def comb(self, n, k):
        if k < 0 or k > n: return 0
        comb = self.fact[n]*self.ifact[k]*self.ifact[n-k] %mod
        return comb

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

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

    comb = combination(2000010)

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

main()

Solution (Python):
mod = 10**9+7
def comb_mod(n,r,mod,invs):
    ans = 1
    for i in range(r):
        ans *= n-i
        ans %= mod
    ans *= invs[r]
    ans %= mod
    return ans

A, B, C, D = map(int, input().split())

invs = [1]*(C+2)
for i in range(1,C+2):
    invs[i] = invs[i-1]*pow(i,mod-2,mod)
    invs[i] %= mod
ans = comb_mod(C+D+2,C+1,mod,invs)-comb_mod(B+C+1,B,mod,invs)-comb_mod(A+D+1,A,mod,invs)+comb_mod(A+B,A,mod,invs)
print(ans%mod)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

C = Factorial(2 * 10 ** 6 + 5, MOD).comb

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

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

    ans += tmp
    ans %= MOD

print (ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

def main():
  r1,c1,r2,c2=map(int,input().split())
  mod=pow(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
  g1 = [1, 1] 
  g2 = [1, 1] 
  inverse = [0, 1]
  for i in range( 2, r2+c2+3):
      g1.append( ( g1[-1] * i ) % mod )
      inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
      g2.append( (g2[-1] * inverse[-1]) % mod )
  ans=0
  for r in range(r1,r2+1):
    ans+=cmb(r+c2+1,r+1,mod)-cmb(r+c1,r+1,mod)
    ans%=mod
  print(ans)

if __name__=='__main__':
  main()

Solution (Python):
def main():
    mod = 10 ** 9 + 7
    N = 2 * 10 ** 6 + 3

    fac = [0] * N
    finv = [0] * N
    inv = [0] * N

    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, N):
        fac[i] = fac[i - 1] * i % mod
        
        
        
    
    finv[N // 2] = pow(fac[N // 2], mod - 2, mod)
    for i in reversed(range(N // 2)):
        finv[i] = (finv[i + 1] * (i + 1)) % mod

    def com(r, c):
        ans = fac[r + c] * finv[r] * finv[c]
        return ans % mod

    def g(r, c):
        return (com(r + 1, c + 1) - 1) % mod

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

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

if __name__ == "__main__":
    main()

Solution (Python):
mod = 10 ** 9 + 7
N = 2 * 10 ** 6 + 10

fac = [0] * N
finv = [0] * N
inv = [0] * N

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, N):
    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):
    global fac, finv, mod
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod

def g(r, c):
    return (com(r + c + 2, r + 1) - 1) % mod

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

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