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



Sample input:
1 1 2 2


Sample output:
14

Submission status: Accepted

Solution code:
mod = 10**9+7


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    # a*x+y*mod = 1
    return (mod+x % mod) % mod


max_num = 2*10**6+100
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

for i in range(2, max_num):
    fact[i] = fact[i-1] * i % mod
    ifact[i] = ifact[i-1] * inv(i, mod) % mod


def cmb(x, y):
    return fact[x] * ifact[y] * ifact[x-y] % mod


def solve(r, c):
    ans = 0
    for i in range(r+1):
        ans += cmb(c+i+1, c)
        ans %= mod
    return ans


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

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

print(ans)

Submission status: Accepted

Solution code:
r1,c1,r2,c2=map(int,input().split())
a=r2-r1+1
b=c2-c1+1
m=max(a,b)
n=min(a,b)
mod=10**9+7
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a
def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod
def f(x,y):
  return comb(x+y+2,y+1,mod)-1
 
print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%mod)

Submission status: Accepted

Solution code:
nn = 2002002
P = 10**9+7
fa = [1]
for i in range(1, nn): fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, nn)[::-1]: fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]
f = lambda a, b: fa[a+b+2] * fainv[a+1] * fainv[b+1] % P - 1
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)

Submission status: Accepted

Solution code:


def pow_mod(x, y):
    MOD = 1000000007
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD

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

  points = {r2 + c2 + 2, r2 + 1, c2 + 1, r2 + c1 + 1, c1, r1 + c2 + 1, r1, r1 + c1}

  factorial_map = {0: 1}
  for i in range(1, r2 + c2 + 3):
    factorial_map[i] = (factorial_map[i - 1] * i) % MOD
    if i > 1 and (i - 2) not in points:
      del factorial_map[i-2]

  a = 1
  a *= factorial_map[r2 + c2 + 2]
  a %= MOD
  a *= pow_mod(factorial_map[r2 + 1], MOD - 2)
  a %= MOD
  a *= pow_mod(factorial_map[c2 + 1], MOD - 2)
  a %= MOD

  b = 1
  b *= factorial_map[r2 + c1 + 1]
  b %= MOD
  b *= pow_mod(factorial_map[r2 + 1], MOD - 2)
  b %= MOD
  b *= pow_mod(factorial_map[c1], MOD - 2)
  b %= MOD

  c = 1
  c *= factorial_map[r1 + c2 + 1]
  c %= MOD
  c *= pow_mod(factorial_map[r1], MOD - 2)
  c %= MOD
  c *= pow_mod(factorial_map[c2 + 1], MOD - 2)
  c %= MOD

  d = 1
  d *= factorial_map[r1 + c1]
  d %= MOD
  d *= pow_mod(factorial_map[r1], MOD - 2)
  d %= MOD
  d *= pow_mod(factorial_map[c1], MOD - 2)
  d %= MOD

  ans = a
  ans -= b
  ans %= MOD
  ans -= c 
  ans %= MOD
  ans += d
  ans %= MOD

  print(ans)


if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

MOD = 10**9 + 7


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


def pathes(x, y):
    xf = None
    yf = None
    xyf = None
    temp = 1
    for i in range(1, x + y + 1):
        temp = (temp*i) % MOD
        if i == x:
            xf = temp
        if i == y:
            yf = temp
        if i == x + y:
            xyf = temp

    return xyf * modinv(xf * yf % MOD, MOD)


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

    a = (pathes(r1, c1) - 1) % MOD
    b = (pathes(r1, c2 + 1) - 1) % MOD
    c = (pathes(r2 + 1, c1) - 1) % MOD
    d = (pathes(r2 + 1, c2 + 1) - 1) % MOD

    print((d - c - b + a) % MOD)


main()

Submission status: Accepted

Solution code:
a,x,b,y=map(int,input().split());m=10**9+7;N=2000010;F=[1 for i in range(N+1)]
def v(x):return pow(x,m-2,m)
for i in range(N):F[i+1]=-~i*F[i]%m
def f(r,c):return F[r+c]*v(F[r])*v(F[c])%m
print((f(b+1,y+1)-f(b+1,x)-f(a,y+1)+f(a,x))%m)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
lr, lc, rr, rc = map(int, input().split())
mod = 10 ** 9 + 7
class Factorial:
  def __init__(self, n, 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] % mod * self.i[k] % mod
