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):
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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

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

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

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

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

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

  mod = 10**9+7

  fact = [1,1]
  finv = [1,1]
  inv = [0,1]

  for i in range(2,r2+c2+3):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)

  def nCr(n,r,mod):
      
      return fact[n]*finv[r]*finv[n-r]%mod

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

if __name__ == "__main__":
  main()

Solution (Python):
def main():
    MOD = 10**9 + 7
    r1, c1, r2, c2 = (int(i) for i in input().split())
    m = r2 + c2 + 3
    fac = [0] * m
    finv = [0] * m
    inv = [0] * m

    def COMBinitialize(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                fac[i] = fac[i-1] * i % MOD
                inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
                finv[i] = finv[i - 1] * inv[i] % MOD

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

    COMBinitialize(m)
    ans = 0
    ans += (fac[r2+1+c2+1]*finv[r2+1]*finv[c2+1] - 1) % MOD
    ans -= (fac[r2+1+c1]*finv[r2+1]*finv[c1] - 1) % MOD
    ans -= (fac[r1+c2+1]*finv[r1]*finv[c2+1] - 1) % MOD
    ans += (fac[r1+c1]*finv[r1]*finv[c1] - 1) % MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
Q = 10**9+7
def getInv(N):
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

def getFactorialInv(N):
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    ret = [1]*(N+1)
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
        ret[i] = ret[i-1]*inv[i]%Q
    return ret

def getFactorial(N):
    ret = [1]*(N+1)
    for i in range(2,N+1):
        ret[i] = ret[i-1]*i%Q
    return ret

def main():
    r1, c1, r2, c2 = map( int, input().split())
    F = getFactorial(2*10**6+2)
    I = getFactorialInv(10**6+1)

    def G(a, b):
        return F[a+b+2]*I[a+1]%Q*I[b+1]%Q
    
    print( ( G(r2,c2) - G(r2, c1-1) - G(r1-1, c2) + G(r1-1, c1-1))%Q)
if __name__ == '__main__':
    main()

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

n = r2 + c2 + 10

fac = [0] * n
inv = [0] * n
finv = [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 comb(n, r) :
  return fac[n] * finv[n-r] % mod * finv[r] % mod

def g(x, y) :
  return comb(x + y, y)

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

print(ret)

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

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

def comb(n, r) :
  return fac[n] * inv[n-r] % mod * inv[r] % mod

def g(x, y) :
  return comb(x + y, y)

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

print(ret)

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


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


def make_table(n, mod=10 ** 9 + 7):
    N = n
    
    g1 = [0] * (N + 1)
    g1[0] = 1
    g1[1] = 1

    tmp = g1[1]
    for i in range(2, N + 1):
        tmp = tmp * i % mod
        g1[i] = (g1[i - 1] * i) % mod

    return g1


def f(x, y):
    return ((x + 2) * cmb(x + y + 2, y, mod) - y - 1) * pow(y + 1, mod - 2, mod)


g1 = make_table(2 * 10 ** 6 + 10)
answer = f(c2, r2) - f(c2, r1 - 1) - f(c1 - 1, r2) + f(c1 - 1, r1 - 1)
answer %= mod
print(answer)

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

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

def comb(n, r) :
  return fac[n] * inv[n-r] * inv[r] % mod

def g(x, y) :
  return comb(x + y, y)

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

print(ret)

Solution (Python):
MOD = int(1e9)+7

def fact(x):
    k = 1
    for i in range(1,x+1):
        k = (k*i)%MOD
    return k

def inverse(b):
    r = 1
    e = MOD -2
    while e:
        if e%2==1:
            r = (r*b)%MOD
        b = (b*b)%MOD
        e >>=1
    return r

def comb(i,j):
    if i==0 or j==0:
        return 0
    num=fact(i+j)
    num*=inverse(fact(i))
    num%=MOD
    num*=inverse(fact(j))
    num%=MOD
    return num

rc = list(map(int, input().split()))
ans = 0
ans += comb(rc[2]+1,rc[3]+1)
ans -= comb(rc[0],rc[3]+1)
ans -= comb(rc[2]+1,rc[1])
ans += comb(rc[0],rc[1])
ans += MOD
ans += MOD
ans %=MOD
print(ans)

Solution (Python):
MOD = int(1e9)+7

def fact(x):
    k = 1
    for i in range(1,x+1):
        k = (k*i)%MOD
    return k

def inverse(b):
    r = 1
    e = MOD -2
    while e:
        if e%2==1:
            r = (r*b)%MOD
        b = (b*b)%MOD
        e >>=1
    return r

def comb(i,j):
    if i==0 or j==0:
        return 0
    num=fact(i+j)
    num*=inverse(fact(i))
    num%=MOD
    num*=inverse(fact(j))
    num%=MOD
    return num

rc = list(map(int, input().split()))
ans = 0
ans += comb(rc[2]+1,rc[3]+1)
ans -= comb(rc[0],rc[3]+1)
ans -= comb(rc[2]+1,rc[1])
ans += comb(rc[0],rc[1])
ans += MOD
ans += MOD
ans %=MOD
print(ans)

Solution (Python):
MOD=1000000007
def fact(x):
    k=1
    for i in range(x+1):
        if i!=0:
            k=(k*i)%MOD
    return k

def inverse(b):
    r=1;e=MOD-2
    while e:
        if (e%2==1):
            r = (r*b)%MOD
        b=(b*b)%MOD
        e>>=1
    return r

def Comb(i,j):
    if i==0 or j==0:
        return 0
    num=fact(i+j)
    num*=inverse(fact(i))
    num%=MOD
    num*=inverse(fact(j))
    num%=MOD
    return num
    
r1,c1,r2,c2 = map(int,input().split())






Ans=0
Ans+=Comb(r2+1,c2+1)
Ans-=Comb(r1,c2+1)
Ans-=Comb(r2+1,c1)
Ans+=Comb(r1,c1)
Ans+=MOD;Ans+=MOD;Ans%=MOD

print(Ans)

Solution (Python):
MOD = 10**9+7
fac = [1, 1]
f_inv = [1, 1]
inv = [0, 1]

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)


def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def f(r, c):
    return modcmb(r+c, r, MOD)


def g(x, y):
    return ((y+2) * modcmb(x+y+2, x, MOD) - (x+1)) * pow(x+1, MOD-2, MOD)


def main():
    prepare(2*10**6+10, MOD)
    r1,c1,r2,c2 = map(int, input().split())

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

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):




