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: Time Limit Exceeded

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())
def comb(a,b):
  if a==b or b==0 or a==0:return 1
  ret=1
  for i in range(a-b+1,a+1):
    ret*=ModInt(i)
  for j in range(1,b+1):
    ret/=ModInt(j)
  return ret
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: Time Limit Exceeded

Solution code:
def main():
    r1, c1, r2, c2 = map(int, raw_input().split())
    MOD = 10 ** 9 + 7
    
    
    # 階乗 & 逆元計算
    factorial = [1]
    inverse = [1]
    for i in range(1, r2 + c2 + 10):
        factorial.append(factorial[-1] * i % MOD)
        inverse.append(pow(factorial[-1], MOD - 2, MOD))
    
    
    # 組み合わせ計算
    def nCr(n, r):
        if n < r or r < 0:
            return 0
        elif r == 0:
            return 1
        return factorial[n] * inverse[r] * inverse[n - r] % MOD
    
    
    ans = 0
    for r in range(r1, r2 + 1):
        ans += ((nCr(r + c2 + 1, r + 1) % MOD) - (nCr(r + c1, r + 1) % MOD)) % MOD
        ans %= MOD
    
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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())
def comb(a,b):
  if a==b or b==0 or a==0:return 1
  ret=1
  for i in range(a-b+1,a+1):
    ret*=ModInt(i)
  for j in range(1,b+1):
    ret/=ModInt(j)
  return ret
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: Time Limit Exceeded

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


# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, r2 + c2 + 10):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


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

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
"""
F
"""
import sys
input=sys.stdin.readline
mod=10**9+7
MAX=2*10**6+100

g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))
    
def cmb(n,r):
    return g1[n]*g2[r]*g2[n-r]%mod

r1,c1,r2,c2=map(int,input().split())
if r2-r1<c2-c1:
    c1,r1=r1,c1
    c2,r2=r2,c2

S=cmb(r1+c1,r1)
ans=S
table1=[]
table2=[]
num1=c1+1
num2=r1+1
for i in range(c2-c1):
    S=(2*S+cmb(num1+i+r1-1,r1-1)+cmb(num2+i+c1-1,c1-1))%mod
    ans=(ans+S)%mod  
    
num1=r1
num2=r1+c2-c1+1
for i in range(r2-(r1+c2-c1)):
    S=(2*S-cmb(num1+i+c2,c2)+cmb(num2+i+c1-1,c1-1))%mod
    ans=(ans+S)%mod  
    