f = Factorial(rr + rc + 1, mod)
res = 0
for i in range(lr, rr + 1):
  res += f.combi(i + rc + 1, i + 1)
  res %= mod
for i in range(lr, rr + 1):
  res -= f.combi(i + lc, i + 1)
  res %= mod
print(res)

Submission status: Accepted

Solution code:

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

mod = 10 ** 9 + 7
MAX = (10**6)*2 + 100
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

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



def cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()

ans = 0
for c in range(c1, c2+1):
    ans += ((r2+1)*fac[r1]*fac[c+r2+1]-r1*fac[r2+1]*fac[c+r1])*finv[c]*finv[r1]*finv[r2+1]*inv[c+1]
    ans %= mod
    
print(ans)

Submission status: Accepted

Solution code:
r1,c1,r2,c2=map(int,input().split());mod=10**9+7;N=2000010
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])%mod
def f(r,c):return (Fact[r+c]*inv(Fact[r])*inv(Fact[c]))%mod
print((f(r2+1,c2+1)-f(r2+1,c1)-f(r1,c2+1)+f(r1,c1))%mod)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
import math

MOD = 10**9 + 7


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


# def pathes(x, y):
#     xf = None
#     yf = None
#     xyf = None
#     temp = 1
#     for i in range(1, x + y + 1):
#         temp *= i % MOD
#         if i == x:
#             xf = temp
#         if i == y:
#             yf = temp
#         if i == x + y:
#             xyf = temp
#     # xf = math.factorial(x) % MOD
#     # yf = math.factorial(y) % MOD
#     # xyf = math.factorial(x + y) % MOD

#     return xyf * modinv(xf * yf % MOD, MOD)


def pathes(rf, cf, rcf):
    return rcf * modinv((rf * cf) % MOD, MOD)


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

    f = [1 for _ in range(r2 + c2 + 2 + 1 + 1)]

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

    a = (pathes(f[r1], f[c1], f[r1 + c1]) - 1) % MOD
    b = (pathes(f[r1], f[c2 + 1], f[r1 + c2 + 1]) - 1) % MOD
    c = (pathes(f[r2 + 1], f[c1], f[r2 + 1 + c1]) - 1) % MOD
    d = (pathes(f[r2 + 1], f[c2 + 1], f[r2 + c2 + 2]) - 1) % MOD

    print((d - c - b + a) % MOD)


main()

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def f(r,c):
    d = c
    prod = 1
    div = 1
    divacc = 1
    for i in range(r-1):
        prod = (prod*d)%R
        divacc = (divacc*div)%R
        d += 1
        div += 1
    ret = (prod*modinv2(divacc,R))%R
    #ddprint("f r {} c {} ret {}".format(r,c,ret))
    return ret

r1,c1,r2,c2 = inm()
r1 += 1
c1 += 1
r2 += 1
c2 += 1
print((f(r2+1,c2+1)-f(r2+1,c1)-f(r1,c2+1)+f(r1,c1))%R)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

