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 = 3*10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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

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

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

def p_mod(m,n,p):
    a = 1
    for i in range(n):
        a = a*(m-i) % p
    return a

def c_mod(m,n,p):
    return (p_mod(m,n,p)*pow(p_mod(n,n,p),p-2,p)) % p

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

Solution (Python):

import sys

sysread = sys.stdin.readline
read = sys.stdin.read


sys.setrecursionlimit(10**7)
import math
from itertools import combinations, product


def run():
    r1, c1, r2, c2 = map(int, read().split())
    mod = 10 ** 9 + 7

    def generate_inv(n, mod):
        """
        逆元行列
        n >= 2
        Note: mod must bwe a prime number
        """
        ret = [0, 1]
        for i in range(2, n + 1):
            next = -ret[mod % i] * (mod // i)
            next %= mod
            ret.append(next)
        return ret

    inv = generate_inv(max(c1,c2,r1,r2) + 1, mod)



    def calc(i,j):
        ret = 0
        agg = 1
        for k in range(1, i+2):
            agg *= (j+k)%mod
            agg *= inv[k]
            agg %= mod
            ret += agg
        return ret


    ret = 0
    ret += calc(r2, c2)
    ret -= calc(r2, c1-1)
    ret -= calc(r1-1, c2)
    ret += calc(r1-1, c1-1)
    ret %= mod
    print(ret)

if __name__ == "__main__":
    run()

Solution (Python):

import sys

sysread = sys.stdin.readline
read = sys.stdin.read


sys.setrecursionlimit(10**7)
import math
from itertools import combinations, product


def run():
    r1, c1, r2, c2 = map(int, read().split())
    mod = 10 ** 9 + 7

    def generate_inv(n, mod):
        """
        逆元行列
        n >= 2
        Note: mod must bwe a prime number
        """
        ret = [0, 1]
        for i in range(2, n + 1):
            next = -ret[mod % i] * (mod // i)
            next %= mod
            ret.append(next)
        return ret

    inv = generate_inv(10 ** 6 + 1, mod)



    def calc(i,j):
        ret = 0
        agg = 1
        for k in range(1, i+2):
            agg *= (j+k)%mod
            agg *= inv[k]
            agg %= mod
            ret += agg
        return ret


    ret = 0
    ret += calc(r2, c2)
    ret -= calc(r2, c1-1)
    ret -= calc(r1-1, c2)
    ret += calc(r1-1, c1-1)
    ret %= mod
    print(ret)

if __name__ == "__main__":
    run()

Solution (Python):






import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)




x1,y1,x2,y2 = inputIL()


def super(X,Y):
  return nCr(X+Y+2,X+1)-1


A = super(x2,y2)
B = super(x2,y1-1)
C = super(x1-1,y2) 
D = super(x1-1,y1-1) 
print((A-B-C+D)%MOD)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self, n):
        fact, invfact = [1] * (n + 1), [1] * (n + 1)
        for i in range(1, n + 1): fact[i] = i * fact[i - 1] % MOD
        invfact[n] = pow(fact[n], MOD - 2, MOD)
        for i in range(n - 1, -1, -1): invfact[i] = invfact[i + 1] * (i + 1) % MOD
        self._fact, self._invfact = fact, invfact

    def inv(self, n):
        return self._fact[n - 1] * self._invfact[n] % MOD

    def fact(self, n):
        return self._fact[n]

    def invfact(self, n):
        return self._invfact[n]

    def comb(self, n, k):
        if k < 0 or n < k: return 0
        return self._fact[n] * self._invfact[k] % MOD * self._invfact[n - k] % MOD

    def perm(self, n, k):
        if k < 0 or n < k: return 0
        return self._fact[n] * self._invfact[n - k] % MOD

def resolve():
    r1, c1, r2, c2 = map(int, input().split())
    mf = modfact(r2 + c2 + 2)
    def S(m, n):
        res = (m + 2) * mf.comb(m + n + 2, m + 2) % MOD * mf.inv(n + 1) % MOD
        res -= 1
        return res % MOD

    res = S(r2, c2) - S(r1 - 1, c2) - S(r2, c1 - 1) + S(r1 - 1, c1 - 1)
    print(res % MOD)
