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:
r1, c1, r2, c2 = map(int, input().split())
N = 10 ** 7
MOD = 10 ** 9 + 7
def createFacArr(n, mod):
    '''
    二項係数計算用の配列の作成

    Parameters
    n : int
        配列のサイズ
    mod : int
        あまり

    Returns
    fac : list
        階乗のリスト
    finv : list
        modの逆元のリスト
    ivn : list
    '''
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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
    return fac, finv
fac, finv = createFacArr(N+100, MOD)

def comb(n ,k, mod):
    '''
    二項係数の計算

    Parameters
    n : int
        元集合
    k : int
        元集合から選択する数
    mod : int
        あまり
    Returns
    c : int
        nCkの組み合わせの数
    '''
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 0

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

print(ans)

Submission status: Accepted

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

    MOD = 10**9+7
    n = r2+c2+2
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
      fac[i] = i*fac[i-1]%MOD
      rev[i] = pow(fac[i], MOD-2, MOD)
    
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD
    f = lambda r,c:comb(r+c+2, c+1)

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

    MOD = 10**9+7
    n = r2+c2+2
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
      fac[i] = i*fac[i-1]%MOD
      rev[i] = pow(fac[i], MOD-2, MOD)
    
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

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

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

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def calc_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD

def make_facts(n):
    '''
        make factorials
        0!(=1), 1!, 2!, 3! .... n!
    '''
    fact = [1]
    for i in range(n):
        fact.append((fact[i] * (i + 1)) % MOD)
    return fact

def make_combs(n, k):
    '''
        make [C(0, k), C(1, k), C(2, k) ..... C(n, k)]
    '''
    fact = [1] * (n + 1)
    for i in range(2, n + 1):
        fact[i] = (fact[i - 1] * i) % MOD

    ret = [0] * (n + 1)
    for i in range(k, n + 1):
        a = fact[i]
        b = (fact[k] * fact[i - k]) % MOD
        ret[i] = calc_fraction_mod(a, b)
    return ret


