Problem:
 Score : 600 points    Problem Statement Snuke is standing on a two-dimensional plane. In one operation, he can move by 1 in the positive x -direction, or move by 1 in the positive y -direction.  Let us define a function f(r, c) as follows:   f(r,c) := (The number of paths from the point (0, 0) to the point (r, c) that Snuke can trace by repeating the operation above)   Given are integers r_1 , r_2 , c_1 , and c_2 .
Find the sum of f(i, j) over all pair of integers (i, j) such that r_1 ≤ i ≤ r_2 and c_1 ≤ j ≤ c_2 , and compute this value modulo (10^9+7) .      Constraints  1 ≤ r_1 ≤ r_2 ≤ 10^6  1 ≤ c_1 ≤ c_2 ≤ 10^6  All values in input are integers.         Input Input is given from Standard Input in the following format:  r_1  c_1  r_2  c_2       Output Print the sum of f(i, j) modulo (10^9+7) .        Sample Input 1 1 1 2 2      Sample Output 1 14  For example, there are two paths from the point (0, 0) to the point (1, 1) : (0,0) → (0,1) → (1,1) and (0,0) → (1,0) → (1,1) , so f(1,1)=2 .  Similarly, f(1,2)=3 , f(2,1)=3 , and f(2,2)=6 . Thus, the sum is 14 .       Sample Input 2 314 159 2653 589      Sample Output 2 602215194

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

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

n = max(r1, c1, r2, c2)
f = Factorial(n * 2 + 1, mod)
res = 0
for i in range(r1, r2 + 1):
  res += f.combi(c2 + i + 1, i + 1) - f.combi(c1 + i, i + 1)
  res %= mod
print(res)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect
from functools import reduce

def main():
    mod = 10 ** 9 + 7
    def comb(n, r):
        numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
        denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
        return numerator * pow(denominator, mod - 2, mod) % mod
    r_1, c_1, r_2, c_2 = MI()
    
    g_r2c2 = (comb(r_2 + c_2 + 2, c_2 + 1) - 1) % mod
    g_r2c1m1 = (comb(r_2 + c_1 + 1, c_1) - 1) % mod
    g_r1m1c2 = (comb(r_1 + c_2 + 1, c_2 + 1) - 1) % mod
    g_r1m1c1m1 = (comb(r_1 + c_1, c_1) - 1) % mod
    ans = (((((g_r2c2 - g_r2c1m1) % mod) - g_r1m1c2) % mod) + g_r1m1c1m1) % mod

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7







lim = 2 * (10 ** 6) + 7 
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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

def cmb(n, r):
    if (r < 0) or (n < r):
        return 0

    if r == 0:
        return 1

    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % mod

"""
g(r,c) を 0 ≤ i ≤ r かつ 0 ≤ j ≤ c を満たす全ての整数の組 (i,j) に対する f(i,j) の総和とする。
ここでf(r + 1, c) = f(r, c) + f(r, c - 1)...f(r, 0)
f(r, c)からr方向へ1つ（一通り）
f(r, c - 1)からr方向へ1つ, c方向に1つ（一通り）
...

つまりf(r2 + 1, c2) = f(r2, c) + f(r2, c - 1) + ... f(r2, 0)
これをf(0, c2)からf(r2 + 1, c2)まで求めればg(r2, c2)が求まる
"""
r1, c1, r2, c2 = getNM()

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

Solution (Python):
mod = 10 ** 9 + 7
n = 2000010
fact = [1] * (n + 1)
ifact = [1] * (n + 1)

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

for i in range(n):
    fact[i + 1] = fact[i] * (i + 1) % mod
    if i + 1 in [r1, c1, r2 + 1, c2 + 1]:
        ifact[i + 1] = pow(fact[i + 1], mod - 2, mod)

def comb(x, y):
    return (fact[x + y] * ifact[x] * ifact[y]) % mod


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

Solution (Python):
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]
n=max(r1,c1,r2,c2)
for i in range(2,2*10**6+2):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)
ans=0
for k in range(r1,r2+1):
  tmp=cmb(k+1+c2,c2,mod)-cmb(k+1+c1-1,c1-1,mod)
  ans+=tmp
  ans%=mod
print(ans)

Solution (Python):
from functools import reduce
def C(n,r):
    if not 0<=r<=n: return 0
    r=min(r,n-r)
    N=reduce(lambda x,y: x*y%M, range(n,n-r,-1),1)
    D=reduce(lambda x,y: x*y%M, range(1,r+1),1)
    return N*pow(D,M-2,M)%M
