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: Runtime Error

Solution code:
from typing import List


class ModInt:
    mem_factorial: List[int]

    def __init__(self, mod=1000000007, mem_size=2000000, precalc=True):
        self.mod = mod
        self.mem_factorial = [0] * mem_size
        self.mem_size = mem_size
        if precalc:
            self.mem_factorial[0] = 1
            for i in range(1, mem_size):
                self.mem_factorial[i] = self.mem_factorial[i-1]*i % mod

    def inverse(self, x, mod: int = None):
        if mod is None:
            mod = self.mod
        return int(pow(x, mod - 2, mod))

    def factorial(self, x, mod: int = None):
        if x == 0:
            return 1
        if mod is None:
            mod = self.mod
        if x < self.mem_size and self.mem_factorial[x] > 0:
            pass
        else:
            self.mem_factorial[x] = (self.factorial(x - 1, mod) * x) % mod
        return self.mem_factorial[x]

    def comb(self, m, n, mod: int = None):
        if mod is None:
            mod = self.mod
        a = self.factorial(m, mod)
        b = self.factorial(n, mod)
        c = self.factorial(m - n, mod)
        bc = b * c % mod
        ret: int = a * self.inverse(bc, mod) % mod
        return ret

mod = 1000000007

modint = ModInt(mod)


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


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: Runtime Error

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

MOD=10**9+7
MAXN=400000+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: Runtime Error

Solution code:
MOD = 10**9+7
r1,c1,r2,c2 = map(int,input().split())
 
size = 1000000*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: Runtime Error

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

def cmb1(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 = 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 )

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

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
  return list(map(int,input().split()))
def m(): #複数文字
  return map(int,input().split())
def onem(): #Nとかの取得
  return int(input())
def s(x): #圧縮
  a = []
  if len(x) == 0:
    return []
  aa = x[0]
  su = 1
  for i in range(len(x)-1):
    if aa != x[i+1]:
      a.append([aa,su])
      aa = x[i+1]
      su = 1
    else:
      su += 1
  a.append([aa,su])
  return a
def jo(x): #listをスペースごとに分ける
  return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
  return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
  ll = 0
  rr = r
  while True:
    mid = (ll+rr)//2

  if rr == mid:
    return ll
  if (ここに評価入れる):
    rr = mid
  else:
    ll = mid+1
