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
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
r1,c1,r2,c2=map(int,input().split())
l=[1]*2000022
for i in range(1,2000022):
  l[i]=l[i-1]*ModInt(i)
def comb(a,b):
  c,d=int(a),int(b)
  if a==b or b==0 or a==0:return 1
  return l[c]/l[d]/l[c-d]
ans=((ModInt(r2)+2)*comb(c2+r2+2,r2+2)-ModInt(c2)-1)/(ModInt(c2)+1)-((ModInt(r1)+1)*comb(c2+r1+1,r1+1)-ModInt(c2)-1)/(ModInt(c2)+1)-((ModInt(r2)+2)*comb(c1+r2+1,r2+2)-ModInt(c1)-2)/ModInt(c1)+((ModInt(r1)+1)*comb(c1+r1,r1+1)-ModInt(c1)-2)/ModInt(c1)
print(ans)

Submission status: Accepted

Solution code:
r1,c1,r2,c2 = map(int,input().split())
mod = 10**9+7
fact = [1]*(2*10**6+11)

for n in range(2*10**6+10):
    fact[n+1] = ((n+1)*fact[n])%mod

factinv = [1]*(2*10**6+10)
for n in range(10**6+10):
    factinv[n] = pow(fact[n],mod-2,mod)

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

def fs(r,c):
    res = 0
    for i in range(1,c+1):
        res += comb(i+1+r,r)-1
    return res

ans = fs(r2,c2)-fs(r1-1,c2)-fs(r2,c1-1)+fs(r1-1,c1-1)
ans %= 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 + 1)
    finv = [0] * (nmax + 1)
    inv = [0] * (nmax + 1)
    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:
bikkuri = [1]
mod = 10**9+7

for i in range(1,2*10**6+1000):
    bikkuri.append((bikkuri[-1]*i)%mod)
r1,c1,r2,c2 = map(int,input().split())

def F(r,c):
    tmp = (bikkuri[r+c+2]*pow(bikkuri[c+1],mod-2,mod)*pow(bikkuri[r+1],mod-2,mod) - 1)%mod
    return tmp

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

Submission status: Accepted

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

r = (r2 + 1)
l = (r1)
ans = 0

for i in range(0, c2):
    gyaku = pow((i + 2), MOD - 2, MOD)
    r *= (r2 + 1 + (i + 1))
    r *= gyaku
    l *= (r1 + (i + 1))
    l *= gyaku
    r %= MOD
    l %= MOD
    if i >= c1 - 1:
        ans += r
        ans -= l
    ans %= MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