num1=c1
num2=r2-(c2-c1)
for i in range(c2-c1):
    S=(2*S-cmb(num1+i+r2,r2)-cmb(num2+i+c2,c2))%mod
    ans=(ans+S)%mod  

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Factorial():
    def __init__(self,n,mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n+1)]
        self.inv = [0 for _ in range(n+1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i+1] = self.factorial[i]*(i+1)%mod
            self.inv[i+1] = self.inv[i]*pow(i+1,mod-2,mod)%mod
    def comb(self,m,k): #組み合わせ 0<=k<=m<=n
        return self.factorial[m]*self.inv[k]*self.inv[m-k]%self.mod
    def fact(self,m): #階乗
        return self.factorial[m]
    def perm(self,m,k): #順列
        if m < k: return 0
        return self.factorial[m]*self.inv[m-k]%self.mod
    def invfact(self,m): #階乗の逆数
        return self.inv[m]

MOD = 1000000007

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

f = Factorial(2000010,MOD)

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

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

def many_paths_naive(r1, c1, r2, c2):
    def nCk(n, k):
        C = 1
        for n, d in zip(range(n, n - k, -1), range(1, k + 1, 1)):
            C = (C * n) // d
        return C
    n = 0
    for i in range(r1, r2+1):
        for j in range(c1, c2+1):
            n += nCk(i + j, i)
            n = n % (10**9 + 7)
    return n

print(many_paths_naive(r1, c1, r2, c2))

Submission status: Time Limit Exceeded

Solution code:
x1, y1, x2, y2 = map(int, input().split())
grid = [[0 for i in range(x2 + 5)] for j in range(y2 + 5)]

for i in range(1):
    for j in range(x2 + 5):
        grid[i][j] = 1

for i in range(y2 + 5):
    grid[i][0] = 1

for i in range(1, y2 + 3):
    for j in range(1, x2 + 3):
        grid[i][j] = grid[i - 1][j] + grid[i][j - 1]

#for i in grid:
#    print(i)

ans = 0
for i in range(y1, y2 + 1):
    for j in range(x1, x2 + 1):
        #print(grid[i][j])
        ans += grid[i][j]
        ans %= 10 ** 9 + 7


print(ans)

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d = map(int,input().split())

dp = [[1 for i in range(d+1)] for j in range(c+1)]
dp[0][0] = 0

mod = 10**9+7
#print(dp)
for i in range(1,c+1):
    for j in range(1,d+1):
        dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod

ans = 0
for i in range(a,c+1):
    for j in range(b,d+1):
        ans += dp[i][j]
        ans %=mod
        #print(dp[i+1][j+1])
#print(dp)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
x,y,X,Y = map(int,input().split())
u = math.factorial(x+y) % (10**9 + 7)
d = (math.factorial(x)*math.factorial(y)) % (10**9 + 7)
K = u//d
keisu = 0
for i in range(X-x+1):
    for j in range(Y-y+1):
        u = (math.factorial(i+j) % (10**9 + 7))
        d = (math.factorial(i) % (10**9 + 7))*(math.factorial(j) % (10**9 + 7))
        keisu += u//d
ans = ((K +1)* keisu - 1) % (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
P = 10**9 + 7

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

table = [[0 for i in range(D+1)] for j in range(C+1)]
for j in range(D+1):
    table[0][j] = 1
for i in range(C+1):
    table[i][0] = 1

for i in range(1,C+1):
    for j in range(1, D+1):
        table[i][j] = (table[i-1][j] + table[i][j-1]) 

table2 = [[0 for i in range(D+1)] for j in range(C+1)]
for j in range(D+1):
    table2[0][j] = j
for i in range(C+1):
    table2[i][0] = i

for i in range(1,C+1):
    for j in range(1, D+1):
        table2[i][j] = (table2[i-1][j] + table2[i][j-1] - table2[i-1][j-1]+ table[i][j]) %P

print((table2[C][D] - table2[A-1][D] - table2[C][B-1] + table2[A-1][B-1])%P)

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10**9 + 7


def pathes(x, y):
    return math.factorial(x + y) // (math.factorial(x) * math.factorial(y))


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

    a = pathes(r1, c1) - 1
    b = pathes(r1, c2 + 1) - 1
    c = pathes(r2 + 1, c1) - 1
    d = pathes(r2 + 1, c2 + 1) - 1

    print((d - c - b + a) % MOD)


main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7  # 出力の制限

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


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


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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import unittest


class TestF(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(1, 1, 2, 2), 14)

    def test_2(self):
        self.assertEqual(think(314, 159, 2653, 589), 602215194)


def solve():
    r1, c1, r2, c2 = read()
    result = think(r1, c1, r2, c2)
    write(result)


def read():
    return read_int(4)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(r1, c1, r2, c2):
    mode = 10 ** 9 + 7
    count = 0

    n = r2 + c2
    inverse_fact = [1] * (n + 1)
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i
        fact[i] %= mode
    inverse_fact[n] = pow(fact[n], mode - 2, mode)
    for i in range(n - 1, -1, -1):
        inverse_fact[i] = inverse_fact[i + 1] * (i + 1)
        inverse_fact[i] %= mode

    cache = {}
    for y in range(r1, r2 + 1):
        for x in range(c1, c2 + 1):
            if (x + y, x) in cache:
                count += cache[(x + y, x)]
            else:
                result = combination(x + y, x, fact, inverse_fact, mode)
                cache[(x + y, x)] = result
                cache[(x + y, y)] = result
                count += result
            count %= mode

    return count


def combination(n, r, fact, inverse_fact, mode):
    if r > n or n < 0 or r < 0:
        return 0
    return (fact[n] * inverse_fact[r] * inverse_fact[n - r]) % mode


def write(result):
    print(result)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Time Limit Exceeded

Solution code:
import unittest


class TestF(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(1, 1, 2, 2), 14)

    def test_2(self):
        self.assertEqual(think(314, 159, 2653, 589), 602215194)


def solve():
    r1, c1, r2, c2 = read()
    result = think(r1, c1, r2, c2)
    write(result)


def read():
    return read_int(4)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(r1, c1, r2, c2):
    mode = 10 ** 9 + 7
    count = 0

    n = r2 + c2
    inverse_fact = [1] * (n + 1)
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i
        fact[i] %= mode
    inverse_fact[n] = pow(fact[n], mode - 2, mode)
    for i in range(n - 1, -1, -1):
        inverse_fact[i] = inverse_fact[i + 1] * (i + 1)
        inverse_fact[i] %= mode

    for y in range(r1, r2 + 1):
        for x in range(c1, c2 + 1):
            count += combination(x + y, x, fact, inverse_fact, mode)
            count %= mode

    return count


def combination(n, r, fact, inverse_fact, mode):
    if r > n or n < 0 or r < 0:
        return 0
    return (fact[n] * inverse_fact[r] * inverse_fact[n - r]) % mode


def write(result):
    print(result)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Time Limit Exceeded

Solution code:
import math

arr = list(map(int,input().split()))

count = 0
for i in range(arr[0],arr[2]+1):
    for j in range(arr[1],arr[3]+1):
        count+=math.factorial(i+j) // (math.factorial(i) * math.factorial(j))


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

Submission status: Time Limit Exceeded

Solution code:
import math

arr = list(map(int,input().split()))

count = 0
for i in range(arr[0],arr[2]+1):
    for j in range(arr[1],arr[3]+1):
        count+=math.factorial(i+j) // (math.factorial(i) * math.factorial(j))


if (count < (10**9 + 7)):
  print(count)
else:
  print(count % (10**9 + 7))

Submission status: Time Limit Exceeded

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 )
    
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: Time Limit Exceeded

Solution code:
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  a = power1[n]
  b = power2[n-k]
  c = power2[k]
  return (a*b*c)%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
mod = 10**9 + 7
r1,c1,r2,c2 = map(int,input().split())
power1 = [0]
power2 = [0]
p1 = 1
p2 = 1
for i in range(1,r2+c2+1):
    p1 = (p1*i)%mod
    p2 = power_func(p1,mod-2,mod)
    power1.append(p1)
    power2.append(p2)
ans = 0
for r in range(r1,r2+1):
    for c in range(c1,c2+1):
        ans = ans+comb(r+c,c,mod)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  a = power1[n]
  b = power2[n-k]
  c = power2[k]
  return (a*b*c)%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
mod = 10**9 + 7
r1,c1,r2,c2 = map(int,input().split())
power1 = [0]
power2 = [0]
p1 = 1
p2 = 1
for i in range(1,r2+c2+1):
    p1 = (p1*i)%mod
    p2 = power_func(p1,mod-2,mod)
    power1.append(p1)
    power2.append(p2)
ans = 0
for r in range(r1,r2+1):
    for c in range(c1,c2+1):
        ans = (ans+comb(r+c,c,mod))%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import unittest


class TestF(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(1, 1, 2, 2), 14)

    def test_2(self):
        self.assertEqual(think(314, 159, 2653, 589), 602215194)


def solve():
    r1, c1, r2, c2 = read()
    result = think(r1, c1, r2, c2)
    write(result)


def read():
    return read_int(4)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(r1, c1, r2, c2):
    mode = 10 ** 9 + 7
    count = 0
    board = [[0 for x in range(c2 + 1)] for y in range(r2 + 1)]
    for x in range(len(board[0])):
        if x == 0:
            continue
        board[0][x] = 1
    for y in range(len(board)):
        if y == 0:
            continue
        board[y][0] = 1
    for y in range(1, len(board)):
        for x in range(1, len(board[0])):
            board[y][x] = board[y][x - 1] + board[y - 1][x]
            board[y][x] %= mode
            if c1 <= x <= c2 and r1 <= y <= r2:
                count += board[y][x]
                count %= mode

    return count


def write(result):
    print(result)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Time Limit Exceeded

Solution code:
x1, y1, x2, y2 = map(int,input().split())
mod = 10**9+7

t = [1]*(x2+1)
for i in range(y1-1):
    s = [1]*(x2+1)
    for j in range(1,x2+1):
        s[j] = (s[j-1] + t[j])%mod
    t = s
ans = 0
for i in range(y2-y1+1):
    s = [1]*(x2+1)
    for j in range(1,x2+1):
        s[j] = (s[j-1] + t[j])%mod
    for j in range(x1,x2+1):
        ans = (ans+s[j])%mod
    t = s
print(ans)

Submission status: Accepted

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

class Factorial:
  def __init__(self, n, mod):
    self.mod = mod
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod
  def permi(self, n, k):
    return self.f[n] * self.i[n - k] % self.mod

n = max(r1, c1, r2, c2)
f = Factorial(n * 2 + 1, mod)
res = 0
for i in range(r1, r2 + 1):
  res += f.combi(c2 + i + 1, i + 1) - f.combi(c1 + i, i + 1)
  res %= mod
print(res)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect
from functools import reduce

def main():
    mod = 10 ** 9 + 7
    def comb(n, r):
        numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
        denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
        return numerator * pow(denominator, mod - 2, mod) % mod
    r_1, c_1, r_2, c_2 = MI()
    #0<=i<=r, o<=j<=cなる全ての(i,j)についてのf(i,j)の和をg(i,j)とする。これをg_rcと表記する。mはマイナス。
    g_r2c2 = (comb(r_2 + c_2 + 2, c_2 + 1) - 1) % mod
    g_r2c1m1 = (comb(r_2 + c_1 + 1, c_1) - 1) % mod
    g_r1m1c2 = (comb(r_1 + c_2 + 1, c_2 + 1) - 1) % mod
    g_r1m1c1m1 = (comb(r_1 + c_1, c_1) - 1) % mod
    ans = (((((g_r2c2 - g_r2c1m1) % mod) - g_r1m1c2) % mod) + g_r1m1c1m1) % mod

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

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

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

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

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

    if r == 0:
        return 1

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

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

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

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
n = 2000010
fact = [1] * (n + 1)
ifact = [1] * (n + 1)

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

for i in range(n):
    fact[i + 1] = fact[i] * (i + 1) % mod
    if i + 1 in [r1, c1, r2 + 1, c2 + 1]:
        ifact[i + 1] = pow(fact[i + 1], mod - 2, mod)

def comb(x, y):
    return (fact[x + y] * ifact[x] * ifact[y]) % mod


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

Submission status: Accepted

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

# コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
n=max(r1,c1,r2,c2)
for i in range(2,2*10**6+2):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)
ans=0
for k in range(r1,r2+1):
  tmp=cmb(k+1+c2,c2,mod)-cmb(k+1+c1-1,c1-1,mod)
  ans+=tmp
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
def C(n,r):
    if not 0<=r<=n: return 0
    r=min(r,n-r)
    N=reduce(lambda x,y: x*y%M, range(n,n-r,-1),1)
    D=reduce(lambda x,y: x*y%M, range(1,r+1),1)
    return N*pow(D,M-2,M)%M