def solve(r: "List[int]", c: "List[int]"):
    #t = make_combs_(10, 2)
    ret = 0
    x = make_combs(r[1] + c[1] + 2, r[1])
    y = make_combs(r[0] + c[1] + 2, r[0] - 1)
    for i in range(c[0], c[1] + 1):
        ret += x[r[1] + i + 1]
        ret -= y[r[0] + i]
        ret %= MOD
    print(ret)
    return ret
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    r = [int()] * (2)  # type: "List[int]"
    c = [int()] * (2)  # type: "List[int]"
    for i in range(2):
        r[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(r, c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def createFacArr(n, mod):
    '''
    二項係数計算用の配列の作成

    Parameters
    n : int
        配列のサイズ
    mod : int
        あまり

    Returns
    fac : list
        階乗のリスト
    finv : list
        modの逆元のリスト
    ivn : list
    '''
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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
    return fac, finv

def comb(n ,k, mod, fac, finv):
    '''
    二項係数の計算

    Parameters
    n : int
        元集合
    k : int
        元集合から選択する数
    mod : int
        あまり
    fac : list
        階乗のリスト
    finv : list
        逆元のリスト
    
    Returns
    c : int
        nCkの組み合わせの数
    '''
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod
MOD = 10 ** 9 + 7
fac, finv =  createFacArr(10**7, MOD)

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

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

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

def main():
    r1,c1,r2,c2 = LI()

    r = 0
    t1 = 1
    u1 = c2 + 1
    t2 = 1
    u2 = c1
    for i in range(1, r2+2):
        t1 *= u1
        t1 %= mod
        u1 += 1
        t1 *= inv(i)
        t1 %= mod
        t2 *= u2
        t2 %= mod
        u2 += 1
        t2 *= inv(i)
        t2 %= mod
        if i > r1:
            r += t1 - t2
            r %= mod

    return r

print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

class Combination:
    def __init__(self, n, mod):

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

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


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(R1, C1, R2, C2):
    C = Combination(2*10**6+1, 10**9+7)
    M = Mod(10**9+7)
    ans = 0
    for r in range(R1, R2+1):
        a = C(C2+r+1, r+1)
        b = C(C1-1+r+1, r+1)
        ans = M.add(ans, M.sub(a, b))
    return ans



def main():
    R1, C1, R2, C2 = read_int_n()
    print(slv(R1, C1, R2, C2))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 1000000007

class combination():
    def __init__(self, n):
        self.fact = [1] * (n+1)
        self.ifact = [1] * (n+1)
        for i in range(1, n+1):
            self.fact[i] = self.fact[i-1]*i % mod
        self.ifact[n] = pow(self.fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            self.ifact[i-1] = self.ifact[i]*i % mod
    def comb(self, n, k):
        if k < 0 or k > n: return 0
        comb = self.fact[n]*self.ifact[k]*self.ifact[n-k] %mod
        return comb

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

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

    comb = combination(2000010)

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

main()

Submission status: Accepted

Solution code:
mod = 10**9+7
def comb_mod(n,r,mod,invs):
    ans = 1
    for i in range(r):
        ans *= n-i
        ans %= mod
    ans *= invs[r]
    ans %= mod
    return ans

A, B, C, D = map(int, input().split())

invs = [1]*(C+2)
for i in range(1,C+2):
    invs[i] = invs[i-1]*pow(i,mod-2,mod)
    invs[i] %= mod
ans = comb_mod(C+D+2,C+1,mod,invs)-comb_mod(B+C+1,B,mod,invs)-comb_mod(A+D+1,A,mod,invs)+comb_mod(A+B,A,mod,invs)
print(ans%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

def main():
  r1,c1,r2,c2=map(int,input().split())
  mod=pow(10,9)+7

  # コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
  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]
  for i in range( 2, r2+c2+3):
      g1.append( ( g1[-1] * i ) % mod )
      inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
      g2.append( (g2[-1] * inverse[-1]) % mod )
  ans=0
  for r in range(r1,r2+1):
    ans+=cmb(r+c2+1,r+1,mod)-cmb(r+c1,r+1,mod)
    ans%=mod
  print(ans)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
    mod = 10 ** 9 + 7
    N = 2 * 10 ** 6 + 3

    fac = [0] * N
    finv = [0] * N
    inv = [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
        # mod pにおける1, 2, ..., nの逆元
        # inv[i] = mod - inv[mod % i] * (mod // i) % mod
        # finv[i] = finv[i - 1] * inv[i] % mod
    # modにおける1!, 2!, ...の逆元
    finv[N // 2] = pow(fac[N // 2], mod - 2, mod)
    for i in reversed(range(N // 2)):
        finv[i] = (finv[i + 1] * (i + 1)) % mod

    def com(r, c):
        ans = fac[r + c] * finv[r] * finv[c]
        return ans % mod

    def g(r, c):
        return (com(r + 1, c + 1) - 1) % mod

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

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

if __name__ == "__main__":
    main()

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 = 3*10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    r1, c1, r2, c2 = map(int, read().split())
    mod = 10 ** 9 + 7

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

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



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


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

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    r1, c1, r2, c2 = map(int, read().split())
    mod = 10 ** 9 + 7

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

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



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


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

if __name__ == "__main__":
    run()

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

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


#############
# Constants #
#############

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

#############
# Functions #
#############

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

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

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

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

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

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

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

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

#############
# Main Code #
#############
x1,y1,x2,y2 = inputIL()


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


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

Submission status: Accepted

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

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

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

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

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

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

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

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

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

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

class ModInt:

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

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

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

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


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

mod = 1000000007

modint = ModInt(mod)


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


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

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

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

print(ans)

Submission status: Accepted

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

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

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

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

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

print(ans%MOD)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

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


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


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


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
# comb_mod(n, c, r, mod, fac, den) ≡ nCr
def prepare(n, mod):
    # fac[i] ≡ i!
    fac = [1]
    for i in range(1, n+1):
        fac.append((fac[-1] * i) % mod)

    # rec ≡ 1 / n!
    rec = pow(fac[-1], mod-2, mod)

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

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

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

# n:max(n), mod:prime number を入力
mod = 10**9 + 7
fac, den = prepare(r2+c2+2, mod)

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

print(ans % mod)

Submission status: Accepted

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


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

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

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

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

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

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

Submission status: Accepted

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

    return ret


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

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

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

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

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

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