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:
r1,c1,r2,c2=map(int,input().split())
MOD=10**9+7
idx=r2+c2+3
perm=[1]*(idx+1)
for i in range(1,idx+1):
    perm[i]=perm[i-1]*i
    perm[i]%=MOD
def inv_mod(a):
  return pow(a,MOD-2,MOD)

def comb(n,m,p=10**9+7):
    if n < m : return 0
    if n < 0 or m < 0:return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p
def g(i,j):
    return comb(i+j+2,i+1,mod)
def s(n,m):
    return comb(n+m+2, m+1, mod)
res=g(r2,c2)-g(r2,c1-1)-g(r1-1,c2)+g(r1-1,c1-1)

mod = 10**9+7
ans = s(r2,c2) - s(r2, c1-1) - s(r1-1, c2) + s(r1-1, c1-1)
ans %= mod
print(res)

Submission status: Runtime Error

Solution code:


import numpy as np
import sys
sys.setrecursionlimit(100000)



def acinput():
    return list(map(int, input().split(" ")))


mod=10**9+7
nCr = {}
def cmb_cash(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


def cmb2(n, r):
    global mod
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])%mod

    return int(result)

r1,c1,r2,c2=acinput()

#cmb=cmb_cash
#print(cmb(10,2))


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

#print(cmb(n, r, p))

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

#r1=1;r2=2;c1=1;c2=2;Sum[Binomial[r+c,r], {r, r1, r2},{c,c1,c2}]

Submission status: Runtime Error

Solution code:

from scipy.special import comb
import numpy as np
import sys
sys.setrecursionlimit(100000)



def acinput():
    return list(map(int, input().split(" ")))


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