def f(r,c): return C(r+c,c)
M=10**9+7
a,b,c,d=map(int, input().split())
print((f(c+1,d+1)-f(a,d+1)-f(c+1,b)+f(a,b))%M)

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

MOD = 10 ** 9 + 7
MAX = 2 * 10 ** 6 + 10
modinv = lambda a, mod=MOD: pow(a, mod - 2, mod)
fac, inv = [1] * MAX, [1] * MAX
for i in range(1, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = modinv(fac[i])


def comb(n, k, error=0):
    if not 0 <= k <= n:
        return error
    return fac[n] * inv[k] * inv[n - k] % MOD


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

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


class Comb:
    def __init__(self, n, mod=pow(10, 9)+7, f=True, i=False, version=False):
        self.n = n
        self.mod = mod
        self.mod_inv = mod-2 if version else -1
        self.factorial_table = None
        self.inverse_table = None
        if f: self.get_factorial()
        if i: self.get_inverse()
        
    def get_factorial(self):
        self.factorial_table = [1]*(self.n+1)
        for i in range(1, self.n+1):
            self.factorial_table[i] = self.factorial_table[i-1]*i%self.mod
        self.inverse_table = None
    
    def get_inverse(self):
        mod = self.mod
        mod_inv = self.mod_inv
        self.inverse_table = [1]*(self.n+1)
        for i in range(self.n+1):
            self.inverse_table[i] = pow(self.factorial_table[i], mod_inv, mod)
    
    def factorial(self, n):
        if self.factorial_table == None:
            return None
        return self.factorial_table[n]
    
    def inverse(self, n):
        if self.inverse_table == None:
            return None
        return self.inverse_table[n]   
    
    def permutation(self, n, k):
        if self.factorial_table == None:
            return None
        mod = self.mod
        mod_inv = self.mod_inv
        if self.inverse_table == None:
            return self.factorial_table[n]*pow(self.factorial_table[n-k], mod_inv, mod)%mod
        return self.factorial_table[n]*self.inverse_table[n-k]%mod
            
    def comb(self, n, k):
        if self.factorial_table == None:
            return None
        mod = self.mod
        mod_inv = self.mod_inv
        if self.inverse_table == None:
            res = self.factorial_table[n]*pow(self.factorial_table[n-k], mod_inv, mod)%mod\
                                    *pow(self.factorial_table[k], mod_inv, mod)%mod
        else:
            res = self.factorial_table[n]*self.inverse_table[n-k]%mod\
                                    *self.inverse_table[k]%mod
        return res
    
    def recomb(self, n, k):
        if n+k-1 > self.n:
            return None
        return self.comb(n+k-1, k)


def main():
    r1, c1, r2, c2 = map(int, input().split())
    comb = Comb(10**6*2+1, version=True)
    mod = pow(10, 9) + 7

    ans = 0
    comb1, comb2 = comb.comb(c1+r2+1, r2+1), comb.comb(c1+r1, r1)
    for key in range(c1, c2+1):
        sub = (((r2+1) * comb1 - r1 * comb2) * pow(key+1, mod-2, mod)) % mod
        ans = (ans + sub) % mod

        comb1 = comb1 * (key + r2 + 2) * pow(key+1, mod-2, mod) % mod
        comb2 = comb2 * (key + r1 + 1) * pow(key+1, mod-2, mod) % mod


    print(ans)


    
if __name__ == "__main__":
    main()

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

mod = 1000000007

def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

def fac(n):
    ret = 1
    for i in range(1, n + 1):
        ret = (ret * i) % mod
    return ret

def facinv(n):
    return pow(fac(n), mod - 2)

def cmb(n, k):
    if k < 0 or k > n:
        return 0
    return ((fac(n) * facinv(k)) % mod * facinv(n - k)) % mod

def rect(r, c):
    return cmb(r + c, c)

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

Solution (Python):
MOD=10**9+7
def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;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

def COM(n,r):
    if n<r or r<0:
        return 0
    else:
        return ((fac[n]*finv[r])%MOD*finv[n-r])%MOD
        
r1,c1,r2,c2=map(int,input().split())

fac,finv,inv=facinv(r2+c2+1)

ans=0

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

Solution (Python):
mod = 10 ** 9 + 7
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
r1, c1, r2, c2 = map(int, input().split())
fa = [1] * (r2 + c2 + 3)
fi = [1] * (r2 + c2 + 3)
for i in range(1, r2 + c2 + 3):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
def ans(r, c):
    return fa[r + c + 2] * fi[r + 1] * fi[c + 1] % mod - 1
print((ans(r2, c2) - ans(r2, c1 - 1) - ans(r1 - 1, c2) + ans(r1 - 1, c1 - 1)) % mod)

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))+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 )
a,b,c,d=map(int,input().split())
print((cmb(c+d+2,c+1,mod)-cmb(d+1+a,a,mod)-cmb(b+c+1,c+1,mod)+cmb(a+b,a,mod))%mod)

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

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

