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:
import os
import sys


if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = [1]
    r = 1
    for inv in mod_invs(max, mod)[1:]:
        r = r * inv % mod
        ret.append(r)
    return ret


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


R1, C1, R2, C2 = list(map(int, sys.stdin.buffer.readline().split()))

comb = Combination(max=10 ** 6 * 2 + 100, mod=MOD)


# 解説
# ある要素に注目して残りを選ぶ数を数えると分かる
# ncr(n, r) == ncr(n-1,r) + (n-1,r-1)
# nhr(n, r) == sum([nhr(n-1,k) for k in range(r)])

# g(r, c) を f(i, j) (0<=i<=r, 0<=j<=c) の総和とすると
# g(R2, C2) - g(R1-1, C2) - g(R2, C1-1) + g(R1-1, C1-1)

def f(n, r):
    return comb.ncr(n + r, r)


# @debug
def g(r, c):
    ret = 0
    for i in range(1, c + 2):
        ret += f(r, i)
        ret %= MOD
    return ret


ans = g(R2, C2) - g(R1 - 1, C2) - g(R2, C1 - 1) + g(R1 - 1, C1 - 1)
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
fac = [1, 1]

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


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

    return fac[n] * pow(fac[r], mod-2, mod) * pow(fac[n-r], mod-2, mod) % mod


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


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


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

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# コンビネーション
mod = 10**9+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

NN = 3*10**6+6 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, NN + 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 = 0
for c in range(c1, c2+1):
    ans += cmb(c+r2+1, r2) - cmb(c+r1, r1-1)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def MI(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [LI() for _ in range(N)]
        return map(list, zip(*read_all))

#################

#0!~(n-1)!をmodしつつ求める
def fact_all(n,M=mod):
    f = [1]*n
    ans = 1
    for i in range(1,n):
        ans = (ans*i)%M
        f[i] = ans
    return f


#a!をmodしつつ求める
def fact(a,M=mod):
    ans = 1
    for i in range(2,a+1):
        ans = (ans*i)%M
    return ans


#互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]


#aの逆元(mod M)を求める（aとMは互いに素）
def mod_inv(a,M=mod):
    x = extgcd(a,M)[0]
    return (M+x%M)%M


#nCkをmodしつつ返す
def nCk(n,k,fact_list=[],inv_list=[],M=mod):
    if fact_list and inv_list:
        return (((fact_list[n]*inv_list[k])%M)*inv_list[n-k])%M
    else:
        x = fact(n,M)
        y1 = mod_inv(fact(k,M),M)
        y2 = mod_inv(fact(n-k,M),M)
        return (x*y1*y2)%M


def g(r,c):
    retval = 0
    for i in range(r+1):
        retval += nCk(i+c+1,c,fact_list,inv_list)
        retval %= mod
    return retval

r1,c1,r2,c2 = LI()
fact_list = fact_all(r2+c2+2)
inv_list = [mod_inv(f) for f in fact_list]

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

Submission status: Accepted

Solution code:
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        if n < r:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

comb = Combination(2 * 10 ** 6 + 5)

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

def main():
    r1, c1, r2, c2 = map(int, input().split())
    r1 -= 1
    c1 -= 1
    MOD = 10 ** 9 + 7
    ans = g(r2,c2)
    ans -= g(r2,c1)
    ans -= g(r1,c2)
    ans += g(r1,c1)
    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10**9 + 7

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

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

total = fact[r2 + c2 + 2] * inv_fact[r2 + 1] * inv_fact[c2 + 1] % mod
total -= fact[r1 + c2 + 1] * inv_fact[r1] * inv_fact[c2 + 1] % mod
total -= fact[r2 + c1 + 1] * inv_fact[c1] * inv_fact[r2 + 1] % mod
total += fact[r1 + c1] * inv_fact[r1] * inv_fact[c1] % mod

print(total % mod)

Submission status: Accepted

Solution code:
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

MOD=10**9+7
MAXN=2000000+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)

r1, c1, r2, c2=map(int, input().split())
s1=comb(r2+c2+2, r2+1)-1
s2=comb(r1+c2+1, r1)-1
s3=comb(r2+c1+1, r2+1)-1
s4=comb(r1+c1, r1)-1
print((s1-s2-s3+s4)%MOD)

Submission status: Accepted

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