mod=10**9+7
nCr = {}
def cmb_cash(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


def cmb2(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return int(result)

r1,c1,r2,c2=acinput()
cmb=cmb2
#cmb=cmb_cash
#print(cmb(10,2))
print(int(cmb(c1+r1,r1)-cmb(c1+r2+1,r2+1)-cmb(c2+r1+1,r1)+cmb(c2+r2+2,r2+1))%mod)

#r1=1;r2=2;c1=1;c2=2;Sum[Binomial[r+c,r], {r, r1, r2},{c,c1,c2}]

Submission status: Runtime Error

Solution code:

from scipy.special import comb
import numpy as np
import sys
sys.setrecursionlimit(100000)



def acinput():
    return list(map(int, input().split(" ")))




def cmb2(n, r):
    """
    Calculate the number of combination (nCr = nPr/r!).
    The parameters need to meet the condition of n >= r >= 0.
    It returns 1 if r == 0, which means there is one pattern
    to choice 0 items out of the number of n.
    """

    # 10C7 = 10C3
    r = min(r, n-r)

    # Calculate the numerator.
    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i

    # Calculate the denominator. Should use math.factorial?
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i

    return numerator // denominator



cmb=comb
r1,c1,r2,c2=acinput()

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

#r1=1;r2=2;c1=1;c2=2;Sum[Binomial[r+c,r], {r, r1, r2},{c,c1,c2}]

Submission status: Runtime Error

Solution code:

from scipy.special import comb
import numpy as np
import sys
sys.setrecursionlimit(100000)



def acinput():
    return list(map(int, input().split(" ")))




def cmb2(n, r):
    """
    Calculate the number of combination (nCr = nPr/r!).
    The parameters need to meet the condition of n >= r >= 0.
    It returns 1 if r == 0, which means there is one pattern
    to choice 0 items out of the number of n.
    """

    # 10C7 = 10C3
    r = min(r, n-r)

    # Calculate the numerator.
    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i

    # Calculate the denominator. Should use math.factorial?
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i

    return numerator // denominator



cmb=comb
r1,c1,r2,c2=acinput()

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

#r1=1;r2=2;c1=1;c2=2;Sum[Binomial[r+c,r], {r, r1, r2},{c,c1,c2}]

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce

def comb(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 + 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 )
    
    
    
r1, c1, r2, c2 = [int(i) for i in input().split()]
 
def calc(r, c):
    a = comb(r + c + 2, r + 1, mod) - r - c - 2
    b = r * (r + 3) / 2
 
    if c == 1:
        return b
    else:
        return a
 
result = calc(r2, c2) - calc(r2, c1 - 1) - calc(r1 - 1, c2) + calc(r1 - 1, c1 - 1)

if result < 0:
  result += 10**9 + 7
print(result)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
from operator import mul
from functools import reduce

def comb(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 + 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 )
    
    
    
r1, c1, r2, c2 = [int(i) for i in input().split()]
 
def calc(r, c):
    a = comb(r + c + 2, r + 1, mod) - r - c - 2
    b = r * (r + 3) / 2
 
    if c == 1:
        return b
    else:
        return a
 
result = calc(r2, c2) - calc(r2, c1 - 1) - calc(r1 - 1, c2) + calc(r1 - 1, c1 - 1)
 
print(result)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
from operator import mul
from functools import reduce

def comb(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 = [int(i) for i in input().split()]
 
def calc(r, c):
    a = comb(r + c + 2, r + 1, mod) - r - c - 2
    b = r * (r + 3) / 2
 
    if c == 1:
        return b
    else:
        return a
 
result = calc(r2, c2) - calc(r2, c1 - 1) - calc(r1 - 1, c2) + calc(r1 - 1, c1 - 1)
 
print(result %  (10**9+7))

Submission status: Runtime Error

Solution code:
from scipy.special import comb

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

def calc(r, c):
    a = comb(r + c + 2, r + 1, exact=True) - r - c - 2
    b = r * (r + 3) / 2

    if c == 1:
        return b
    else:
        return a

result = calc(r2, c2) - calc(r2, c1 - 1) - calc(r1 - 1, c2) + calc(r1 - 1, c1 - 1)

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

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
def inv_mod(a,p=MOD):
    def inv_mod_sub(a,p):
        if a == 1:
            return 1,0
        else:
            d,r = p//a,p%a
            x,y = inv_mod_sub(r,a)
            return y-d*x,x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n,k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD

def f(a,b):
  return comb_mod(a+b,b)

r1,c1,r2,c2 = map(int,input().split())
f_mod=[1]*(2*10**6)
f_mod_inverse=[1]*(2*10**6)
for i in range(1,2*10**6):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD
print((f(r2+1,c2+1)-f(r1,c2+1)-f(r2+1,c1)+f(r1,c1))%MOD)

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
def inv_mod(a,p=MOD):
    def inv_mod_sub(a,p):
        if a == 1:
            return 1,0
        else:
            d,r = p//a,p%a
            x,y = inv_mod_sub(r,a)
            return y-d*x,x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n,k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD

def f(a,b):
  return comb_mod(a+b,b)

r1,c1,r2,c2 = map(int,input().split())
f_mod=[1]*(2*10**6)
f_mod_inverse=[1]*(2*10**6)
for i in range(1,10**6):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD
print((f(r2+1,c2+1)-f(r1,c2+1)-f(r2+1,c1)+f(r1,c1))%MOD)

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
def inv_mod(a,p=MOD):
    def inv_mod_sub(a,p):
        if a == 1:
            return 1,0
        else:
            d,r = p//a,p%a
            x,y = inv_mod_sub(r,a)
            return y-d*x,x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n,k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD

def f(a,b):
  return comb_mod(a+b,b)

r1,c1,r2,c2 = map(int,input().split())
f_mod=[1]*(10**6)
f_mod_inverse=[1]*(10**6)
for i in range(1,10**6):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD
print((f(r2+1,c2+1)-f(r1,c2+1)-f(r2+1,c1)+f(r1,c1))%MOD)

Submission status: Runtime Error

Solution code:
import sys
import socket

hostnames = ['N551J', 'F551C', 'X553M']
input_file = 'f1.in'
if socket.gethostname() in hostnames:
    sys.stdin = open(input_file)


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()

M = 10 ** 9 + 7
MAX = 10 ** 6 + 2
inv = [0] * MAX
inv[1] = 1
for i in range(2, MAX):
    inv[i] = - inv[M % i] * (M // i)
    inv[i] %= M

def f(r, c):
    res = 1
    for k in range(c + 1):
        res *= r + c + 2 - k    
        res %= M
        res *= inv[k + 1]
        res %= M
    res -= 1
    res %= M
    return res

N = 3
b = [[1] * N for _ in range(N)]
for i in range(1, N):
    for j in range(1, N):
        b[i][j] = (b[i - 1][j - 1] + b[i - 1][j]) % M


def f_exact_but_slow(r, c):
    res = 0
    for i in range(r + 1):
        for j in range(c + 1):
            res += b[i][j]
            res %= M
    return res


def solve():
    r1, c1, r2, c2 = read_int_list()
    res = f(r2, c2) 
    res -= f(r1 - 1, c2) 
    res -= f(r2, c1 - 1) 
    res += f(r1 - 1, c1 - 1)
    return res


def main():
    res = solve()
    print(res)


def find_mismatch()
    for r in range(20):
        for c in range(20):
            expected = f_exact_but_slow(r, c)
            output = f(r, c)
            if output == expected:
                continue
            print('r, c, expected, output:', end=' ')
            print(r, c, expected, output)


if __name__ == '__main__':
    # main()
    find_mismatch()

Submission status: Runtime Error

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

div=10**9+7
def g(r,c):
    sum=0
    for i in range(c+1):
        sum+= f(r,i)
    for j in range(r+1):
        sum+= f(j,c)
    return int(sum)%div

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  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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

def f(r,c):
    return cmb(r+c,c,p)
#def f(r,c):
#    RC=math.factorial(r+c)
#    R=math.factorial(r)
#    C=math.factorial(c)
#    ans=int(RC//(R*C))%div
#    return ans

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

Submission status: Runtime Error

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

div=10**9+7
def g(r,c):
    sum=0
    for i in range(c+1):
        sum+= f(r,i)
    for j in range(r+1):
        sum+= f(j,c)
    return int(sum)%div

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 ** 5  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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

def f(r,c):
    return cmb(r+c,c,p)
#def f(r,c):
#    RC=math.factorial(r+c)
#    R=math.factorial(r)
#    C=math.factorial(c)
#    ans=int(RC//(R*C))%div
#    return ans

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

Submission status: Runtime Error

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

div=10**9+7
def g(r,c):
    sum=0
    for i in range(c+1):
        sum+= f(r,i)
    for j in range(r+1):
        sum+= f(j,c)
    return int(sum)%div

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 ** 7  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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

def f(r,c):
    return cmb(r+c,c,p)
#def f(r,c):
#    RC=math.factorial(r+c)
#    R=math.factorial(r)
#    C=math.factorial(c)
#    ans=int(RC//(R*C))%div
#    return ans

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

Submission status: Runtime Error

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

div=10**9+7
def g(r,c):
    sum=0
    for i in range(c+1):
        sum+= f(r,i)
    for j in range(r+1):
        sum+= f(j,c)
    return int(sum)%div

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  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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 f(r,c):
    return cmb(r+c,c,p)
#def f(r,c):
#    RC=math.factorial(r+c)
#    R=math.factorial(r)
#    C=math.factorial(c)
#    ans=int(RC//(R*C))%div
#    return ans

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

Submission status: Runtime Error

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

#output
mod = 10**9 + 7

n_ = 10**10 + 3
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 cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

answer = 0
for j in range(c_1, c_2+1):
    answer += cmb(r_2+j+1, j+1) % mod - cmb(r_1+j, j+1) % mod

print(answer % mod)

Submission status: Runtime Error

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

#output
mod = 10**9 + 7

n_ = 10**6 + 3
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 cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

answer = 0
for j in range(c_1, c_2+1):
    answer += cmb(r_2+j+1, j+1) % mod - cmb(r_1+j, j+1) % mod

print(answer % mod)

Submission status: Runtime Error

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

#output
mod = 10**9 + 7

n_ = 10**5 + 3
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 cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

answer = 0
for j in range(c_1, c_2+1):
    answer += cmb(r_2+j+1, j+1) % mod - cmb(r_1+j, j+1) % mod

print(answer % mod)

Submission status: Runtime Error

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

#output
mod = 10**9 + 7

n_ = 10**6 + 3
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 cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

answer = 0
for i in range(r_1, r_2+1):
    for j in range(c_1, c_2+1):
        answer += cmb(i+j, j) % mod
print(answer % mod)

Submission status: Runtime Error

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

#output
mod = 10**9 + 7

n_ = 10**5 + 3
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 cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

answer = 0
for i in range(r_1, r_2+1):
    for j in range(c_1, c_2+1):
        answer += cmb(i+j, j) % mod
print(answer % mod)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 7)

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


# 階乗、Combinationコンビネーション(numpyを使う)

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


MOD = 10 ** 9 + 7
U = 10**6 * 2 + 1
fact, fact_inv = make_fact(U, MOD)


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


def calc_rc(r, c):
    a = mod_comb_k(r + c + 2, r + 1, MOD)
    b = 1
    return a-b


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

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 7)

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


# 階乗、Combinationコンビネーション(numpyを使う)

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


MOD = 10 ** 9 + 7
U = 10**6 * 2 + 1
fact, fact_inv = make_fact(U, MOD)


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


def calc_rc(r, c):
    a = mod_comb_k(r + c + 2, r + 1, MOD)
    b = 1
    return a-b


ans = calc_rc(r2, c2) + calc_rc(r1-1, c1-1) - \
    calc_rc(r1-1, c2) - calc_rc(r2, c1-1)

print(ans)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#define ll long long int
using namespace std;

ll r1, c1, r2, c2, MOD=1e9+7, score=0;
vector<vector<ll> > v;

ll dp(ll x, ll y) {
  if (v[x][y]) return v[x][y];
  if (x==0 and y==0) return 0;
  if (x==0) return 1;
  if (y==0) return 1;
  ll r = (dp(x-1, y) + dp(x, y-1)) % MOD;
  v[x][y] = r;
  if (r1 <= x && x <= r2 && c1 <= y && y <= c2) score = (score + r) % MOD;
  return r;
}

int main() {
  cin >> r1 >> c1 >> r2 >> c2;
  v.resize(r2+1, vector<ll> (c2+1, 0));
  dp(r2, c2);
  cout << score << "\n";

  return 0;
}

Submission status: Runtime Error

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

M=10**6
fac=[0]*(M+1)
ifac=[0]*(M+1)
fac[0]=1
for i in range(1,M+1):
    fac[i]=fac[i-1]*i%MOD
ifac[M]=pow(fac[M],MOD-2,MOD)
for i in range(M-1,0,-1):
    ifac[i]=ifac[i+1]*(i+1)%MOD

def comb(a,b): return fac[a]*ifac[a-b]*ifac[b]%MOD

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

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

Submission status: Runtime Error

Solution code:
N = input()
list_N = []
a=0
for i in range(len(N)):
    if N[i]==" ":
        list_N.append(int(N[a:i]))
        a = i
list_N.append(int(N[a+1:len(N)]))
print(list_N)

r_1=list_N[0]
c_1=list_N[1]
r_2=list_N[2]
c_2=list_N[3]

# print(r_2)

def kaijou(n):
    if n==1:
        a=1
    if n>=2:
        a=kaijou(n-1)*n
    return a
        
def convi(r, c):
    C=kaijou(r+c)/(kaijou(r)*kaijou(c))
    return C

sum=0

for i in range(r_2-r_1+1):
    for j in range(c_2-c_1+1-i):
        if r_1+i==(c_1+i)+j:
            sum += convi(r_1+i, (c_1+i)+j)
        elif r_1+i!=(c_1+i)+j:
            sum += convi(r_1+i, (c_1+i)+j)*2
        
        
print(int(sum))

Submission status: Runtime Error

Solution code:
r1,c1,r2,c2=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
N=10**6
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
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)

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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;
//const ll MOD=998244353;

const int MAX_N=1010101*2;
ll inv[MAX_N+1], fact[MAX_N+1], ifact[MAX_N+1];

ll comb(int n, int k){
  if(n<k) return 0;
  return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD;
}

void prepare(){
  inv[1]=fact[0]=fact[1]=ifact[0]=ifact[1]=1LL;
  for(int i=2;i<=MAX_N;i++){
    inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
    fact[i]=fact[i-1]*i%MOD;
    ifact[i]=ifact[i-1]*inv[i]%MOD;
  }
}

ll f(int r,int c){
  ll ret=0;
  for(int i=1;i<=r+1;i++){
    ll tmp=fact[i+c]*ifact[i]%MOD*ifact[c]%MOD;
    ret=(ret+tmp)%MOD;
  }
  return ret;
}


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  prepare();

  int R[2],C[2]; cin>>R[0]>>C[0]>>R[1]>>C[1];

  ll ans=f(R[1],C[1]);
  ans=(ans-f(R[0]-1,C[1])+MOD)%MOD;
  ans=(ans-f(R[1],C[0]-1)+MOD)%MOD;
  ans=(ans+f(R[0]-1,C[0]-1))%MOD;
  cout<<ans<<endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;
//const ll MOD=998244353;

const int MAX_N=1010101;
ll inv[MAX_N+1], fact[MAX_N+1], ifact[MAX_N+1];

ll comb(int n, int k){
  if(n<k) return 0;
  return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD;
}

void prepare(){
  inv[1]=fact[0]=fact[1]=ifact[0]=ifact[1]=1LL;
  for(int i=2;i<=MAX_N;i++){
    inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
    fact[i]=fact[i-1]*i%MOD;
    ifact[i]=ifact[i-1]*inv[i]%MOD;
  }
}

ll f(int r,int c){
  ll ret=0;
  for(int i=1;i<=r+1;i++){
    ll tmp=fact[i+c]*ifact[i]%MOD*ifact[c]%MOD;
    ret=(ret+tmp)%MOD;
  }
  return ret;
}


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  prepare();

  int R[2],C[2]; cin>>R[0]>>C[0]>>R[1]>>C[1];

  ll ans=f(R[1],C[1]);
  ans=(ans-f(R[0]-1,C[1])+MOD)%MOD;
  ans=(ans-f(R[1],C[0]-1)+MOD)%MOD;
  ans=(ans+f(R[0]-1,C[0]-1))%MOD;
  cout<<ans<<endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
# コンビネーション
mod = 10**9+7
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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

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

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

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

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
import numpy as np

mod = 10**9 + 7

r1, c1, r2, c2 = map(int, input().split())
f = np.ones((r2 + 1, c2 + 1), dtype=np.int)
g = np.ones((r2 + 1, c2 + 1), dtype=np.int)
for i, j in np.ndindex(r2, c2):
  f[i+1, j+1] = (f[i, j+1] + f[i+1, j]) % mod
print(f[r1:, c1:].sum() % mod)

Submission status: Runtime Error

Solution code:
import numpy as np

mod = 10**9 + 7

r1, c1, r2, c2 = map(int, input().split())
f = np.ones((r2 + 1, c2 + 1), dtype=np.int)
g = np.ones((r2 + 1, c2 + 1), dtype=np.int)
for i, j in np.ndindex(r2, c2):
  f[i+1, j+1] = (f[i, j+1] + f[i+1, j]) % mod
print(f[r1:, c2:].sum() % mod)

Submission status: Runtime Error

Solution code:
import numpy as np

r1, c1, r2, c2 = map(int, input().split())
f = np.ones((r2 + 1, c2 + 1), dtype=np.int)
g = np.ones((r2 + 1, c2 + 1), dtype=np.int)
for i, j in np.ndindex(r2, c2):
  f[i+1, j+1] = f[i, j+1] + f[i+1, j]
print(f[r1:, c2:].sum())

Submission status: Runtime Error

Solution code:
import numpy as np

r1, c1, r2, c2 = map(int, input().split())
f = np.ones((r2 + 1, c2 + 1), dtype=np.int)
g = np.ones((r2 + 1, c2 + 1), dtype=np.int)
for i, j in np.ndindex(r2, c2)
  f[i+1, j+1] = f[i, j+1] + f[i+1, j]
print(f[r1:, c2:].sum())

Submission status: Runtime Error

Solution code:
#from scipy.special import comb
r1, c1, r2, c2 = map(int, input().split())
#mod = 1000000007
#hole = (comb(r2 + c2 + 2, r2 + 1, exact=True) - 1) % mod
#rect1 = (comb(r2 + c1 - 1 + 2, r2 + 1, exact=True) - 1) % mod
#rect2 = (comb(r1 - 1 + c2 + 2, r1, exact=True) - 1) % mod
#duplicate = (comb(r1 + c1, r1, exact=True) - 1) % mod
#ans = (hole - rect1 - rect2 + duplicate) % mod

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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 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

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

Submission status: Runtime Error

Solution code:
from scipy.special import comb
r1, c1, r2, c2 = map(int, input().split())
mod = 1000000007
hole = (comb(r2 + c2 + 2, r2 + 1, exact=True) - 1) % mod
rect1 = (comb(r2 + c1 - 1 + 2, r2 + 1, exact=True) - 1) % mod
rect2 = (comb(r1 - 1 + c2 + 2, r1, exact=True) - 1) % mod
duplicate = (comb(r1 + c1, r1, exact=True) - 1) % mod
ans = (hole - rect1 - rect2 + duplicate) % mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

def cmb(n, k):
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

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

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

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

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

# 16

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

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

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

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

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