"""

mod = 10**9+7 #出力の制限
N = 10**6 * 2
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
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % 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 )
# a = cmb(n,r)

r1,c1,r2,c2= m()

p1 = 0

p2 = 0

p3 = 0

p4 = 0

for i in range(1,r2+2):
  p1 += cmb(c2+i,i)
  p1 %= mod
for i in range(1,r1+1):
  p2 += cmb(c2+i,i)
  p2 %= mod
for i in range(1,r2+2):
  p3 += cmb(c1+i-1,i)
  p3 %= mod
for i in range(1,r1+1):
  p4 += cmb(c1+i-1,i)
  p4 %= mod

print((p1-p2-p3+p4)%mod)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
import numpy as np

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

MOD = 10 ** 9 + 7

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

U = 2 * 10 ** 6 + 2  # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,v,p = map(int,input().split())
    MOD = 10**9+7
    N = v+p+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(v+1,p+1)-comb(v+1,b)-comb(p+1,a)+comb(a,b))%MOD)
    
if _name_ == "_main_":
    main()

Submission status: Runtime Error

Solution code:

##mod,nについての制約は自分でいかに記入する
mod=10**9+7
def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist
 #あるかずxのn乗をmodで割ったあまりを返す関数pow_cal(x,n,mod)
def pow_cal(x,n,mod):
    if n==0:
        return 1
    elif n==1:
        return x%mod
    elif n>=2:
        if n%2==0:
            return (pow_cal(x,n//2,mod)**2)%mod
        else:
            return (x*pow_cal(x,n//2,mod)**2)%mod

def find_inv_power(n,mod):
    #0!からn!までの逆元を素数modで割ったあまりリストを作る関数
    c=1
    uselist=[0 for i in range(n+1)]
    for i in range(1,n+1):
        c*=i
        c%=mod
    first=pow_cal(c,mod-2,mod)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(mod)
    return uselist
    
A=find_power(2*10**6,mod)
B=find_inv_power(2*10**6,mod)

def combi(n,r,mod):
    if n<r:
        return 0
    elif n>=r:
        return (A[n]*B[r]*B[n-r])%(mod)
    
r1,c1,r2,c2=map(int,input().split())

mod=10**9+7     

K=combi(r2+c2+2,c2+1,mod)-combi(r2+c1+1,c1,mod)-combi(r1+c2+1,r1,mod)+combi(r1+c1,c1,mod)

print(K%mod)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    x,y,z,w = map(int,input().split())
    MOD = 10**9+7
    K= z+w+5
    fac = [0 for i in range(K+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,K+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(e,f):
        return (fac[e+f]*pow(fac[e],MOD-2,MOD)*pow(fac[f],MOD-2,MOD))%MOD
 
    print((comb(z+1,w+1)-comb(z+1,y)-comb(w+1,x)+comb(x,y))%MOD)
    
if _name_ == "_main_":
    main()
#print the result

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    K= c+d+5
    fac = [0 for i in range(K+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,K+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(e,f):
        return (fac[e+f]*pow(fac[e],MOD-2,MOD)*pow(fac[f],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if _name_ == "_main_":
    main()
#print the result

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N= c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(e,f):
        return (fac[e+f]*pow(fac[e],MOD-2,MOD)*pow(fac[f],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if _name_ == "_main_":
    main()
#print the result

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    K= c+d+5
    fac = [0 for _ in range(K+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,K+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(e,f):
        return (fac[e+f]*pow(fac[e],MOD-2,MOD)*pow(fac[f],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if _name_ == "_main_":
    main()
#print the result

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if _name_ == "_main_":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    K = c+d+5
    fac = [0 for _ in range(K+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,K+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if _name_ == "_main_":
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
iport numpy
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
       
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
   
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    mod = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for j in range(2,N+1):
        fac[j] = (fac[j-1]*j)%mod
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],mod-2,mod)*pow(fac[y],mod-2,mod))%mod
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%mod)
    
if _name_ == "_main_":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    P= c+d+5
    fac = [0 for _ in range(P+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,P+1):
        fac[i] = (fact[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if _name_ == "_main_":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    P= c+d+5
    fac = [0 for _ in range(P+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,P+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if _name_ == "_main_":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for j in range(2,N+1):
        fac[j] = (fac[j-1]*j)%MOD
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if _name_ == "_main_":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    P= c+d+5
    fac = [0 for _ in range(P+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,P+1):
        fac[i] = (fact[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if _name_ == "_main_":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    w,x,y,z = map(int,input().split())
    MOD = 10**9+7
    N = y+z+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(r,s):
        return (fac[r+s]*pow(fac[r],MOD-2,MOD)*pow(fac[s],MOD-2,MOD))%MOD
 
    print((comb(y+1,z+1)-comb(y+1,x)-comb(z+1,w)+comb(w,x))%MOD)
    
if _name_ == "_main_":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    t,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x1,y2):
        return (fac[x1+y2]*pow(fac[x1],MOD-2,MOD)*pow(fac[y2],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,t)+comb(t,b))%MOD)
    
if _name_ == "_main_":
    main()
#print the result

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    t,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,t)+comb(t,b))%MOD)
    
if _name_ == "_main_":
    main()
#print the result
#calling the main function

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for i in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,f):
        return (fac[x+f]*pow(fac[x],MOD-2,MOD)*pow(fac[f],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if _name_ == "_main_":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,t)+comb(t,b))%MOD)
    
if _name_ == "_main_":
    main()
#print the result
#calling the main function

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    t,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,t)+comb(t,b))%MOD)
    
if _name_ == "_main_":
    main()
#print the result

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MODE = 10**9+7
    NU = c+d+5
    fac = [0 for _ in range(NU+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,NU+1):
        fac[i] = (fac[i-1]*i)%MODE
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MODE-2,MODE)*pow(fac[y],MODE-2,MODE))%MODE
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MODE)
    
if _name_ == "_main_":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    factt = [0 for _ in range(N+1)]
    factt[0],factt[1] = 1,1
 
    for i in range(2,N+1):
        factt[i] = (factt[i-1]*i)%MOD
        
    def comb(x,y):
        return (factt[x+y]*pow(factt[x],MOD-2,MOD)*pow(factt[y],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if _name_ == "_main_":
    main()

Submission status: Runtime Error

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

import sys
# 再起回数上限変更
# sys.setrecursionlimit(1000000)

r1, c1, r2, c2 = map(int, input().split())
DIVISOR = 10**9 + 7

'''
1 1 2 2
'''


def comb(n, r):
    # nCi mod m (i=0からnまでを全て求める）
    res1 = [1] * (r+1)
    res2 = [1] * (r+1)

    for i in range(1, r + 1):
        # 分子
        res1[i] = (res1[i-1] * (n-i+1)) % DIVISOR
        # 分母
        # res2[i] = (res2[i-1] * i) % DIVISOR
        # res2[i] = power_mod(res2[i], DIVISOR - 2, DIVISOR)
        res2[i] = power_mod((res2[i-1] * i), DIVISOR - 2, DIVISOR)

    res = [(r1 * r2) % DIVISOR for r1, r2 in zip(res1, res2)]

    return res


def power_mod(n, k, m):
    if k == 0:
        return 1
    elif k % 2 == 1:
        return power_mod(n, k-1, m) * (n % m) % m
    elif k % 2 == 0:
        temp = power_mod(n, k/2, m)
        return (temp % m) * (temp % m) % m


# r1+c1 C r1
ans0 = comb(r1+c1, r1)[-1]
# print(ans0)

rs = r2-r1
cs = c2-c1

dp = [[0] * (cs+1) for _ in range(rs+1)]
dp[0][0] = ans0


for c in range(1, cs+1):
    dp[0][c] = (dp[0][c-1] * (r1 + c1 + c) / (c1 + c)) % DIVISOR
    # dp[0][c] = dp[0][c-1] * ((r1 + c1 + c) % DIVISOR) / (c1 + c)
    # dp[0][c] = dp[0][c-1] * ((r1 + c1 + c) % DIVISOR) * power_mod(c1 + c, DIVISOR - 2, DIVISOR)

for r in range(1, rs+1):
    dp[r][0] = (dp[r - 1][0] * (r1 + c1 + r) / (r1 + r)) % DIVISOR
    # dp[r][0] = dp[r - 1][0] * ((r1 + c1 + r) % DIVISOR) / (r1 + r)
    # dp[r][0] = dp[r - 1][0] * ((r1 + c1 + r) % DIVISOR) * power_mod(r1 + r, DIVISOR - 2, DIVISOR)
    for c in range(1, cs+1):
        dp[r][c] = (dp[r][c-1] * (r1 + c1 + r + c) / (c1 + c)) % DIVISOR
        # dp[r][c] = dp[r][c-1] * ((r1 + c1 + r + c) % DIVISOR) * power_mod(c1 + c, DIVISOR - 2, DIVISOR)
        # print(r, c)

# print(dp)
print(int(sum([sum(i) % DIVISOR for i in dp]) % DIVISOR))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(500*500)
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)

r1,c1,r2,c2=map(int,input().split())
n1=r2+c2+2
n2=r2+c1+1
n3=r1+c2+1
n4=r1+c1
l=[r2+1,r2+1,r1,r1]
p=10**9+7
buf=1
cnt=0
l=[0]*(10**6+10)
inv=[0]*(10**6+10)
l[1]=1
for i in range(2,n1+3,1):#n1+1
    l[i]=(l[i-1]*i)%p
print((((l[n1]*modinv(l[r2+1],p)*modinv(l[n1-r2-1],p))%p)-(l[n2]*modinv(l[r2+1],p)*modinv(l[n2-r2-1],p))-(l[n3]*modinv(l[r1],p)*modinv(l[n3-r1],p))+(l[n4]*modinv(l[r1],p)*modinv(l[n4-r1],p)))%p)

Submission status: Runtime Error

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)

r1,c1,r2,c2=map(int,input().split())
n1=r2+c2+2
n2=r2+c1+1
n3=r1+c2+1
n4=r1+c1
l=[r2+1,r2+1,r1,r1]
p=10**9+7
buf=1
cnt=0
l=[0]*(10**6+10)
inv=[0]*(10**6+10)
l[1]=1
for i in range(2,n1+3,1):#n1+1
    l[i]=(l[i-1]*i)%p
print((((l[n1]*modinv(l[r2+1],p)*modinv(l[n1-r2-1],p))%p)-(l[n2]*modinv(l[r2+1],p)*modinv(l[n2-r2-1],p))-(l[n3]*modinv(l[r1],p)*modinv(l[n3-r1],p))+(l[n4]*modinv(l[r1],p)*modinv(l[n4-r1],p)))%p)

Submission status: Runtime Error

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)

r1,c1,r2,c2=map(int,input().split())
n1=r2+c2+2
n2=r2+c1+1
n3=r1+c2+1
n4=r1+c1
l=[r2+1,r2+1,r1,r1]
p=10**9+7
buf=1
cnt=0
l=[0]*(10**6+10)
inv=[0]*(10**6+10)
for i in range(2,n1+3,1):#n1+1
    l[i]=(l[i-1]*i)%p
print((((l[n1]*modinv(l[r2+1],p)*modinv(l[n1-r2-1],p))%p)-(l[n2]*modinv(l[r2+1],p)*modinv(l[n2-r2-1],p))-(l[n3]*modinv(l[r1],p)*modinv(l[n3-r1],p))+(l[n4]*modinv(l[r1],p)*modinv(l[n4-r1],p)))%p)

Submission status: Runtime Error

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)

r1,c1,r2,c2=map(int,input().split())
n1=r2+c2+2
n2=r2+c1+1
n3=r1+c2+1
n4=r1+c1
l=[r2+1,r2+1,r1,r1]
p=10**9+7
buf=1
cnt=0
l=[0]*(10**6+10)
l2=[0]*20
inv=[0]*(10**6+10)
l[1]=1
for i in range(2,n1+3,1):#n1+1
    l[i]=(l[i-1]*i)%p
l2[1]=1
for i in range(2,10,1):
    l2[i]=(l2[i-1]*i)%p
#print(l2)
print((((l[n1]*modinv(l[r2+1],p)*modinv(l[n1-r2-1],p))%p)-(l[n2]*modinv(l[r2+1],p)*modinv(l[n2-r2-1],p))-(l[n3]*modinv(l[r1],p)*modinv(l[n3-r1],p))+(l[n4]*modinv(l[r1],p)*modinv(l[n4-r1],p)))%p)

Submission status: Runtime Error

Solution code:
def resolve():
    r1, c1, r2, c2 = map(int, input().split())
    dp = [[0] * (c2+2) for _ in range(r2+2)]
    dp[0][0] = 1
    for r in range(r2+1):
        dp[r][0] = 1
    for c in range(c2+1):
        dp[0][c] = 1
    m = 10 ** 9 + 7
    ans = 0
    for r in range(r2+1):
        for c in range(c2+1):
            if r-1 >= 0 and c-1 >= 0:
                dp[r][c] = (dp[r-1][c] + dp[r][c-1])
            if r1 <= r <= r2 and c1 <= c <= c2:
                ans = (ans + dp[r][c]) % m
    print(ans)

resolve()

Submission status: Runtime Error

Solution code:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author silviase
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        FManyManyPaths solver = new FManyManyPaths();
        solver.solve(1, in, out);
        out.close();
    }

    static class FManyManyPaths {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            ModInt ans = new ModInt(0);
            ModComb mc = new ModComb(2000005);
            int r1 = in.nextInt();
            int c1 = in.nextInt();
            int r2 = in.nextInt();
            int c2 = in.nextInt();
            for (int i = r1; i <= r2; i++) {
                ans = ans.add(mc.combFac(c2 + i + 1, c2)).sub(mc.combFac(c1 + i, i + 1));
                // out.println(mc.combFac(c2+i+1,c2));
                // out.println(mc.combFac(c1+i,i+1));
            }

            out.println(ans.getVal());

        }

    }

    static class ModInt {
        long val;
        int MOD = (int) 1e9 + 7;

        public ModInt(long i) {
            this.val = (i + MOD) % MOD;
        }

        public ModInt mul(long l) {
            return new ModInt(this.val * l);
        }

        public ModInt add(ModInt m) {
            return new ModInt(this.val + m.getVal());
        }

        public ModInt sub(ModInt m) {
            return new ModInt(this.val - m.getVal());
        }

        public ModInt inv() {
            return this.pow(MOD - 2);
        }

        public ModInt pow(long l) {
            ModInt res = new ModInt(1);
            ModInt v = new ModInt(this.val);
            while (l > 0) {
                if (l % 2 != 0) {
                    res = res.mul(v.val);
                }
                v = v.mul(v.val);
                l /= 2;
            }
            return res;
        }

        public long getVal() {
            return val;
        }

        public String toString() {
            return Long.toString(val);
        }

    }

    static class ModComb {
        private int size;
        private ModInt[] fac;
        private ModInt[] inv;

        public ModComb(int n) {
            size = n;
            fac = new ModInt[n + 1];
            inv = new ModInt[n + 1];
            makeFac();
        }

        private void makeFac() {
            for (int i = 0; i <= size; i++) {
                if (i == 0) {
                    fac[i] = new ModInt(1);
                } else {
                    fac[i] = fac[i - 1].mul(i);
                }
                inv[i] = fac[i].inv();
            }
        }

        public ModInt combFac(int n, int k) {
            if (n < k) {
                return new ModInt(0);
            }
            return fac[n].mul(inv[k].getVal()).mul(inv[n - k].getVal());
        }

    }
}

Submission status: Runtime Error

Solution code:
nmax = 10**6+1
mod = 10**9+7

fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    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 ncr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n]* (finv[r] * finv[n-r] %mod) %mod

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

ans = 0
for c in range(c1,c2+1):
    for r in range(r1,r2+1):
        ans+=ncr(r+c,c)
        ans %=mod
print(ans)

Submission status: Runtime Error

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

def init_mod_c(lim=10**6*2, mod=10**9+7):
    fact = [1, 1] + [0] * (lim-1)
    fact_inv = [1, 1] + [0] * (lim-1)
    inv = [0, 1] + [0] * (lim-1)
    
    for i in range(2, lim+1):
        fact[i] = fact[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod

    def mod_c(n, m):
        if n < m or n < 0 or m < 0: return 0
        return fact[n] * (fact_inv[m] * fact_inv[n-m] % mod) % mod

    return mod_c

comb = init_mod_c()
pc = lambda r, c: comb(r+c, min(r, c))

ans = 0
for i in range(r1, r2+1):
    ans += pc(i+1, c2)
    if c1 > 0: ans -= pc(i+1, c1-1)
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
r1,c1,r2,c2=map(int,input().split())
r2+=1
c2+=1
N=2*(10**6)
mod=10**9+7
fac=[1]*(N+2)
inv=[1]*(N+2)
t=1
for i in range(1,N+2):
    t*=i
    t%=mod
    fac[i]=t
t=pow(fac[N+1],mod-2,mod)
for i in range(N+1,0,-1):
    inv[i]=t
    t*=i
    t%=mod
def comb(n,r):
    return fac[n]*inv[n-r]*inv[r]%mod
print(comb(r2+c2,c2)-comb(r2+c1,c1)-comb(r1+c2,c2)+comb(r1+c1,c1))

Submission status: Runtime Error

Solution code:
u, l, d, r = map(int, input().split())
mod = 10 ** 9 + 7

def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y

def moddiv(a, b):
    _, inv, _ = extGCD(b, mod)
    return (a * inv) % mod

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

def comb(a, b):
    return moddiv(moddiv(f[a+b], f[a]), f[b])

ans = 0
d += 1
r += 1
ans += comb(d, r)
ans += comb(u, l)
ans -= comb(d, l)
ans -= comb(u, r)
print(ans % mod)

Submission status: Runtime Error

Solution code:
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

r1, c1, r2, c2 = map(int, input().split())
ans = combinations_count(r2, c2)
ans -= combinations_count(r1, c2)
ans -= combinations_count(r2, c1)
ans += combinations_count(r1, r2)
print(ans)

Submission status: Runtime Error

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

path = [[0]*(r2+1) for i in range(c2+1)]
ans = 0
mod = 10**9+7
for i in range(r2+1):
    for j in range(c2+1):
        if i == 0 or j == 0:
            path[j][i] = 1
        else:
            path[j][i] = (path[j-1][i] + path[j][i-1])%mod
        if c1 <= j <= c2 and r1<= i <= r2:
            ans = (ans + path[j][i])%mod
print(ans)

Submission status: Runtime Error

Solution code:

p = 10**9+7
kai_ = [1]
for i in range(1, 10 ** 6 * 2):
    kai_.append(kai_[-1] * i % p)


def kai(x):
    return kai_[x]


def comb(a, b):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai(a)
    c *= pow(kai(b), p - 2, p)
    c *= pow(kai(a - b), p - 2, p)
    return c % p


r1, c1, r2, c2 = [int(i) for i in input().split()]


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


print((s(r2, c2) - s(r2, c1 - 1) - s(r1 - 1, c2) + s(r1 - 1, c1 - 1)) % p)