MOD = 10**9+7
fac = [1, 1]
f_inv = [1, 1]
inv = [0, 1]

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)


def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def f(r, c):
    return modcmb(r+c, r, MOD)


def main():
    prepare(2*10**6+10, MOD)
    r1,c1,r2,c2 = map(int, input().split())

    ans = 0
    for c in range(c1,c2+1):
        ans += ((r2+1) * modcmb(c+r2+1, r2+1, MOD) - r1 * modcmb(c+r1, r1, MOD)) * pow(c+1, MOD-2, MOD)
        ans %= MOD

    print(ans)


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

mod = 10**9+7
fc = [0]*(2*10**6+2)
fc[0] = 1

for i in range(1, 2*10**6+2):
    fc[i] = fc[i-1]*i%mod
    
inv = [1]*(2*10**6+2)
lst = 2*10**6+1
inv[lst] = pow(fc[lst], mod-2, mod)

for i in range(lst, 0, -1):
    inv[i-1] = (inv[i]*i)%mod

def comb(n, r):
    return ((fc[n]*inv[r])%mod)*inv[n-r]%mod

cum=0
for i in range(r1, r2+1):
    d1 = comb(i+1+c2, c2)
    d2 = comb(i+c1, c1-1)
    cum = (cum+(d1-d2))%mod

print(cum)