f = Factorial(max(r1, c1, r2, c2) * 3, mod)

res = 0
for i in range(r1, r2 + 1):
  res += (f.combi(i + c2 + 1, c2 + 1) * (c2 + 1) - f.combi(i + c1, c1) * c1) % mod * pow(i + 1, mod - 2, mod) % mod
  res %= mod
print(res)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    def calc(c):
        prev = 1
        cur = 1
        comb1 = 0
        comb2 = 0

        for i in range(1, r1 + 1):
            cur = prev * (c + i)
            cur %= MOD
            cur *= pow(i, MOD - 2, MOD)
            cur %= MOD
            comb1 += cur
            comb1 %= MOD
            prev = cur

        comb2 = comb1

        for i in range(r1 + 1, r2 + 2):
            cur = prev * (c + i)
            cur %= MOD
            cur *= pow(i, MOD - 2, MOD)
            cur %= MOD
            comb2 += cur
            comb2 %= MOD
            prev = cur

        return comb1, comb2

    comb1, comb2 = calc(c1-1)
    comb3, comb4 = calc(c2)

    ans = comb4 - comb2 - comb3 + comb1
    ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
mod = 10**9+7
def cmb(n,k):
    return fac[n]*inv_fac[n-k]*inv_fac[k] % mod
def g(r,c):
    x = 0
    for i in range(1,r+2):
        x += cmb(c+i,i)
    x %= mod
    return x

r1,c1,r2,c2 = map(int,input().split())
N = r2+c2+1
fac = [1]
for i in range(1,N+1):
    fac.append(fac[-1]*i % mod)
inv_fac = [pow(fac[N],mod-2,mod)]
for i in range(1,N+1)[::-1]:
    inv_fac.append(inv_fac[-1]*i % mod)
inv_fac = inv_fac[::-1]
print((g(r2,c2)-g(r2,c1-1)-g(r1-1,c2)+g(r1-1,c1-1))% mod)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

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

    
    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

    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 )

    def g(r,c):
        tmp=cmb(r+1+c+1,r+1)-1
        return tmp%mod

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

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

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


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

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 )

def g(r,c):
    tmp=cmb(r+1+c+1,r+1)-1
    return tmp%mod

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

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

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


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

N = 10**6*2+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 )

def g(r,c):
    tmp=cmb(r+1+c+1,r+1)-1
    return tmp%mod

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

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

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


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

N = 10**6*2+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 )

def g(r,c):
    tmp=cmb(r+1+c+1,r+1)-cmb(0+c+1,0)
    return tmp%mod

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

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

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


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

N = 10**6*2+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 )

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

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

Solution (Python):
import math

r1, c1, r2, c2 = map(int, input().split())
P = int(1e9+7)
kaizyo = [0]
kaizyo_inv = [0]
tmp = 1
for i in range(1, 2*max(r1, r2, c1, c2)+2):
    tmp = (tmp*i) % P
    kaizyo.append(tmp)
    kaizyo_inv.append(pow(tmp, P - 2, P))


def comb(n, r):
    if n < r or n==0:
        return 0
    elif n == r or r==0:
        return 1
    else:
        return kaizyo[n] * kaizyo_inv[r] * kaizyo_inv[n - r]


def solve_naive(r, c):
    if r < 0 or c < 0:
        return 0
    S = [[0] * (c+1) for _ in range(r+1)]
    for i in range(1, r + 1):
        for j in range(1, c + 1):
            S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + comb(i + j , i)
    return S[-1][-1]


def solve(r, c):
    if r < 0 or c < 0:
        return 0
    ret = 0
    for i in range(2, r + 2):
        ret = (ret + comb(i + c, i)) % P
    return ret



ans = (solve(r2, c2) - solve(r1 - 1, c2) -
       solve(r2, c1 - 1) + solve(r1 - 1, c1 - 1)) % P
print(ans)

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

MOD = 10 ** 9 + 7
N = r2 + c2 + 10
fact = [0 for _ in range(N)]
invfact = [0 for _ in range(N)]
fact[0] = 1
for i in range(1, N):
    fact[i] = fact[i - 1] * i % MOD

invfact[N - 1] = pow(fact[N - 1], MOD - 2, MOD)