def f(r,c): return C(r+c,c)
M=10**9+7
a,b,c,d=map(int, input().split())
print((f(c+1,d+1)-f(a,d+1)-f(c+1,b)+f(a,b))%M)

Submission status: Accepted

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

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


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


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

Submission status: Accepted

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


class Comb:
    def __init__(self, n, mod=pow(10, 9)+7, f=True, i=False, version=False):
        self.n = n
        self.mod = mod
        self.mod_inv = mod-2 if version else -1
        self.factorial_table = None
        self.inverse_table = None
        if f: self.get_factorial()
        if i: self.get_inverse()
        
    def get_factorial(self):
        self.factorial_table = [1]*(self.n+1)
        for i in range(1, self.n+1):
            self.factorial_table[i] = self.factorial_table[i-1]*i%self.mod
        self.inverse_table = None
    
    def get_inverse(self):
        mod = self.mod
        mod_inv = self.mod_inv
        self.inverse_table = [1]*(self.n+1)
        for i in range(self.n+1):
            self.inverse_table[i] = pow(self.factorial_table[i], mod_inv, mod)
    
    def factorial(self, n):
        if self.factorial_table == None:
            return None
        return self.factorial_table[n]
    
    def inverse(self, n):
        if self.inverse_table == None:
            return None
        return self.inverse_table[n]   
    
    def permutation(self, n, k):
        if self.factorial_table == None:
            return None
        mod = self.mod
        mod_inv = self.mod_inv
        if self.inverse_table == None:
            return self.factorial_table[n]*pow(self.factorial_table[n-k], mod_inv, mod)%mod
        return self.factorial_table[n]*self.inverse_table[n-k]%mod
            
    def comb(self, n, k):
        if self.factorial_table == None:
            return None
        mod = self.mod
        mod_inv = self.mod_inv
        if self.inverse_table == None:
            res = self.factorial_table[n]*pow(self.factorial_table[n-k], mod_inv, mod)%mod\
                                    *pow(self.factorial_table[k], mod_inv, mod)%mod
        else:
            res = self.factorial_table[n]*self.inverse_table[n-k]%mod\
                                    *self.inverse_table[k]%mod
        return res
    
    def recomb(self, n, k):
        if n+k-1 > self.n:
            return None
        return self.comb(n+k-1, k)


