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 heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True
 
ans=0

r,c,R,C=LI()
n=R+C+5


cm=Comb(n)

t=[[0]*(C+1) for i in range(R+1)]

for i in range(R+1):
    for j in range(C+1):
        t[i][j]=cm.comb(i+j,i)

ans=0
for i in range(r,R+1):
    for j in range(c,C+1):
        ans+=t[i][j]
        ans%=mo

print(ans%mo)

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7


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

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

    return modFacts, invs


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


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


F = [[0] * (max(r2 + 1, c2 + 1)) for _ in range(max(r2 + 1, c2 + 1))]
ans = 0
for x in range(r1, r2 + 1):
    for y in range(c1, c2 + 1):
        tmp = f(x, y)
        ans += tmp
        ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
amari = 1000000007

d = {}
def f(r,c):
  if (r,c) in d:
    return d[(r,c)]
  elif r < 0 or c < 0:
    d[(r,c)] = 0
    return d[(r,c)]
  elif r == 0 or c == 0:
    d[(r,c)] = 1
    return d[(r,c)]
  else:
    d[(r,c)] = (f(r-1,c)+f(r,c-1))%amari
    return d[(r,c)]

r1, c1, r2, c2 = map(int, input().split()) 
ans = 0
for i in range(r1,r2+1):
  for j in range(c1,c2+1):
    ans += f(i,j)%amari
    ans %= amari
print(ans)

Submission status: Runtime Error

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

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

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

def main():
    r1, c1, r2, c2 = map( int, input().split())
    F = getFactorial(2*(10**6))
    J = getInv(2*(10**6))
    I = [0]*(2*(10**6)+1)
    I[0] = 1
    I[1] = 1
    for i in range(2,2*(10**6)+1):
        I[i] = I[i-1]*J[i]%Q
    #print(F[5]*I[5]%Q)
    a = 0
    b = 0
    c = 0
    d = 0
    for i in range(1, c2+1):
        a += F[r2+i+1]*I[i+1]%Q*I[r2]%Q-1
#        print(F[r2+i+1]*I[i+1]%Q*I[r2]%Q-1)
        a %= Q
    if r1 == 1:
        b = 0
    else:
        for i in range(1, c2):
            b += F[r1+i]*I[i]%Q*I[r1]%Q-1
            b %= Q
    if c1 == 1:
        c = 0
    else:
        for i in range(1, c1):
            c += F[r2+i]*I[i]%Q*I[r2]%Q-1
            c %= Q
    if c1 == 1 or r1 == 1:
        d = 0
    else:
        for i in range(1, c1):
            d += F[r1+i]*I[i]%Q*I[r1]%Q-1
            d %= Q
#    print(a, b,c, d)
    print((a-b-c+d)%Q)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
a,b,c,d= map(int,input().split())
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
M = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, M + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

cnt = 0
for i in range(a,c+1,1):
    for j in range(b,d+1,1):
        cnt += cmb(i+j,min(i,j),p)
print(cnt%p)

Submission status: Runtime Error

Solution code:
r_1,c_1,r_2,c_2=map(int,input().split())
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 = 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 )
s=0
for r in range(r_1,r_2+1):
  for c in range(c_1,c_2+1):
    s+=cmb(r+c,c,mod)
print(s%(10**9+7))

Submission status: Runtime Error

Solution code:
import math

mod = 10 ** 9 + 7

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

def f(r, c):
    return math.factorial(r + c) // (math.factorial(r) * math.factorial(c))

import numpy as np

ls = np.zeros((r2 - r1 + 1, c2 - c1 + 1)).astype("int")

res = 0

for r in range(r2 - r1 + 1):
    tmp = f(r + r1, c1) % mod
    ls[r, 0] = tmp
    res += tmp

for c in range(1, c2 - c1 + 1):
    tmp = f(r1, c + c1) % mod
    ls[0, c] = tmp
    res += tmp

for r in range(1, r2 - r1 + 1):
    for c in range(1, c2 - c1 + 1):
        tmp = ls[r - 1, c] + ls[r, c - 1] % mod
        ls[r, c] = tmp
        res += tmp

print(res % mod)

Submission status: Runtime Error