class Combination(object):
	def __init__(self, N, con):
		self.fac = [0] * (N + 1)
		self.inv = [0] * (N + 1)
		self.finv = [0] * (N + 1)
		self.fac[0], self.fac[1] = 1, 1
		self.inv[1] = 1
		self.finv[0], self.finv[1] = 1, 1

		# 前計算
		for i in range(2, N + 1):
			self.fac[i] = self.fac[i - 1] * i % con
			self.inv[i] = self.inv[con % i] * (con - (con // i)) % con
			self.finv[i] = self.finv[i - 1] * self.inv[i] % con

	def com(self, N, k):
		return (self.fac[N] * self.finv[k] * self.finv[N - k]) % con

#処理内容
def main():
	r1, c1, r2, c2 = getlist()
	Com1 = Combination(r1 + c2 + 1, con)
	Com2 = Combination(r1 + c1, con)
	ans = 0
	val1 = Com1.com(r1 + c2 + 1, r1 + 1)
	val2 = Com2.com(r1 + c1, r1 + 1)
	ans += val1 - val2
	for R in range(r1, r2):
		inv = pow(R + 2, con - 2, con)
		val1 = (val1 * (R + c2 + 2) * inv) % con
		val2 = (val2 * (R + c1 + 1) * inv) % con
		ans += val1 - val2
		ans %= con
	
	ans %= con
	print(ans)
	 #mod conにおける逆元


	


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def f(i, j):
    Fij = modFacts[i + j]
    Ii = invs[i]
    Ij = invs[j]
    rst = (Fij * Ii * Ij) % MOD
    return rst


def g(r1, r2, y):
    rst = 0
    for x in range(r1, r2 + 1):
        rst += f(x + 1, y)
        rst %= MOD
    return rst


r1, c1, r2, c2 = map(int, input().split())
modFacts, invs = prepare(max(r1, c1, r2, c2) * 2 + 1)


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


print(ans % MOD)

Submission status: Accepted

Solution code:
def main():
    mod=1000000007
    r1,c1,r2,c2=map(int,input().split())
    Fact=[1] #階乗
    n=r2+c2+1
    for i in range(1,n+1):
        Fact.append(Fact[i-1]*i%mod)
    Finv=[0]*(n+1) #階乗の逆元
    Finv[-1]=pow(Fact[-1],mod-2,mod)
    for i in range(n-1,-1,-1):
        Finv[i]=Finv[i+1]*(i+1)%mod
    def comb(n,r):
        if n<r:
            return 0
        return Fact[n]*Finv[r]*Finv[n-r]%mod
    def f(r,c):
        ret=0
        for i in range(r+1):
            ret+=comb(c+i+1,c)
            ret%=mod
        return ret
 
    print((f(r2,c2)-f(r2,c1-1)-f(c2,r1-1)+f(r1-1,c1-1))%mod)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def ncr(n, r): 
    p = 10**9 + 7
    # initialize numerator 
    # and denominator 
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p
    return (num * pow(den,  
            p - 2, p)) % p
  
r1, c1, r2, c2 = [int(i) for i in input().split()]
r1 += 1
c1 += 1
r2 += 1
c2 += 1
print((ncr(r2 + c2, c2) - ncr(r2 + c1 -1, c1-1) - ncr(c2+r1-1, r1-1) + ncr(r1+c1-2, c1-1))%(10**9+7))

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

def getFact(n, MOD):
    fact = 1
    for i in range(1, n+1):
        fact = (fact * i) % MOD
    return fact
def getFacts(n, MOD):
    facts = [1] * (n+1)
    for x in range(2, n+1):
        facts[x] = (facts[x-1] * x) % MOD
    return facts
def getInvFacts(n, MOD):
    invFacts = [0] * (n+1)
    invFacts[n] = pow(getFact(n, MOD), MOD-2, MOD)
    for x in reversed(range(n)):
        invFacts[x] = (invFacts[x+1] * (x+1)) % MOD
    return invFacts

facts = getFacts(2*10**6+3, MOD)
invFacts = getInvFacts(10**6+3, MOD)

def f(r, c):
    ans = facts[r+c] * invFacts[r] * invFacts[c]
    return ans % MOD

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

print(ans)

Submission status: Accepted

Solution code:
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
fi = {}


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


a1 = (C + 2) * f[c + 1] * f[C + R + 2] - (c + 1) * f[C + 2] * f[c + R + 1]
a1 *= inv(f[c + 1]) * inv(f[C + 2]) * inv(f[R + 1])
a2 = (C + 2) * f[c + 1] * f[C + r + 1] - (c + 1) * f[C + 2] * f[c + r]
a2 *= inv(f[c + 1]) * inv(f[C + 2]) * inv(f[r])
ans = a1 - a2
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
r, c, R, C = [int(_) for _ in input().split()]
mod = 10**9 + 7

f = [1] * (3 * 10**6 + 10)
for i in range(1, 3 * 10**6 + 10):
    f[i] = i * f[i - 1] % mod
fi = {}


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


a1 = (C + 2) * f[c + 1] * f[C + R + 2] - (c + 1) * f[C + 2] * f[c + R + 1]
a1 *= inv(f[c + 1]) * inv(f[C + 2]) * inv(f[R + 1])
a2 = (C + 2) * f[c + 1] * f[C + r + 1] - (c + 1) * f[C + 2] * f[c + r]
a2 *= inv(f[c + 1]) * inv(f[C + 2]) * inv(f[r])
ans = a1 - a2
ans %= mod
print(ans)

Submission status: Accepted

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

fact = [1]*(n+1)
rfact = [1]*(n+1)
r = 1
for i in range(1, n+1):
  fact[i] = r = r * i % mod
rfact[n] = r = pow(fact[n], mod-2, mod)
for i in range(n, 0, -1):
  rfact[i-1] = r = r * i % mod

def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % mod

ans = 0
for r in range(r1,r2+1):
  mini = (((c2+1) * comb(r + c2 + 1, r) - c1 * comb(c1+r,r)) * pow(r+1,mod-2,mod)) % mod
  ans = (ans + mini) % mod
print(ans % mod)

Submission status: Accepted

Solution code:
r1,c1,r2,c2 = map(int,input().split())
MOD = 10**9 + 7
MAX = 2 * (10**6) + 1

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]
fac[0] = 1
fac[1] = 1
finv[0] = 1
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

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

ans = com(r1+c1, r1)
if r1 == r2 or c1 == c2:
	if r1 != r2:
		for r in range(r1+1, r2+1):
			ans = (ans + com(r+c1, r)) % MOD
	if c1 != c2:
		for c in range(c1+1, c2+1):
			ans = (ans + com(r1+c, r1)) % MOD
	print(ans % MOD)
	exit()

diff_c = c2 - c1
keisu = [com(diff_c+i, i+1) for i in range(r2 - r1)]
t_keisu = [0]
for k in keisu:
	t_keisu.append((t_keisu[-1] + k) % MOD)
for r in range(r1+1, r2+1):
	tmp = com(r+c1, r)
	ans = (ans + tmp + tmp * t_keisu[r1 - r]) % MOD

diff_r = r2 - r1
keisu = [com(diff_r+i, i+1) for i in range(c2 - c1)]
t_keisu = [0]
for k in keisu:
	t_keisu.append((t_keisu[-1] + k) % MOD)
for c in range(c1 + 1, c2 + 1):
	tmp = com(r1+c, c)
	ans = (ans + tmp + tmp * t_keisu[c1 - c]) % MOD

print(ans)

Submission status: Accepted

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

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

    # comb init
    nmax = 2 * 10 ** 6 + 5  # change here
    fac = [0] * nmax
    finv = [0] * nmax
    inv = [0] * nmax
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    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 comb(n, r):
        if n < r:
            return 0
        else:
            return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def getInvs(n, MOD):
    invs = [0] * (n+1)
    invs[1] = 1
    for x in range(2, n+1):
        invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
    return invs
invs = getInvs(c2+r2+1, MOD)

combi_c2 = []
combi_c1_1 = []
for i in range(c2+r2+2):
    if i <= c2:
        combi_c2.append(int(i == c2))
    else:
        c = combi_c2[-1]
        combi_c2.append((c * i * invs[i-c2+1]) % MOD)
    if i <= c1-1:
        combi_c1_1.append(int(i == c1-1))
    else:
        c = combi_c1_1[-1]
        combi_c1_1.append((c * i * invs[i-c1]) % MOD)

ans = 0
t = 1
b = 1
for x in range(r2+2, c2+r2+2):
    t *= x
    t %= MOD
for x in range(1, c2+1):
    t *= invs[x]
    t %= MOD
for x in range(r2+2, c1+r2+1):
    b *= x
    b %= MOD
for x in range(1, c1):
    b *= invs[x]
    b %= MOD

ans = t - b
ans %= MOD
for i in range(r2, r1, -1):
    t = (t * ((i+c2+1)-c2) * invs[(i+c2+1)]) % MOD
    b = (b * ((i+c1-1+1)-(c1-1)) * invs[i+c1]) % MOD
    ans += t - b
    ans %= MOD
print(ans)

Submission status: Accepted

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

n = 2000100
fact = [1]*(n+1)
inv = [1]*(n+1)
ifact = [1]*(n+1)
for i in range(1,n+1):
    fact[i] = fact[i-1]*i % MOD
    inv[i] = pow(i,MOD-2,MOD)
    ifact[i] = ifact[i-1]*inv[i] % MOD

def nCr(n,r):
    return fact[n] * ifact[r] * ifact[n-r] % MOD

def f(r,c):
    return nCr(r+c+2,c+1)-1
    
print((f(r2,c2) - f(r2,c1-1) - f(r1-1,c2) + f(r1-1,c1-1)) % MOD)

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
m=10**9+7
s=[pow(i,m-2,m)for i in range(10**6+2)]
def f(x,y):
    p,q=x,x
    for i in range(2,y+1):
        q=(q*(x+i-1)*s[i])%m
        p=(p+q)%m
    return p
print((f(c+1,d+1)-f(a,d+1)-f(c+1,b)+f(a,b))%m)

Submission status: Accepted

Solution code:
r1,c1,r2,c2 = map(int,input().split())
mod = 10**9 + 7
def factorial(N,MOD,r=True):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1,N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N],MOD-2,MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    if r:
        return fact,rfact
    else:
        return fact