class factorial:
  def __init__(self, n, p=10**9 + 7):
    self.__p  = p
    self.__fac  = [0] * (n+1)
    self.__inv  = [0] * (n+1)
    self.__finv = [0] * (n+1)

    self.__fac[0] = self.__fac[1] = 1
    self.__inv[1] = 1
    self.__finv[0] = self.__finv[1] = 1

    for i in range(2, n+1):
      self.__fac[i] = self.__fac[i-1] * i % p
      self.__inv[i] = p - self.__inv[p%i] * (p // i) % p
      self.__finv[i] = self.__finv[i-1] * self.__inv[i] % p
  
  def fact(self, n):
    return self.__fac[n]
  
  def perm(self, n, k):
    return self.__fac[n] * self.__finv[n-k] % self.__p
  
  def comb(self, n, k):
    return self.perm(n, k) * self.__finv[k] % self.__p

f = factorial(r2+c2+2)
print((f.comb(r2+c2+2, r2+1) + f.comb(r1+c1, r1) - f.comb(r1+c2+1, r1) - f.comb(c1+r2+1, c1)) % (10**9 + 7))

Submission status: Accepted

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

p = 10 ** 9 + 7
size = 1010000 * 2
f_list = [1] * size
for i in range(1, size):
    f_list[i] = (f_list[i - 1] * i) % p

def cmb(n, r):
    return f_list[n + r] * pow(f_list[n], p-2, p) * pow(f_list[r], p-2, p) % p

hole = cmb(r2 + 1, c2 + 1) - 1
rect1 = cmb(r2 + 1, c1) - 1
rect2 = cmb(r1, c2 + 1) - 1
duplicate = cmb(r1, c1) - 1
ans = (hole - rect1 - rect2 + duplicate) % p
print(ans)

Submission status: Accepted

Solution code:
def mod_combination(n, k, mod = 10 ** 9 + 7):
    def extended_gcd(a, b):
        if b == 0:
            return (a, 1, 0)
        d, x, y = extended_gcd(b, a % b)
        return (d, y, x - (a // b) * y)
    p, q = 1, 1
    for i in range(n - k + 1, n + 1):
        p = (p * i) % mod
    for i in range(2, k + 1):
        q = (q * i) % mod
    return p * (extended_gcd(q, mod)[1] % mod) % mod

mod = 10 ** 9 + 7

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

def f(i, j):
    return mod_combination(i + j, i)

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

Submission status: Accepted

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

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

    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)

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

def cmb(n, k):
    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

r1, c1, r2, c2 = lr()
MOD = 10 ** 9 + 7
U = 2 * 10 ** 6 + 10
fact, fact_inv = make_fact(U,MOD)

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

# 16

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

  mod = 10**9+7

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

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

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

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

if __name__ == "__main__":
  main()

Submission status: Accepted

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

n = r2 + c2 + 10

fac = [0] * n
inv = [0] * n
finv = [0] * n
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2, n) :
  fac[i] = fac[i-1] * i % mod
  inv[i] = mod - inv[mod%i] * (mod // i) % mod
  finv[i] = finv[i-1] * inv[i] % mod

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

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

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

print(ret)

Submission status: Accepted

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

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

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

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

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

print(ret)

Submission status: Accepted

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


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


def make_table(n, mod=10 ** 9 + 7):
    N = n
    # 元テーブル
    g1 = [0] * (N + 1)
    g1[0] = 1
    g1[1] = 1

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

    return g1


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


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

Submission status: Accepted

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

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

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

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

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

print(ret)

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

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

def Comb(i,j):
    if i==0 or j==0:
        return 0
    num=fact(i+j)
    num*=inverse(fact(i))
    num%=MOD
    num*=inverse(fact(j))
    num%=MOD
    return num
    
r1,c1,r2,c2 = map(int,input().split())
#おなじみパスカル行列を区間で和を取ろうという問題
#F[n][r]=nCr(n+r,r)と、
#G[a][b]をΣ[i,0~a-1](Σ[j,0~b-1](F[i][j]))と表す
#ここで、G[a][b]をO(N)くらいで計算できれば勝ち
#ところで、G[a][b]=F[a+1][b+1]-1になる
#なので、それぞれのGをO(N+logMOD)で計算できるのでAC
Ans=0
Ans+=Comb(r2+1,c2+1)
Ans-=Comb(r1,c2+1)
Ans-=Comb(r2+1,c1)
Ans+=Comb(r1,c1)
Ans+=MOD;Ans+=MOD;Ans%=MOD

print(Ans)

Submission status: Accepted

Solution code:
#f_listとf_r_listの要素数は状況に応じて変えよう

MOD = 10**9 + 7
list_size = 2000003

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

def f(x, y):
	if x * y == 0:
		return 0
	elif x == 1:
		return y * (y+3) // 2
	else:
		return comb(x+y+2, x+1) - x - y - 2


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

Submission status: Accepted

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

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

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

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

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

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

print(cum)

Submission status: Accepted

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

solve()

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


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


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

Submission status: Accepted

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

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

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

def fact(n):
    return factorial[n]

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

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

Submission status: Accepted

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


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


# 互いに素なx, yについて、a * x + b * y = 1の解の一つを求める。
def extGCD(x, y):
    r = [1, 0, x]
    w = [0, 1, y]
    # print(r, w)
    while w[2] != 1:
        # print(r, w)
        q = r[2] // w[2]
        w_tmp = [r[0] - q * w[0], r[1] - q * w[1], r[2] % w[2]]
        r, w = w, w_tmp

    return w[:2]


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


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


r1, c1, r2, c2 = inpl()

MOD = 10**9 + 7

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

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

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

Submission status: Accepted

Solution code:
nn = 2002002
P = 10**9+7

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

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

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
mod = 10**9+7

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

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

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

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

Submission status: Accepted

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


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




r1, c1, r2, c2 = LI()

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


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


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


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

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

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

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        # 階乗テーブル
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        # 階乗の逆元テーブル
        inverse = [1] * MAX
        # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            # 最後から戻っていくこのループならMAX回powするより処理が速い
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """

        if n < r: return 0
        # 10C7 = 10C3
        r = min(r, n-r)
        # 分子の計算
        numerator = self.fact[n]
        # 分母の計算
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

r1, c1, r2, c2 = MAP()

mt = ModTools(r2+c2+2, MOD)
# nCr(0, 0)からnCr(n, r)までの全ての組み合わせの総和
def calc(r, c):
    return mt.nCr(r+c+2, r+1) - 1

# 2次元で区間和取る時の要領で4点足し引き
ans = calc(r2, c2) - calc(r2, c1-1) - calc(r1-1, c2) + calc(r1-1, c1-1)
print(ans%MOD)

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

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

fac, ifac = make_table()

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

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

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

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

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

Submission status: Accepted

Solution code:
def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


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