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())
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):
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)
  ans %= MOD
print(ans)

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

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



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


N = 2 * 10**6 + 3
g1 = [1, 1]  
g2 = [1, 1]  
inverse = [0, 1]  

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




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

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n_ = 2*10**6 + 5
mod = 10**9+7
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod

def nCr(n,r):
    if r > n:
        return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

r1,c1,r2,c2 = nm()

def H(k,l):
    return (nCr(k+l+2, k+1)-1)%mod

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

Solution (Python):
class PERM_COMB_MOD():
    
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

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

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

    def h(self, n, k):
        if n == k == 0:
            return 1
        return self.comb(n+k-1, k)

PCM = PERM_COMB_MOD(3*10**6+100)
mod = 10**9+7

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

def sq(R,L):
    R+=1
    L+=1
    ret = 0
    for i in range(R):
        ret += PCM.comb(L+i, i+1)
    ret %= mod
    return ret
ans = sq(r2, c2) - sq(r2, c1-1) - sq(r1-1, c2) + sq(r1-1,c1-1)
ans %= mod
print(ans)

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n_ = 2*10**6 + 3
mod = 10**9+7
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod

def nCr(n,r):
    if r > n:
        return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod


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

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def comb(a,b):
        return f[a]*inv[b]*inv[a-b]%mod
    r1,c1,r2,c2 = LI()
    N = 3*10**6
    f = [1]
    for i in range(N):
        f.append(f[-1]*(i+1)%mod)
    inv = [None]*(N+1)
    inv[-1] = pow(f[-1],mod-2,mod)
    for i in range(N)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    ans = 0
    for i in range(r1,r2+1):
        s = 0
        ans += comb(i+1+c2,i+1)-comb(i+c1,i+1)
        ans %= mod
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
mod = 10**9+7
rng = 2000100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(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):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10 ** 9 + 7

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


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

fact, fact_inv = make_fact(2 * 10**6 + 10)

def F(i,j):
    return fact[i+j+2] * fact_inv[i+1] % MOD * fact_inv[j+1] % MOD

a,b,c,d = map(int,read().split())

answer = F(c,d) - F(a-1,d) - F(c,b-1) + F(a-1,b-1)
answer %= MOD
print(answer)

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

mod = 10**9 + 7
l = 2*10**6 + 3

M = [1]  
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

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



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

def C(x, y):  
    if y < 0 or y > x:
        return 0
    ans = M[x]
    ans = (ans * MI[y]) % mod
    return (ans * MI[x-y]) % mod

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

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
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 )
    
r,c,R,C=map(int,input().split())
ans=0
for i in range(C-c):
  ans=ans+cmb(r+c+1+i,r,mod)*cmb(R-r+C-c-i,R-r,mod)
ans=ans+cmb(r+c,r,mod)
for i in range(R-r):
  ans=ans+cmb(c+r+1+i,c,mod)*cmb(C-c+R-r-i,C-c,mod)
print(ans%mod)

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

FACT=[1]
for i in range(1,2*10**6+3):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**6+2,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

ANS=0

for x in range(c1+1,c2+2):
    ANS=(ANS+Combi(r2+x,r2)-Combi(r1+x-1,r1-1))%mod

print(ANS)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  




def enumfif(n, mod):
    f = [0] * (n+1)
    invf = [0] * (n+1)
    f[0] = 1
    for i in range(1, n+1):
        f[i] = f[i-1] * i % mod

    a = f[n]
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a//b
        d = a; a = b; b = d % b
        d = p; p = q; q = d-c*q
    invf[n] = p + mod if p < 0 else p
    for i in range(n-1,-1,-1):
        invf[i] = invf[i+1] * (i+1) % mod
    return f, invf

def C(n, r, mod, fif):
    if n < 0 or r < 0 or r > n:
        return 0
    return fif[0][n] * fif[1][r] * fif[1][n-r] % mod

mod = 1000000007
fif = enumfif(2000005, mod)




r1, c1, r2, c2 = na()
ans = \
    C(r2+1+c2+1, c2+1, mod, fif) - \
    C(r1 + c2 + 1, c2 + 1, mod, fif) - \
    C(r2 + c1 + 1, c1 - 1 + 1, mod, fif) + \
    C(r1 + c1, c1 - 1 + 1, mod, fif)
ans %= mod
if ans < 0: ans += mod
print(ans)

Solution (Python):



SIZE=2*10**6+10**5

MOD=10**9+7 

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

def choose(n,r): 
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0

import sys
readline = sys.stdin.readline
read = sys.stdin.read


p,a,q,b = [int(i) for i in read().split()]


ans = choose(q+b+2,b+1) - choose(p+b+1,b+1) - choose(q+a+1,a) + choose(p+a,a)


print(ans%MOD)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10 ** 9 + 7

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


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

fact, fact_inv = make_fact(2 * 10**6 + 10)

def F(i,j):
    return fact[i+j+2] * fact_inv[i+1] % MOD * fact_inv[j+1] % MOD

a,b,c,d = map(int,read().split())

answer = F(c,d) - F(a-1,d) - F(c,b-1) + F(a-1,b-1)
answer %= MOD
print(answer)