resolve()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    r,c,rr,cc=map(int,input().split())
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,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%MOD
            inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
            finv[i]=finv[i-1]*inv[i]%MOD
        return fac,finv,inv
    
    fac,finv,inv=COMinit(rr+cc+10,MOD)
    
    def COM(n, k, MOD=MOD):
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    
    ans=COM(rr+cc+2,rr+1)-COM(rr+c+1,c)-COM(r+cc+1,r)+COM(r+c,r)
    ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    r,c,rr,cc=map(int,input().split())
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,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%MOD
            inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
            finv[i]=finv[i-1]*inv[i]%MOD
        return fac,finv,inv
    
    fac,finv,inv=COMinit(rr+cc+10,MOD)
    
    def COM(n, k, MOD=MOD):
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    
    ans=0
    for i in range(c,cc+1):
        ans+=COM(rr+i+1,i+1)-COM(r+i,i+1)
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

class ModInt:

    def __init__(self, mod=1000000007, mem_size=3000000):
        self.mod = mod
        self.mem_factorial = [0] * mem_size
        self.mem_size = mem_size
        self.mem_inv = [0] * mem_size
        self.mem_invfactorial = [0] * mem_size
        self.mem_factorial[0] = 1
        self.mem_inv[1] = 1
        self.mem_invfactorial[0] = 1
        for i in range(1, mem_size):
            self.mem_factorial[i] = self.mem_factorial[i-1]*i % mod
            if i > 1:
                self.mem_inv[i] = (-1) * (mod//i) * (self.mem_inv[mod % i]) % mod
            self.mem_invfactorial[i] = self.mem_invfactorial[i-1] * self.mem_inv[i] % mod

    def inverse(self, x):
        if x < self.mem_size:
            return self.mem_inv[x]
        mod = self.mod
        return int(pow(x, mod-2, mod))

    def factorial(self, x):
        return self.mem_factorial[x]

    def invfactorial(self, x):
        return self.mem_invfactorial[x]


    def comb(self, m, n):
        mod = self.mod
        a = self.factorial(m)
        b = self.invfactorial(n)
        c = self.invfactorial(m - n)
        ret = a * b * c % mod
        return ret

mod = 1000000007

modint = ModInt(mod)


def r_sum(r, c):
    a = modint.factorial(c + r + 1) * (r + 1)
    b = modint.invfactorial(c + 1) * modint.invfactorial(r + 1)
    ret = a * b
    return ret % mod


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

r_from, c_from, r_to, c_to = map(int, input().split())

ans = F(r_to, c_to)
ans -= F(r_to, c_from - 1)
ans -= F(r_from - 1, c_to)
ans += F(r_from - 1, c_from - 1)
ans %= mod

print(ans)

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

MOD=10**9+7
MAXN=4000000+10
g1=[1, 1]
g2=[1, 1]
inverse=[0, 1]

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

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

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

print(ans%MOD)

Solution (Python):
MOD = 10**9+7
r1,c1,r2,c2 = map(int,input().split())
 
size = 1010000*2
f_list = [1]*(size)
for i in range(1,size):
    f_list[i] = (f_list[i-1]*i)%MOD

def func(r,c):
    return (f_list[r+c]*pow(f_list[r],MOD-2,MOD)*pow(f_list[c],MOD-2,MOD))
 
ans = func(r2+1,c2+1)-1
ans += func(r1,c1)-1
ans -= func(r2+1,c1)-1
ans -= func(r1,c2+1)-1
print(ans%MOD)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class Combination:
    def __init__(self, n: int, mod: int):
        self.mod = mod
        self.fact = [0] * (n + 1)
        self.factinv = [0] * (n + 1)
        self.inv = [0] * (n + 1)
        
        self.fact[0] = self.fact[1] = 1
        self.factinv[0] = self.factinv[1] = 1
        self.inv[1] = 1
        for i in range(2, n + 1):
            self.fact[i] = (self.fact[i - 1] * i) % mod
            self.inv[i] = (-self.inv[mod % i] * (mod // i)) % mod
            self.factinv[i] = (self.factinv[i - 1] * self.inv[i]) % mod
    
    def ncr(self, n: int, r: int):
        if r < 0 or n < r:
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] % self.mod * self.factinv[n - r] % self.mod
    
    def nhr(self, n: int, r: int):
        return self.ncr(n + r - 1, r)
    
    def npr(self, n: int, r: int):
        if r < 0 or n < r:
            return 0
        return self.fact[n] * self.factinv[n - r] % self.mod


def solve():
    r1, c1, r2, c2 = map(int, rl().split())
    MOD = 10 ** 9 + 7
    
    com = Combination(r2 + c2 + 100, MOD)
    ans = com.ncr(r2 + c2 + 2, c2 + 1)
    ans = (ans - com.ncr(r1 + c2 + 1, c2 + 1)) % MOD
    ans = (ans - com.ncr(r2 + c1 + 1, c1)) % MOD
    ans = (ans + com.ncr(r1 + c1, c1)) % MOD
    print(ans)


if __name__ == '__main__':
    solve()

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

F = 2*10**6+5
mod = 10**9+7
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[F-1]=pow(fact[F-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

ans=fact[r2+c2+2]*inv[r2+1]*inv[c2+1]-fact[r2+c1+1]*inv[r2+1]*inv[c1]-fact[r1+c2+1]*inv[r1]*inv[c2+1]+fact[r1+c1]*inv[r1]*inv[c1]
ans%=mod
print(ans)

Solution (Python):
mod = 10**9+7
MAX = (10**6)*2+1 
fact = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact[i] = (fact[i-1]*i)%mod
inv = [1]*(MAX+1)
for i in range(2, MAX+1):
    inv[i] = inv[mod%i]*(mod-mod//i)%mod
fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1]*inv[i]%mod
def comb(n, r):
    if n < r:
        return 0
    return fact[n]*fact_inv[n-r]*fact_inv[r] % mod
ans = 0
r1,c1,r2,c2 = map(int,input().split())
for i in range(r1+1,r2+2):
    ans += comb(i+c2,c2)-comb(i+c1-1,c1-1)
    ans %= mod
print(ans)

Solution (Python):
MOD = 10 ** 9 + 7
def comb(n, r):
    return fact[n] * pow(fact[n - r], MOD - 2, MOD) * pow(fact[r], MOD - 2, MOD)
def g(r, c):
    return (comb(r + c + 2, c + 1) - 1) % MOD
r1, c1, r2, c2 = map(int, input().split())
FACT_MAX = r2 + c2 + 3
fact = [1] * FACT_MAX
for i in range(1, FACT_MAX):
    fact[i] = fact[i - 1] * i % MOD
print((g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)) % MOD)

Solution (Python):
MOD = 10 ** 9 + 7
FACT_MAX = 2 * 10 ** 6 + 3
fact = [1] * FACT_MAX
for i in range(1, FACT_MAX):
    fact[i] = fact[i - 1] * i % MOD
def comb(n, r):
    return fact[n] * pow(fact[n - r], MOD - 2, MOD) * pow(fact[r], MOD - 2, MOD)
def g(r, c):
    return (comb(r + c + 2, c + 1) - 1) % MOD
r1, c1, r2, c2 = map(int, input().split())
print((g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)) % MOD)

Solution (Python):
def f(n, r, mod=10 ** 9 + 7):
	n += r
	assert n >= r >= 0

	def ex_euclid(x, y):
		a, b = 1, 0
		while y != 0:
			a, b = b, (a - x // y * b)
			x, y = y, x % y
		return a

	p = q = 1
	for i in range(n - r + 1, n + 1):
		p *= i
		p %= mod
	for i in range(2, r + 1):
		q *= i
		q %= mod
	p *= ex_euclid(q, mod)
	p %= mod
	return p

a,b,c,d=map(int,input().split())
mod=10**9+7
print((f(c+1,d+1)+mod-f(a,d+1)+mod-f(c+1,b)+f(a,b))%mod)

Solution (Python):

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

    
    rec = pow(fac[-1], mod-2, mod)

    
    den = [1 for _ in range(n+1)]
    den[n] = rec
    for i in range(n-1, 0, -1):
        rec = (rec * (i+1)) % mod
        den[i] = rec
    
    return fac, den

def comb_mod(n, r, mod, fac, den):
    return (fac[n] * den[r] * den[n - r]) % mod

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


mod = 10**9 + 7
fac, den = prepare(r2+c2+2, mod)

ans = comb_mod(r2+1+c2+1, c2+1, mod, fac, den)
ans -= comb_mod(r2+1+c1, c1, mod, fac, den)
ans -= comb_mod(r1+c2+1, c2+1, mod, fac, den)
ans += comb_mod(r1+c1, c1, mod, fac, den)

print(ans % mod)

Solution (Python):

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

    
    rec = pow(fac[-1], mod-2, mod)

    
    den = [1 for _ in range(n+1)]
    den[n] = rec
    for i in range(n-1, 0, -1):
        rec = (rec * (i+1)) % mod
        den[i] = rec
    
    return fac, den

def comb_mod(n, r, mod, fac, den):
    return (fac[n] * den[r] * den[n - r]) % mod

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


mod = 10**9 + 7
fac, den = prepare(r2+c2+2, mod)

ans = comb_mod(r2+1+c2+1, c2+1, mod, fac, den)
ans -= comb_mod(r2+1+c1, c1, mod, fac, den)
ans -= comb_mod(r1+c2+1, c2+1, mod, fac, den)
ans += comb_mod(r1+c1, c1, mod, fac, den)

print(ans % mod)

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

def cmb1(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+5
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 )

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

Solution (Python):
def g(r, c):
    return (fact[r + c + 2] * fact_inv[r + 1] * fact_inv[c + 1] - 1) % mod


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

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

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

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

fact_inv = [1] * (MAX + 10)
for i in range(1, MAX + 10):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod

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

Solution (Python):
def g(r, c):
    ret = 0
    for i in range(1, r + 2):
        ret += fact[i + c] * fact_inv[i] * fact_inv[c]
        ret %= mod

    return ret


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

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

fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact[i] = (fact[i-1] * i) % mod

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

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod

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,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
  return list(map(int,input().split()))
def m(): 
  return map(int,input().split())
def onem(): 
  return int(input())
def s(x): 
  a = []
  if len(x) == 0:
    return []
  aa = x[0]
  su = 1
  for i in range(len(x)-1):
    if aa != x[i+1]:
      a.append([aa,su])
      aa = x[i+1]
      su = 1
    else:
      su += 1
  a.append([aa,su])
  return a
def jo(x): 
  return " ".join(map(str,x))
def max2(x): 
  return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
  ll = 0
  rr = r
  while True:
    mid = (ll+rr)//2

  if rr == mid:
    return ll
  if (ここに評価入れる):
    rr = mid
  else:
    ll = mid+1
"""

mod = 10**9+7 
N = 10**6 * 2 + 2
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
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % 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 )


r1,c1,r2,c2= m()

p1 = 0

p2 = 0

p3 = 0

p4 = 0

for i in range(1,r2+2):
  p1 += cmb(c2+i,i)
  p1 %= mod
for i in range(1,r1+1):
  p2 += cmb(c2+i,i)
  p2 %= mod
for i in range(1,r2+2):
  p3 += cmb(c1+i-1,i)
  p3 %= mod
for i in range(1,r1+1):
  p4 += cmb(c1+i-1,i)
  p4 %= mod

print((p1-p2-p3+p4)%mod)

Solution (Python):

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

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

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

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

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

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

Solution (Python):

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

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

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

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

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

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

Solution (Python):


mod=10**9+7
def find_power(n,mod):
    
    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 pow_cal(x,n,mod):
    if n==0:
        return 1
    elif n==1:
        return x%mod
    elif n>=2:
        if n%2==0:
            return (pow_cal(x,n//2,mod)**2)%mod
        else:
            return (x*pow_cal(x,n//2,mod)**2)%mod

def find_inv_power(n,mod):
    
    c=1
    uselist=[0 for i in range(n+1)]
    for i in range(1,n+1):
        c*=i
        c%=mod
    first=pow_cal(c,mod-2,mod)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(mod)
    return uselist
    
A=find_power(2*10**6+10,mod)
B=find_inv_power(2*10**6+10,mod)

def combi(n,r,mod):
    if n<r:
        return 0
    elif n>=r:
        return (A[n]*B[r]*B[n-r])%(mod)
    
r1,c1,r2,c2=map(int,input().split())

mod=10**9+7     

K=combi(r2+c2+2,c2+1,mod)-combi(r2+c1+1,c1,mod)-combi(r1+c2+1,r1,mod)+combi(r1+c1,c1,mod)

print(K%mod)

Solution (Python):
import sys
import math
import numpy
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
       
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
   
if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,p,d = map(int,input().split())
    MOD = 10**9+7
    N = p+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(p+1,d+1)-comb(p+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(g,h):
        return (fac[g+h]*pow(fac[g],MOD-2,MOD)*pow(fac[h],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(500*500)
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)

r1,c1,r2,c2=map(int,input().split())
n1=r2+c2+2
n2=r2+c1+1
n3=r1+c2+1
n4=r1+c1
l=[r2+1,r2+1,r1,r1]
p=10**9+7
buf=1
cnt=0
l=[0]*(10**7+10)
inv=[0]*(10**7+10)
l[1]=1
for i in range(2,n1+3,1):
    l[i]=(l[i-1]*i)%p
print((((l[n1]*modinv(l[r2+1],p)*modinv(l[n1-r2-1],p))%p)-(l[n2]*modinv(l[r2+1],p)*modinv(l[n2-r2-1],p))-(l[n3]*modinv(l[r1],p)*modinv(l[n3-r1],p))+(l[n4]*modinv(l[r1],p)*modinv(l[n4-r1],p)))%p)

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

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

    def calc(r, c):
        return (pow(fact[c+1]*fact[r+1] % mod, mod-2, mod)*fact[r+c+2]-1) % mod

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


main()

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

fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    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 ncr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n]* (finv[r] * finv[n-r] %mod) %mod

def g(r,c):
    ans = 0
    for i in range(1,r+2):
        
        ans += ncr(i+c,c)
        ans %=mod
    return ans

ncr_pre()
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)
print(ans % mod)

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

def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1

    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD

    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if __name__ == "__main__":
    main()

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

def init_mod_c(lim=10**7, mod=10**9+7):
    fact = [1, 1] + [0] * (lim-1)
    fact_inv = [1, 1] + [0] * (lim-1)
    inv = [0, 1] + [0] * (lim-1)
    
    for i in range(2, lim+1):
        fact[i] = fact[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod

    def mod_c(n, m):
        if n < m or n < 0 or m < 0: return 0
        return fact[n] * (fact_inv[m] * fact_inv[n-m] % mod) % mod

    return mod_c

comb = init_mod_c()
pc = lambda r, c: comb(r+c, min(r, c))

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

print(ans)

Solution (Python):
r1,c1,r2,c2=map(int,input().split())
r2+=1
c2+=1
N=2*(10**6)+2
mod=10**9+7
fac=[1]*(N+2)
inv=[1]*(N+2)
t=1
for i in range(1,N+2):
    t*=i
    t%=mod
    fac[i]=t
t=pow(fac[N+1],mod-2,mod)
for i in range(N+1,0,-1):
    inv[i]=t
    t*=i
    t%=mod
def comb(n,r):
    return fac[n]*inv[n-r]*inv[r]%mod
print((comb(r2+c2,c2)-comb(r2+c1,c1)-comb(r1+c2,c2)+comb(r1+c1,c1))%mod)

Solution (Python):
u, l, d, r = map(int, input().split())
mod = 10 ** 9 + 7

def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y

def moddiv(a, b):
    _, inv, _ = extGCD(b, mod)
    return (a * inv) % mod

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

def comb(a, b):
    return moddiv(moddiv(f[a+b], f[a]), f[b])

ans = 0
d += 1
r += 1
ans += comb(d, r)
ans += comb(u, l)
ans -= comb(d, l)
ans -= comb(u, r)
print(ans % mod)

Solution (Python):
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

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

ans = 0

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

print(ans % MOD)

Solution (Python):

p = 10**9+7
kai_ = [1]
for i in range(1, 10 ** 7):
    kai_.append(kai_[-1] * i % p)


def kai(x):
    return kai_[x]


def comb(a, b):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai(a)
    c *= pow(kai(b), p - 2, p)
    c *= pow(kai(a - b), p - 2, p)
    return c % p


r1, c1, r2, c2 = [int(i) for i in input().split()]


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


print((s(r2, c2) - s(r2, c1 - 1) - s(r1 - 1, c2) + s(r1 - 1, c1 - 1)) % p)