for i in range(N - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD
def nCk(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return fact[n] * invfact[k] * invfact[n - k] % MOD
        
ans = nCk(r2 + c2 + 2, r2 + 1) - nCk(r2 + c1 + 1, r2 + 1) \
    - nCk(r1 + c2 + 1, c2 + 1) + nCk(r1 + c1, r1)
print(ans % MOD)

Solution (Python):
r1,c1,r2,c2 = map(int, input().split())
mod = int(1e9+7)



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

def init_cmb(Nmax):
    
    g1 = [1, 1] 
    g2 = [1, 1] 
    inverse = [0, 1] 

    for i in range(2, Nmax + 1):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)
    return g1, g2
  
g1, g2 = init_cmb(max(r1,r2) + max(c1,c2) + 10)

def solve(r1,c1,r2,c2):
  def f(r,c):
    return cmb(r+c,min(r,c))
  
  res = 0
  
  
  r2,c2 = r2, c2
  res += f(r2,c2)
  res -= f(r2,c1)
  res -= f(r1,c2)
  res += f(r1,c1)
  
  """
  for c in range(0,c2+1):
    res += (c+1) * cmb(r2+c, c)
    res %= mod
  for c in range(0,c1):
    res -= (c+1) * cmb(r2+c, c)
    res %= mod
  for r in range(0,r1):
    res -= (r+1) * cmb(c2+r,r)
    res %= mod
  for r in range(0,r1):
    res += (r+1) * cmb(c1-1+r,r)
    res %= mod
  """  
  return res % mod

def solve2(r1,c1,r2,c2):
  res = 0
  for r in range(r1,r2+1):
    for c in range(c1,c2+1):
      res += cmb(c+r,c)
      res %= mod
  return res


print(solve(r1,c1,r2+1,c2+1))

Solution (Python):
r1,c1,r2,c2 = map(int, input().split())
mod = int(1e9+7)



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

def init_cmb(Nmax):
    
    g1 = [1, 1] 
    g2 = [1, 1] 
    inverse = [0, 1] 

    for i in range(2, Nmax + 1):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)
    return g1, g2
  
g1, g2 = init_cmb(max(r1,r2) + max(c1,c2) + 10)

def solve(r1,c1,r2,c2):
  def f(r,c):
    return cmb(r+c,min(r,c))
  
  res = 0
  
  
  r2,c2 = r2, c2
  res += f(r2,c2)
  res -= f(r2,c1)
  res -= f(r1,c2)
  res += f(r1,c1)
  
  """
  for c in range(0,c2+1):
    res += (c+1) * cmb(r2+c, c)
    res %= mod
  for c in range(0,c1):
    res -= (c+1) * cmb(r2+c, c)
    res %= mod
  for r in range(0,r1):
    res -= (r+1) * cmb(c2+r,r)
    res %= mod
  for r in range(0,r1):
    res += (r+1) * cmb(c1-1+r,r)
    res %= mod
  """  
  return res % mod

def solve2(r1,c1,r2,c2):
  res = 0
  for r in range(r1,r2+1):
    for c in range(c1,c2+1):
      res += cmb(c+r,c)
      res %= mod
  return res


print(solve(r1,c1,r2+1,c2+1))

Solution (Python):
import sys
from functools import reduce
from operator import mul
from typing import Callable, ClassVar, Sequence, Type, TypeVar



T = TypeVar('T', bound='ModIntBase')


class ModIntBase:
    value: int
    mod: ClassVar[int]
    fac: ClassVar[Sequence[int]] = ()
    inv: ClassVar[Sequence[int]] = ()
    finv: ClassVar[Sequence[int]] = ()

    def __init__(self, value: int) -> None:
        self.value = value % self.mod

    def __hash__(self) -> int:
        return hash((self.value, self.mod))

    def __eq__(self, other) -> bool:
        if isinstance(other, self.__class__):
            return self.value == other.value
        else:
            return NotImplemented

    def __ne__(self, other) -> bool:
        if isinstance(other, self.__class__):
            return self.value != other.value
        else:
            return NotImplemented

    
    def __add__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__((self.value + other.value) % self.mod)
        else:
            return NotImplemented

    def __sub__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__((self.value - other.value) % self.mod)
        else:
            return NotImplemented

    def __mul__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__(self.value * other.value % self.mod)
        else:
            return NotImplemented

    def __truediv__(self, other):
        if isinstance(other, self.__class__):
            a = other.value
            b = self.mod
            u = 1
            v = 0
            while b:
                t = a // b
                a, b = b, a - t * b
                u, v = v, u - t * v
            return self.__class__(self.value * u % self.mod)
        else:
            return NotImplemented

    def __pow__(self, other):
        if isinstance(other, self.__class__):
            v = 1
            a = self.value
            b = other.value
            mod = self.mod
            while b > 0:
                if b & 1:
                    v = v * a % mod
                a = a * a % mod
                b >>= 1
            return self.__class__(v)
        else:
            return NotImplemented

    @classmethod
    def comb(cls, n: int, k: int):
        if n < k:
            return cls(0)
        if n < 0 or k < 0:
            return cls(0)

        if n < len(cls.fac):
            return cls(cls.fac[n] * (cls.finv[k] * cls.finv[n - k] % cls.mod) % cls.mod)
        else:
            k = min(k, n - k)
            a = reduce(mul, map(cls, range(n - k + 1, n + 1)), cls(1))
            b = reduce(mul, map(cls, range(1, k + 1)), cls(1))
            return a / b

    def __repr__(self) -> str:
        return f'{self.__class__.__name__}({self.value!r})'

    def __str__(self) -> str:
        return str(self.value)