fact,rfact = factorial(r2+c2+1,mod)
def perm(n,k): #上のfactorialと併用
    return fact[n]*rfact[n-k]%mod
def comb(n,k): #上のfactorialと併用
    return fact[n]*rfact[k]*rfact[n-k]%mod
ans = comb(r1+c1,r1)
#print(ans)
for i in range(r1+1,r2+1):
    ans += comb(i+c1,c1)*comb(r2-c1+c2+1-i,r2-i+1)
    ans %= mod
    #print(ans)
#print(-1)
for i in range(c1+1,c2+1):
    ans += comb(i+r1,r1)*comb(c2-r1+r2+1-i,c2-i+1)
    ans %= mod
    #print(ans)

print(ans)

Submission status: Accepted

Solution code:
def examA():
    S, T = LSI()
    A, B = LI()
    U = SI()
    if S==U:
        print(A-1,B)
    else:
        print(A,B-1)
    return

def examB():
    S = SI()
    N = len(S)
    ans = ""
    for i in range(N):
        ans += "x"
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    d = defaultdict(int)
    for a in A:
        d[a] += 1
        if d[a]>=2:
            print("NO")
            return
    print("YES")
    return

def examD():
    N, K = LI()
    P = LI()
    S = [0]*(N+1)
    for i in range(N):
        S[i+1] = S[i]+(P[i]+1)/2
    ans = 0
    for i in range(N-K+1):
        cur = S[i+K]-S[i]
        ans = max(ans,cur)
    print(ans)
    return