n_max=2*(10**6+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

def f(x,y):
  return comb(x+y+2,y+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:
r1,c1,r2,c2=map(int,input().split())
INF=10**9+7
def modcomb(n,k,m):
    fac=[0]*(n+1)
    finv=[0]*(n+1)
    inv=[0]*(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%m
        inv[i]=m-inv[m%i]*(m//i)%m
        finv[i]=finv[i-1]*inv[i]%m
    return fac[n]*(finv[k]*finv[n-k]%m)%m
def modinv(a,m):
    b=m
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while not b==0:
        q=a//b
        (a,b)=(b,a%b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx%m
ans=modcomb(r1+c1,r1,INF)
c=modcomb(r2+c1,c1,INF)
for i in range(c1+1,c2+1):
    c=c*(i+r2)
    x=modinv(i,INF)
    c=(c*x)%INF
    ans=(ans+c)%INF
c=modcomb(r1+c2,r1,INF)
for i in range(r1+1,r2+1):
    c=c*(i+c2)
    x=modinv(i,INF)
    c=(c*x)%INF
    ans=(ans+c)%INF
print(ans)

Submission status: Accepted

Solution code:
class Factorial():
    def __init__(self,n,mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n+1)]
        self.inv = [0 for _ in range(n+1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i+1] = self.factorial[i]*(i+1)%mod
        self.inv[n] = pow(self.factorial[n],mod-2,mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i+1]*(i+1)%mod


    def comb(self,m,k): #組み合わせ 0<=k<=m<=n
        return self.factorial[m]*self.inv[k]*self.inv[m-k]%self.mod

def solve():

    MOD = 1000000007

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

    f = Factorial(2000010,MOD)

    ans = 0

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

    print(ans)

solve()

Submission status: Accepted

Solution code:
def main():
    mod = 10**9+7
    fact = [1]
    fact_inv = [1]
    for i in range(2000005):
        new_fact = fact[-1]*(i+1)%mod
        fact.append(new_fact)


    def mod_comb_k(n,k,mod):
        return fact[n] * pow(fact[k],mod-2,mod) % mod * pow(fact[n-k],mod-2,mod) %mod

    x,p,y,q = map(int,input().split())

    res = mod_comb_k(p+x,x,mod) - mod_comb_k(p+y+1,y+1,mod) - mod_comb_k(q+x+1,x,mod) + mod_comb_k(q+y+2,y+1,mod)
    print(res%mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci
frac, fraci = frac(2341398)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%MOD

def accumulate2d(X2):
    X = X2
    N = len(X)
    M = len(X[0])
    
    for i in range(N):
        for j in range(1, M):
            X[i][j] += X[i][j-1]
    
    for j in range(M):
        for i in range(1, N):
            X[i][j] += X[i-1][j]
    
    return X

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

def calc(R, C):
    if min(R, C) == 0:
        return 1
    res = R
    for i in range(1, C):
        res = (res + comb(R+i, i+1)) % MOD
    return res
r2 += 1
c2 += 1
print((calc(r2, c2)-calc(r2, c1)-calc(r1, c2)+calc(r1, c1))%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:
MOD = 10**9 + 7  # 出力の制限

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


# https://qiita.cmb/derodero24/items/91b6468e66923a87f39f
def cmb(n, r):
  if (r < 0 or r > n):
    return 0
  r = min(r, n - r)
  return g1[n] * g2[r] * g2[n - r] % MOD


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

# Sum[Sum[Binomial[i + j, i], {i, r1, r2}], {j, c1, c2}]
# Binomial[c1 + r1, r1] - Binomial[1 + c2 + r1, r1] -  Binomial[1 + c1 + r2, 1 + r2] + Binomial[2 + c2 + r2, 1 + r2]

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n_ = 2*10**6 + 5
mod = 10**9+7
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod

def nCr(n,r):
    if r > n:
        return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

r1,c1,r2,c2 = nm()

def H(k,l):
    return (nCr(k+l+2, k+1)-1)%mod

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

Submission status: Accepted

Solution code:
class PERM_COMB_MOD():
    # http://drken1215.hatenablog.com/entry/2018/06/08/210000
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

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

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

    def h(self, n, k):
        if n == k == 0:
            return 1
        return self.comb(n+k-1, k)

PCM = PERM_COMB_MOD(3*10**6+100)
mod = 10**9+7

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

def sq(R,L):
    R+=1
    L+=1
    ret = 0
    for i in range(R):
        ret += PCM.comb(L+i, i+1)
    ret %= mod
    return ret
ans = sq(r2, c2) - sq(r2, c1-1) - sq(r1-1, c2) + sq(r1-1,c1-1)
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n_ = 2*10**6 + 3
mod = 10**9+7
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod

def nCr(n,r):
    if r > n:
        return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod


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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def comb(a,b):
        return f[a]*inv[b]*inv[a-b]%mod
    r1,c1,r2,c2 = LI()
    N = 3*10**6
    f = [1]
    for i in range(N):
        f.append(f[-1]*(i+1)%mod)
    inv = [None]*(N+1)
    inv[-1] = pow(f[-1],mod-2,mod)
    for i in range(N)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    ans = 0
    for i in range(r1,r2+1):
        s = 0
        ans += comb(i+1+c2,i+1)-comb(i+c1,i+1)
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
mod = 10**9+7
rng = 2000100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(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:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10 ** 9 + 7

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


def make_fact(U, MOD = 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]
    fact.flags.writeable = False
    fact_inv.flags.writeable = False
    return fact,fact_inv

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

def F(i,j):
    return fact[i+j+2] * fact_inv[i+1] % MOD * fact_inv[j+1] % MOD

a,b,c,d = map(int,read().split())

answer = F(c,d) - F(a-1,d) - F(c,b-1) + F(a-1,b-1)
answer %= MOD
print(answer)

Submission status: Accepted

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

mod = 10**9 + 7
l = 2*10**6 + 3

M = [1]  # i!のmod
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  # x**y の mod を返す関数
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  # x の mod での逆元を返す関数
    return pow(x, mod-2, mod)

# print(inv(8,13))

MI = [0] * (l-1) +[inv(M[l-1], mod)]  # i!の逆元
for i in range(l-2, -1, -1):
    MI[i] = MI[i+1] * (i+1) % mod

def C(x, y):  # コンビネーション
    if y < 0 or y > x:
        return 0
    ans = M[x]
    ans = (ans * MI[y]) % mod
    return (ans * MI[x-y]) % mod

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

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
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 )
    
r,c,R,C=map(int,input().split())
ans=0
for i in range(C-c):
  ans=ans+cmb(r+c+1+i,r,mod)*cmb(R-r+C-c-i,R-r,mod)
ans=ans+cmb(r+c,r,mod)
for i in range(R-r):
  ans=ans+cmb(c+r+1+i,c,mod)*cmb(C-c+R-r-i,C-c,mod)
print(ans%mod)

Submission status: Accepted

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

FACT=[1]
for i in range(1,2*10**6+3):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**6+2,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

ANS=0

for x in range(c1+1,c2+2):
    ANS=(ANS+Combi(r2+x,r2)-Combi(r1+x-1,r1-1))%mod

print(ANS)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

# sum_{i:r1,r2} sum_{c:c1,c2} f(r+c,c)
# sum_{i:r1,r2} (f(r+c2+1,c2) - f(r+c1, c1-1))

def enumfif(n, mod):
    f = [0] * (n+1)
    invf = [0] * (n+1)
    f[0] = 1
    for i in range(1, n+1):
        f[i] = f[i-1] * i % mod

    a = f[n]
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a//b
        d = a; a = b; b = d % b
        d = p; p = q; q = d-c*q
    invf[n] = p + mod if p < 0 else p
    for i in range(n-1,-1,-1):
        invf[i] = invf[i+1] * (i+1) % mod
    return f, invf

def C(n, r, mod, fif):
    if n < 0 or r < 0 or r > n:
        return 0
    return fif[0][n] * fif[1][r] * fif[1][n-r] % mod

mod = 1000000007
fif = enumfif(2000005, mod)
# sum_{i:r1,r2} (f(r+c2+1,c2) - f(r+c1, c1-1))
# (f(r2+1+c2+1,c2+1) ^ f(r1+c2+1,c2+1) - f(r2+1+c1, c1-1+1) +
# f(r1+c1, c1-1+1)
# )
r1, c1, r2, c2 = na()
ans = \
    C(r2+1+c2+1, c2+1, mod, fif) - \
    C(r1 + c2 + 1, c2 + 1, mod, fif) - \
    C(r2 + c1 + 1, c1 - 1 + 1, mod, fif) + \
    C(r1 + c1, c1 - 1 + 1, mod, fif)
ans %= mod
if ans < 0: ans += mod
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

SIZE=2*10**6+10**5
#SIZE = 10000
MOD=10**9+7 #998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0

import sys
readline = sys.stdin.readline
read = sys.stdin.read


p,a,q,b = [int(i) for i in read().split()]


ans = choose(q+b+2,b+1) - choose(p+b+1,b+1) - choose(q+a+1,a) + choose(p+a,a)


print(ans%MOD)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10 ** 9 + 7

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


def make_fact(U, MOD = 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]
    fact.flags.writeable = False
    fact_inv.flags.writeable = False
    return fact,fact_inv

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

def F(i,j):
    return fact[i+j+2] * fact_inv[i+1] % MOD * fact_inv[j+1] % MOD

a,b,c,d = map(int,read().split())

answer = F(c,d) - F(a-1,d) - F(c,b-1) + F(a-1,b-1)
answer %= MOD
print(answer)

Submission status: Runtime Error

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

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

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

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

#############
# Main Code #
#############

# 逆元事前処理ver
# nが小さい場合に
lim = 10 ** 6 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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

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

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

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

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

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

Submission status: Runtime Error

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

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

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

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

#############
# Main Code #
#############

# 逆元事前処理ver
# nが小さい場合に
lim = 10 ** 6 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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

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

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

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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


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


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

Submission status: Runtime Error

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

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


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


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

Submission status: Runtime Error

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

n = 200004
mod = 1000000007

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

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

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

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

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

Submission status: Runtime Error

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)
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
a,b,c,d=map(int,input().split())
print(cmb(c+d+2,c+1,mod)-cmb(d+1+a,a,mod)-cmb(b+c+1,c+1,mod)+cmb(a+b,a,mod))

Submission status: Runtime Error

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

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

# MOD combination
def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 10**6*2+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

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

Submission status: Runtime Error

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

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

# MOD combination
def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 10**6*2
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

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

Submission status: Runtime Error

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

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


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

	ff=[1]

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


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

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

	print(ans%m)














if __name__ == "__main__":
	main()

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(2000000000)

p = 10 ** 9 + 7
N = a2+b2+2  # N は必要分だけ用意する
R = a2+1
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)
  
for i in range(2, R + 1):
  inv.append((-inv[p % i] * (p // i)) % p)
  factinv.append((factinv[-1] * inv[-1]) % p)

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

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