Solution (Python):
def solve():
    r1, c1, r2, c2 = map(int, input().split())
    
    p = 10 ** 9 + 7
    N = r2 + c2 + 2
    fact = [1, 1]
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % p)
    
    def comb(n, r):
        a = fact[n]
        b = pow(fact[r], p - 2, p)
        c = pow(fact[n-r], p - 2, p)
        return a * b * c % p
    
    def f(i, j):
        return comb(i + j, i)
    
    def g(i, j):
        return f(i + 1, j + 1) - 1
    
    ans = g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)
    
    print(ans % p)

solve()

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


def comb(x, y):
    return f[x] * pow(f[y], mod - 2, mod) * pow(f[x - y], mod - 2, mod)


print((comb(C + R + 2, R + 1) - comb(c + R + 1, R + 1) - comb(C + r + 1, r) + comb(c + r, r)) % mod)

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


factorial=[1]
for i in range(1, n+1):
    factorial.append(factorial[-1] * i % mod)

inv_factorial = [-1] * (n+1)
inv_factorial[-1] = pow(factorial[-1], mod-2, mod)
for i in reversed(range(n)):
    inv_factorial[i] = inv_factorial[i+1] * (i+1) % mod

def fact(n):
    return factorial[n]

def nck(n, k):
    if k>n or k<0:
        return 0
    else:
        return factorial[n] * inv_factorial[n-k] * inv_factorial[k]
      
def routes(r,c):
  return nck(r+c+2,c+1)-1

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

Solution (Python):
def inpl():
    return list(map(int, input().split()))


def cmb(n, r):
    
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    return (over[n] * under[r] * under[n - r]) % MOD



def extGCD(x, y):
    r = [1, 0, x]
    w = [0, 1, y]
    
    while w[2] != 1:
        
        q = r[2] // w[2]
        w_tmp = [r[0] - q * w[0], r[1] - q * w[1], r[2] % w[2]]
        r, w = w, w_tmp

    return w[:2]


def mod_inv(a, m):
    _, x = extGCD(m, a)
    return (x + m) % m


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


r1, c1, r2, c2 = inpl()

MOD = 10**9 + 7

over = [0 for i in range(r2 + c2 + 3)]
under = [0 for i in range(r2 + c2 + 3)]
over[0] = 1
for i in range(r2 + c2 + 2):
    over[i + 1] = over[i] * (i + 1) % MOD

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

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

Solution (Python):
nn = 2002002
P = 10**9+7

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P

f = lambda a, b: fa[a+b+2] * fainv[a+1] * fainv[b+1] % P
r1, c1, r2, c2 = map(int, input().split())
print((f(r2, c2) - f(r2, c1-1) - f(r1-1, c2) + f(r1-1, c1-1)) % P)

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

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

  fact = [1]*(U+1)
  fact_inv = [1]*(U+1)

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

  for i in range(U,0,-1):
      fact_inv[i-1] = (fact_inv[i]*i)%MOD

  def comb(n, k):
      if k < 0 or k > n:
          return 0
      z = fact[n]
      z *= fact_inv[k]
      z %= MOD
      z *= fact_inv[n-k]
      z %= MOD
      return z

  ans = 0
  r1, c1, r2, c2 = map(int, input().split())
  for i in range(c1, c2+1):
    ans += comb(i+r2+1, i+1) - comb(i+r1, i+1)
  print(ans%MOD)
  
if __name__ == "__main__":
  main()

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

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

  fact = [1]*(U+1)
  fact_inv = [1]*(U+1)

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

  for i in range(U,0,-1):
      fact_inv[i-1] = (fact_inv[i]*i)%MOD

  def comb(n, k):
      if k < 0 or k > n:
          return 0
      z = fact[n]
      z *= fact_inv[k]
      z *= fact_inv[n-k]
      z %= MOD
      return z

  ans = 0
  r1, c1, r2, c2 = map(int, input().split())
  for i in range(c1, c2+1):
    ans += comb(i+r2+1, i+1) - comb(i+r1, i+1)
  print(ans%MOD)
  
if __name__ == "__main__":
  main()

Solution (Python):
mod = 10**9+7
rng = 2000100
fctr = [1]+[0]*(rng-1)
for i in range(1,rng):
  fctr[i] = fctr[i-1]*i%mod