def examE():
    def ketadp(a,K):
        n = len(a)
        C = [i for i in range(K+1)]
        dp = defaultdict(int)
        dp[0, 0, 0] = 1
        for i, less, k in itertools.product(range(n), (0, 1), C):
            max_d = 9 if less else int(a[i])
            for d in range(max_d + 1):
                less_ = less or d < max_d
                if d==0:
                    dp[i + 1, less_, k] += dp[i, less, k]
                elif k<K:
                    dp[i + 1, less_, k+1] += dp[i, less, k]

        ans = sum(dp[n, less, K] for less in (0, 1))
        return ans
    N = SI()
    K = I()
    ans = ketadp(N,K)
    print(ans)
    return

def examF():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

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

        def comb(self, n, r, mod):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % mod
    r1, c1, r2, c2 = LI()
    C = combination(r2+c2+2,mod)
    H = [0]*(c2+2)
    W = [0]*(c2+2)
    for i in range(c2+1):
        H[i+1] = H[i] + C.comb(r2+i+1,i+1,mod)
        W[i + 1] = W[i] + C.comb(r1-1 + i + 1, i + 1, mod)

#    print(H,W)
    ans = H[c2+1] - H[c1] - W[c2+1] + W[c1]
    ans = (ans+mod)%mod
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examF()

"""

"""

Submission status: Accepted

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

MOD = 10 ** 9 + 7