Solution code:
r_1,c_1,r_2,c_2=map(int,input().split())
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 = 10**4
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 )
s=0
for r in range(r_1,r_2+1):
  for c in range(c_1,c_2+1):
    s+=cmb(r+c,c,mod)
print(s%(10**9+7))

Submission status: Runtime Error

Solution code:
import math
r1, c1,r2,c2  = map(int, input().split())
x = 0
for i in range(r1, r2+1):
    for j in range(c1, c2+1):
        x += int(math.factorial(i+j)/(math.factorial(i)*math.factorial(j)))
print(x%(10**9+7))

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

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

Submission status: Runtime Error

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

# f(r,c) = (r+c)_C_c

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

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

def f(r,c):
    temp = [nCr(k,c) for k in range(c+1,r+c+2)]
    return sum(temp) % MOD
    
print((f(r2,c2) - f(r2,c1-1) - f(r1-1,c2) + f(r1-1,c1-1)) % MOD)

Submission status: Runtime Error

Solution code:
import math
import fractions

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

    # divisors.sort()
    return divisors

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

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

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

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
'''
p = 10 ** 9 + 7
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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


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

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


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

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

Submission status: Runtime Error

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]*2000002
for i in range(1,2000002):
  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: Runtime Error

Solution code:
import numpy as np
r1,c1,r2, c2 = map(int, input().split())
p = np.zeros((r2+1,c2+1))
#p[0,:] = range(c2+1)
#p[:,0] = range(r2+1)
p[0,1:] = np.ones((c2))
p[1:,0] = np.ones((r2))

div = 10**9+7

for r in range(1,r2+1):
    for c in range(1,c2+1):
        #print(r,c)
        #p[r][c] = (p[r-1][c] + p[r][c-1] + 2) % div
        p[r][c] = (p[r-1][c] + p[r][c-1]) % div

#for i in range(c2+1):
#    print(p[i,:])

#print((p[r2][c2] - p[r1][c1]) % div)

print((np.sum(p[r1:r2+1,c1:c2+1])) % div)

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 = 10**4
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())

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

Submission status: Runtime Error

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

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

factinv = [1]*(2*10**6+1)
for n in range(10**6+1):
    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: Runtime Error

Solution code:
import numpy as np
r1,c1,r2, c2 = map(int, input().split())
p = np.zeros((r2+1,c2+1),dtype=np.int64)
#p[0,:] = range(c2+1)
#p[:,0] = range(r2+1)
p[0,1:] = np.ones((c2))
p[1:,0] = np.ones((r2))

div = 10**9+7

for r in range(1,r2+1):
    for c in range(1,c2+1):
        #print(r,c)
        #p[r][c] = (p[r-1][c] + p[r][c-1] + 2) % div
        p[r][c] = (p[r-1][c] + p[r][c-1]) % div

#for i in range(c2+1):
#    print(p[i,:])

#print((p[r2][c2] - p[r1][c1]) % div)

print((np.sum(p[r1:r2+1,c1:c2+1])) % div)

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


R = LIST()


def f_r_c(r, c):
	return int(factorial(r+c)/(factorial(r)*factorial(c)))

su = 0
for i in range(R[0], R[2] + 1):
	for j in range(R[1], R[3] + 1):
		su += f_r_c(i, j)

print(su)

Submission status: Runtime Error

Solution code:
a,b = input().split()
arr = list(map(int,input().split()))
ans = 0

for i in range(0, len(arr) - int(b)):
    c = 0
    for j in range(i,int(b)):
        c += (1 + arr[j]) * arr[j] / (2 * arr[j])
    if ans < c:
        ans = c
    print(ans)


print(ans)

Submission status: Runtime Error

Solution code:
import math

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


def routes(r, c):
    return (math.factorial(c + r) / (math.factorial(r) * math.factorial(c)))


ans = 0
for r in range(r1, r2 + 1):
    for c in range(c1, c2+1):
        ans += routes(r, c)
        # print(ans)

print(ans % (10**9+7))

Submission status: Runtime Error

Solution code:
r1,c1,r2,c2=map(int, input().split())
import numpy as np
dp=np.zeros((r2+1,c2+1),dtype=int)+1
MOD=10**9+7
for i in range(r2+1):
  for j in range(c2+1):
    if i==0 and j==0:
      continue
    if i>0 and j>0:
      dp[i,j]=(dp[i-1,j]+dp[i,j-1])%MOD
    elif i>0:
      dp[i,j]=dp[i-1,j]%MOD
    else:
      dp[i,j]=dp[i,j-1]%MOD
ans=0
for i in range(r1,r2+1):
  for j in range(c1,c2+1):
    ans+=dp[i,j]%MOD
print(ans%MOD)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np


def solve():
    N, K, *P = map(int, sys.stdin.read().split())
    P = np.array(P)
    n = np.convolve(P, np.ones(K), mode='valid').argmax()
    cusum = np.array(range(1000+1)).cumsum()
    return np.sum(cusum[P[n:n+K]] / P[n:n+K])


if __name__ == "__main__":
    answer = solve()
    print(answer)

Submission status: Runtime Error

Solution code:
r1, c1, r2, c2 = [int(_) for _ in input().split()]
mod = 10**9 + 7

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


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


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

Submission status: Runtime Error

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(1341398)
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: 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 = 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)

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

ans = 0
for i in range(r1, r2 + 1):
    for j in range(c1, c2 + 1):
        ans += cmb((i + j), min(i, j), mod)

print(ans % (10**9 + 7))

Submission status: Runtime Error

Solution code:
r1,c1,r2,c2=map(int, input().split())
import numpy as np
dp=np.zeros((r2+1,c2+1),dtype=int)+1
MOD=10**9+7
for i in range(r2+1):
  for j in range(c2+1):
    if i>0 and j>0:
      dp[i,j]=(dp[i-1,j]+dp[i,j-1])%MOD
    elif i>0:
      dp[i,j]=dp[i-1,j]%MOD
    else:
      dp[i,j]=dp[i,j-1]%MOD
ans=0
for i in range(r1,r2+1):
  for j in range(c1,c2+1):
    ans+=dp[i,j]%MOD
print(ans%MOD)

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 = 10**4
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 = 0
for i in range(r1, r2 + 1):
    for j in range(c1, c2 + 1):
        ans += cmb((i + j), min(i, j), mod)

print(ans % (10**9 + 7))

Submission status: Runtime Error

Solution code:
import math
import itertools
r1,c1,r2,c2=map(int,input().split())
r=list(i for i in range(r1,r2+1))
c=list(i for i in range(c1,c2+1))
p=itertools.product(r,c)
ans=0
for m,z in p:
    a=math.factorial(m+z)
    b=math.factorial(m)
    c=math.factorial(z)
    ans=ans+a/(b*c)
print(ans%(10**9+7))

Submission status: Runtime Error

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

Solution code:
r_1, c_1, r_2, c_2 = map(int, input().split())

import math
import sys
sys.setrecursionlimit(20000)

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 = 10**4
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 = 0
for i in range(r_1, r_2 + 1):
  for j in range(c_1, c_2 + 1):
    ans += cmb(i+j, i, mod)
    ans %= mod

print(ans % mod)

Submission status: Runtime Error

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

Solution code:
r_1, c_1, r_2, c_2 = map(int, input().split())

import math

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 = 10**4
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 = 0
for i in range(r_1, r_2 + 1):
  for j in range(c_1, c_2 + 1):
    ans += cmb(i+j, i, mod)
    ans %= mod

print(ans % mod)

Submission status: Runtime Error

Solution code:
r_1, c_1, r_2, c_2 = map(int, input().split())

import math

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 = 10**4
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 = 0
for i in range(r_1, r_2 + 1):
  for j in range(c_1, c_2 + 1):
    ans += cmb(i+j, i, mod)
    ans %= mod

print(ans)

Submission status: Runtime Error

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 = 2*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: Runtime Error

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

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

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p), 0! = 1! = 1
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p), 0! = 1! = 1
inv = [0, 1]  # inv[n] = n^(-1) mod p, 0! = 1　だけど便宜上inv[0]=0にしてる

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

ans = 0
for i in range(r1,r2+1):
    for j in range(c1,c2+1):

        ans += nCr_mod_p(i+j,i,p)

print(ans%p)

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 = 10**4
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: Runtime Error

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

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

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**6,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)