def finv(x):
  return pow(fctr[x],mod-2,mod)
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv(n-k)*finv(k)%mod

x1,y1,x2,y2 = map(int,input().split())
print((cmb(x2+y2+2,x2+1)-cmb(x2+y1+1,y1)-cmb(x1+y2+1,x1)+cmb(x1+y1,x1))%mod)

Solution (Python):
mod = 10**9+7
rng = 2000100
fctr = [1]+[0]*(rng-1)
for i in range(1,rng):
  fctr[i] = fctr[i-1]*i%mod
def finv(x):
  return pow(fctr[x],mod-2,mod)
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv(n-k)*finv(k)%mod

x1,y1,x2,y2 = map(int,input().split())
print((cmb(x2+y2+2,x2+1)-cmb(x2+y1+1,y1)-cmb(x1+y2+1,x1)+cmb(x1+y1,x1))%mod)

Solution (Python):
mod = 10**9+7
rng = 2000100
fctr = [1]+[0]*(rng-1)
finv = [1]+[0]*(rng-1)
for i in range(1,rng):
  fctr[i] = fctr[i-1]*i%mod
for i in range(1,rng):
  finv[i] = pow(fctr[i],mod-2,mod)
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod

x1,y1,x2,y2 = map(int,input().split())
print((cmb(x2+y2+2,x2+1)-cmb(x2+y1+1,y1)-cmb(x1+y2+1,x1)+cmb(x1+y1,x1))%mod)

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

f = [1]*(2*10**6+5)
f[0] = 1
for i in range(1,2*10**6+4):
    f[i] = f[i-1]*i%mod

def inv(i):
    return pow(f[i],mod-2,mod)

def g(x,y):
    return f[x+y]*inv(x)*inv(y)%mod

r1,c1,r2,c2 = map(int,input().split(" "))
ans = g(r2+1,c2+1)-g(r2+1,c1)-g(r1,c2+1)+g(r1,c1)
print(ans%mod)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007