def mod_comb_init(max_: int) -> Callable[[Type[T]], Type[T]]:
    def _mod_comb_init(cls: Type[T]) -> Type[T]:
        mod: int = cls.mod
        assert max_ < mod

        fac = cls.fac = [0] * max_
        finv = cls.finv = [0] * max_
        inv = cls.inv = [0] * 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

        return cls
    return _mod_comb_init


@mod_comb_init(2 * 10 ** 6 + 1)
class ModInt(ModIntBase):
    mod = 1000000007  


def resolve(in_):
    r1, c1, r2, c2 = map(int, next(in_).strip().split())
    
    ans = (
        ModInt.comb((r2 + 1) + (c2 + 1), c2 + 1)
        - ModInt.comb((r2 + 1) + c1, c1)
        - ModInt.comb(r1 + (c2 + 1), c2 + 1)
        + ModInt.comb(r1 + c1, c1)
    )

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

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, r)

    MOD = 10 ** 9 + 7
    r1, c1, r2, c2 = map(int, input().split())
    r2 += 1
    c2 += 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):


def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

mod = 10**9 + 7
r1, c1, r2, c2 = map(int, input().split())
r2 += 1
c2 += 1
a1 = combination(r1+c1, r1)
a2 = combination(r2+c2, r2)
a3 = combination(r1+c2, r1)
a4 = combination(r2+c1, r2)
print((a1+a2-a3-a4)%mod)

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	r1,c1,r2,c2=MI()
	m=10**9+7

	ff=[1]

	for i in range(1,2*10**6+5):
		ff.append(ff[-1]*i%m)


	def f(r,c):
		return (ff[r+c]*pow(ff[r],m-2,m)*pow(ff[c],m-2,m))%m

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

	print(ans%m)



if __name__ == "__main__":
	main()

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	r1,c1,r2,c2=MI()
	m=10**9+7

	ff=[1]

	for i in range(1,2*10**6+5):
		ff.append(ff[-1]*i%m)


	def f(r,c):
		return (ff[r+c]*pow(ff[r],m-2,m)*pow(ff[c],m-2,m))%m

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

	print(ans%m)



if __name__ == "__main__":
	main()

Solution (Python):
a1,b1,a2,b2=map(int,input().split())

import sys
sys.setrecursionlimit(2000000000)

p = 10 ** 9 + 7
N = a2+b2+2  
R = max(a2+1,b2+1)
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

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

def comb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fact[n] * factinv[r] * factinv[n-r] % p

score=comb(a2+b2+2,a2+1,p)-comb(a2+b1+1,a2+1,p)-comb(a1+b2+1,a1,p)+comb(a1+b1,a1,p)
print(score%(10**9+7))

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

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

print(ans)

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

fac = [1, 1]
for i in range(2, table_len):
    fac.append(fac[-1] * i % MOD)
    
finv = [0] * table_len
finv[-1] = pow(fac[-1], MOD - 2, MOD)
for i in range(table_len-1, 0, -1):
    finv[i-1] = finv[i] * i % MOD

def comb(a, b):
    return fac[a+b] * finv[a] * finv[b] % MOD


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

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

fac = [1, 1]
for i in range(2, table_len):
    fac.append(fac[-1] * i % MOD)
    
finv = [0] * table_len
finv[-1] = pow(fac[-1], MOD - 2, MOD)
for i in range(table_len-1, 0, -1):
    finv[i-1] = finv[i] * i % MOD

def comb(a, b):
    return fac[a+b] * finv[a] * finv[b] % MOD


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