def main():
    r1, c1, r2, c2 = map(int, input().split())
    comb = Comb(10**6*2+1, version=True)
    mod = pow(10, 9) + 7

    ans = 0
    comb1, comb2 = comb.comb(c1+r2+1, r2+1), comb.comb(c1+r1, r1)
    for key in range(c1, c2+1):
        sub = (((r2+1) * comb1 - r1 * comb2) * pow(key+1, mod-2, mod)) % mod
        ans = (ans + sub) % mod

        comb1 = comb1 * (key + r2 + 2) * pow(key+1, mod-2, mod) % mod
        comb2 = comb2 * (key + r1 + 1) * pow(key+1, mod-2, mod) % mod


    print(ans)


    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

mod = 1000000007

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

def fac(n):
    ret = 1
    for i in range(1, n + 1):
        ret = (ret * i) % mod
    return ret

def facinv(n):
    return pow(fac(n), mod - 2)

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

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

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

Submission status: Accepted

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

mod = 10**9+7 #出力の制限
N = (2*(10**6))+5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
a,b,c,d=map(int,input().split())
print((cmb(c+d+2,c+1,mod)-cmb(d+1+a,a,mod)-cmb(b+c+1,c+1,mod)+cmb(a+b,a,mod))%mod)

Submission status: Accepted

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

class Factorial:
  def __init__(self, n, mod):
    self.mod = mod
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod
  def permi(self, n, k):
    return self.f[n] * self.i[n - k] % self.mod

f = Factorial(max(r1, c1, r2, c2) * 3, mod)

res = 0
for i in range(r1, r2 + 1):
  res += (f.combi(i + c2 + 1, c2 + 1) * (c2 + 1) - f.combi(i + c1, c1) * c1) % mod * pow(i + 1, mod - 2, mod) % mod
  res %= mod
print(res)