r1, c1, r2, c2 = LI()

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


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


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class ModTools:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        
        inverse = [1] * MAX
        
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """

        if n < r: return 0
        
        r = min(r, n-r)
        
        numerator = self.fact[n]
        
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

r1, c1, r2, c2 = MAP()

mt = ModTools(r2+c2+2, MOD)

def calc(r, c):
    return mt.nCr(r+c+2, r+1) - 1


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

Solution (Python):
import sys

MOD = 10 ** 9 + 7

def make_table(size=2*10**6+2, p=MOD):
    fac = [None] * (size + 1)
    fac[0] = 1
    for i in range(size):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (size + 1)
    ifac[size] = pow(fac[size], p-2, p)
    for i in range(size, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    return fac, ifac

fac, ifac = make_table()

def comb(n, r, mod=MOD):
    if r > n or r < 0:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

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

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

def main():
    ans = (g(r2, c2) - (g(r1-1, c2) + g(r2, c1-1) - g(r1-1, c1-1))) % MOD
    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
MOD = 10**9+7
fac = [1, 1]
f_inv = [1, 1]
inv = [0, 1]

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)


def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def f(r, c):
    return modcmb(r+c, r, MOD)


def main():
    prepare(2*10**6+10, MOD)
    r1,c1,r2,c2 = map(int, input().split())

    ans = 0
    for i in range(1,c2+2):
        ans += f(r2, i)
        ans %= MOD

    for i in range(1,c2+2):
        ans -= f(r1-1, i)
        ans %= MOD

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

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

    print(ans % MOD)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] * ifac[com_n - com_r]

def s(r, c):
    return nCr(r + c + 2, r + 1)

r1, c1, r2, c2 = MI()
md = 10**9+7
n_max = r2+c2+5
fac = [mint(1)]
for i in range(1, n_max + 1): fac.append(fac[-1] * i)
ifac = [1] * (n_max + 1)
ifac[n_max] = fac[n_max] ** (md - 2)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1)

def main():
    ans=s(r2,c2)-s(r1-1,c2)-s(r2,c1-1)+s(r1-1,c1-1)
    print(ans)

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


r1, c1, r2, c2 = list(map(int, input().split()))
MOD = 10 ** 9 + 7
facts, invs = prepare(r2 + c2 + 1, MOD)
ans = 0
for i in range(r1, r2 + 1):
    d1 = facts[i + c2 + 1] * invs[c2] % MOD
    d2 = facts[i + c1] * invs[c1 - 1] % MOD
    ans = (ans + (d1 - d2) * invs[i + 1]) % MOD
print(ans)

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

mod = 1000000007


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

fact = [0 for i in range(2000003)]
for i in range(2000003):
    if i <= 1:
        fact[i] = 1
    else:
        fact[i] = (fact[i-1] * i) % mod


def combination(n, r):
    return (((fact[n] * inversion(fact[r])) % mod) * inversion(fact[n-r])) % mod

answer = (
combination(r2 + c2 + 2, r2 + 1) -
combination(r2 + c1 + 1, r2 + 1) -
combination(r1 + c2 + 1, c2 + 1) +
combination(r1 + c1    , c1    ) )

answer %= mod

if answer < 0:
    answer += mod

print(answer)

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



mod = 10**9 + 7
max = 3 * 10**6
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = 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

comInit(max)


def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod


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

print(ans)

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


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


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


def S(): return input()


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


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


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


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


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


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


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


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



show_flg = True

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


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


def g(r, c):
    return cmb(r+c+2, r+1, MOD)


def main():
    M = 10 ** 6
    r1, c1, r2, c2 = MI()
    r1 -= 1
    c1 -= 1

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

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


if __name__ == '__main__':
    main()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class ModTools:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        
        inverse = [1] * MAX
        
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """

        if n < r: return 0
        
        r = min(r, n-r)
        
        numerator = self.fact[n]
        
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

    def div(self, x, y):
        """ MOD除算 """

        return x * pow(y, self.MOD-2, self.MOD) % self.MOD

r1, c1, r2, c2 = MAP()

mt = ModTools(r2+c2+2, MOD)
def calc(r, c):
    return mt.div(((r+2) * mt.nCr(c+r+2, r+2) - c - 1), (c + 1))

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

Solution (Python):

def modfac(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 modnCr(n,r,mod,fac,inv): 

    return fac[n] * inv[n-r] * inv[r] % mod

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

mod = 10 ** 9 + 7
fac,inv = modfac(r2+c2+1,mod)
ans = 0

for r in range(r1,r2+1):

    ans += modnCr(r+c2+1,c2,mod,fac,inv) - modnCr(r+c1,c1-1,mod,fac,inv)
    ans %= mod

print (ans)

Solution (Python):
def f_many_many_paths():
    class Combination(object):
        """参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb"""
        __slots__ = ['mod', 'factorial', 'inverse']

        def __init__(self, max_val_arg: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_val_arg + 1):
                fac_append(fac[-1] * i % mod)

            
            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_val_arg, 0, -1):
                inv_append((inv[-1] * i) % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def combination(self, n, r):
            if n < 0 or r < 0 or n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

    R1, C1, R2, C2 = [int(i) for i in input().split()]
    comb = Combination(R2 + C2 + 2).combination

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

    return (g(R2, C2) - g(R1 - 1, C2) - g(R2, C1 - 1) + g(R1 - 1, C1 - 1)) % (10**9 + 7)

print(f_many_many_paths())

Solution (Python):

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

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

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


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

def g(r,c):
    gsum = 0
    for i in range(1,r+2):
        gsum += cmb(i+c,c)
    return gsum
'''
sum = 0
for r in range(r1,r2+1):
    for c in range(c1,c2+1):
        sum += cmb(r+c,r)
print(sum % mod)
'''
sum2 = g(r2,c2) - g(r1-1,c2) - g(r2,c1-1) + g(r1-1,c1-1)
print(sum2 % mod)