def modInverse(x, p):
    # Fermat's little theorem
    return pow(x, p - 2, p)


def nCr(n, r, p):
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return num * modInverse(den, p) % p


def hockey(n, m):
    # sum i=0 to m of nCr(n + i, i) == nCr(n + m + 1, m)
    return nCr(n + m + 1, m, MOD)


tot1 = hockey(c2, r2 + 1) - hockey(c2, r1)
tot2 = hockey(c1 - 1, r2 + 1) - hockey(c1 - 1, r1)
print((tot1 - tot2) % MOD)

Submission status: Accepted

Solution code:
#f(r,c)=(r+c)_C_r
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)

Submission status: Accepted

Solution code:
r, c, R, C = [int(_) for _ in input().split()]
mod = 10**9 + 7

f = [1] * (3 * 10**6 + 10)
for i in range(1, 3 * 10**6 + 10):
    f[i] = i * f[i - 1] % mod
fi = {}


def comb(n, r):
    if r not in fi:
        fi[r] = pow(f[r], mod - 2, mod)
    if n - r not in fi:
        fi[n - r] = pow(f[n - r], mod - 2, mod)
    return (f[n] * fi[r] * fi[n - r]) % mod


a1 = (C + 2) * f[c + 1] * f[C + R + 2] - (c + 1) * f[C + 2] * f[c + R + 1]
a1 *= pow(R + 1, mod - 2, mod) * pow(f[c + 1], mod - 2, mod) * pow(
    f[C + 2], mod - 2, mod) * pow(f[R], mod - 2, mod)
a2 = (C + 2) * f[c + 1] * f[C + r + 1] - (c + 1) * f[C + 2] * f[c + r]
a2 *= pow(r, mod - 2, mod) * pow(f[c + 1], mod - 2, mod) * pow(
    f[C + 2], mod - 2, mod) * pow(f[r - 1], mod - 2, mod)
ans = a1 - a2
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def cmb(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
'''
p = 10 ** 9 + 7
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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


#a = list(map(int, input().split()))

x1,y1,x2,y2 = list(map(int, input().split()))


p = 10 ** 9 + 7
N = 2 * 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

def cmb2(a,b,p):
    return cmb(a+b+2,a+1,p)
    
print((cmb2(x2,y2,p) - cmb2(x1-1,y2,p) -cmb2(x2,y1-1,p) + cmb2(x1-1,y1-1,p))%p)
#print(cmb2(x2,y2,p), cmb2(x1-1,y2,p) ,cmb2(x2,y1-1,p) ,cmb2(x1-1,y1-1,p))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
MAX_N = 2 * 10**6 + 1

# Construct factorial table
fac = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * (i) % MOD

fac_inv = [1] + [0] * MAX_N
# Femrmat's little theorem says a**(p-1) mod p == 1
# then, a * a**(p-2) mod p == 1
# it means that a**(p-2) is the inverse element
# Here, Get 1 / n! first
fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD

def get_rect_sum(r, c):
    total = 0
    for i in range(1, c+2):
        total += mod_nCr(r + i, r)
    return total

r1, c1, r2, c2 = [int(item) for item in input().split()]
ans = get_rect_sum(r2, c2)
ans += get_rect_sum(r1 - 1, c1 - 1)
ans -= get_rect_sum(r2, c1 - 1)
ans -= get_rect_sum(r1 - 1, c2)
ans %= MOD
print(ans)

Submission status: Accepted

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


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

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


def comb_sum(i, j):
    return nck(i+j+2, i+1)

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

Submission status: Accepted

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

# 二項係数 mod P

mod = 10**9+7

m = r2+c2 +10 
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod


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

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

Submission status: Accepted

Solution code:
def main():
    r1, c1, r2, c2 = map(int, raw_input().split())
    MOD = 10 ** 9 + 7

    mod = 10 ** 9 + 7  # 出力の制限
    N = 10 ** 4
    g1 = [1, 1]  # 元テーブル
    g2 = [1, 1]  # 逆元テーブル
    inverse = [0, 1]  # 逆元テーブル計算用テーブル

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

    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


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

    print(ans % MOD)


if __name__ == '__main__':
    main()