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:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import bisect
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21

def routes_from_zero(r,c, factorial, gyaku):
    ret = 0
    for i in range(r + 1):
        tmp = 1
        tmp *= factorial[i+c+1]
        tmp %= MOD
        tmp *= gyaku[c]
        tmp %= MOD
        tmp *= gyaku[i+1]
        tmp %= MOD

        ret += tmp
        ret %= MOD

    return ret

def main():
    r1, c1, r2, c2 = getlist()
    factorial = [1]
    tmp = 1
    for i in range(1, r2 + c2 + 5):
        tmp *= i
        tmp %= MOD
        factorial.append(tmp)
    gyaku = [pow(i, MOD - 2, MOD) for i in factorial]

    # print(routes_from_zero(r2, c2))
    # print(routes_from_zero(r1, c2))
    # print(routes_from_zero(r2, c1))
    # print(routes_from_zero(r1, c1))
    ans = routes_from_zero(r2, c2, factorial, gyaku) - routes_from_zero(r1 - 1, c2, factorial, gyaku)\
          - routes_from_zero(r2, c1 - 1, factorial, gyaku) + routes_from_zero(r1 - 1, c1 - 1, factorial, gyaku)
    print(ans % MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import bisect
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21

def routes_from_zero(r,c, factorial):
    ret = 0
    for i in range(r + 1):
        tmp = 1
        tmp *= factorial[i+c+1]
        tmp %= MOD
        tmp *= pow(factorial[c], MOD - 2, MOD)
        tmp %= MOD
        tmp *= pow(factorial[i + 1], MOD - 2, MOD)
        tmp %= MOD

        ret += tmp
        ret %= MOD

    return ret

def main():
    r1, c1, r2, c2 = getlist()
    factorial = [1]
    tmp = 1
    for i in range(1, r2 + c2 + 5):
        tmp *= i
        tmp %= MOD
        factorial.append(tmp)

    # print(routes_from_zero(r2, c2))
    # print(routes_from_zero(r1, c2))
    # print(routes_from_zero(r2, c1))
    # print(routes_from_zero(r1, c1))
    ans = routes_from_zero(r2, c2, factorial) - routes_from_zero(r1 - 1, c2, factorial)\
          - routes_from_zero(r2, c1 - 1, factorial) + routes_from_zero(r1 - 1, c1 - 1, factorial)
    print(ans % MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import bisect
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21

def routes_from_zero(r,c, factorial):
    ret = 0
    for i in range(r + 1):
        tmp = 1
        tmp *= factorial[i+c+1]
        tmp *= pow(factorial[c], MOD - 2, MOD)
        tmp *= pow(factorial[i + 1], MOD - 2, MOD)
        tmp %= MOD

        ret += tmp
        ret %= MOD

    return ret

def main():
    r1, c1, r2, c2 = getlist()
    factorial = [1]
    tmp = 1
    for i in range(1, r2 + c2 + 5):
        tmp *= i
        tmp %= MOD
        factorial.append(tmp)

    # print(routes_from_zero(r2, c2))
    # print(routes_from_zero(r1, c2))
    # print(routes_from_zero(r2, c1))
    # print(routes_from_zero(r1, c1))
    ans = routes_from_zero(r2, c2, factorial) - routes_from_zero(r1 - 1, c2, factorial)\
          - routes_from_zero(r2, c1 - 1, factorial) + routes_from_zero(r1 - 1, c1 - 1, factorial)
    print(ans % MOD)

if __name__ == '__main__':
    main()

"""
7 
aaaabbb
3
1 7 c
2 1 5
2 1 7
>> 2
>> 3


26 
abcdefghijklmnopqrstuvwxyz
7
2 1 26
2 2 26
2 5 5
2 11 20
2 25 26 
1 1 z
2 1 26
>> 26
>> 25
>> 1
>> 10
>> 2
>> 25
"""

Submission status: Time Limit Exceeded

Solution code:
class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod


def main():
    mod = 10 ** 9 + 7
    ncr = nCrMod(mod)

    r1, c1, r2, c2 = map(int, input().split())
    r1, c1 = r1 - 1, c1 - 1
    t = ncr(r2 + c2 + 2, c2 + 1) + ncr(r1 + c1 + 2, c1 + 1) - ncr(r1 + c2 + 2, c2 + 1) - ncr(r2 + c1 + 2, c1 + 1)
    print(t % mod)

main()

Submission status: Time Limit Exceeded

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

# 互除法
def get_euclidian (A, B):
  if B == 1:
    return (1)
  else:
    return (int((1 - A * get_euclidian (B, A % B)) / B))

# 階乗計算
F = [1]
for i in range(1, r2 + c2 + 3):
  F.append(F[i - 1] * i)

# 組み合わせ計算
def get_combi (n, r):

  NmodL = F[n] % L
  RmodL = F[r] % L
  SmodL = F[n-r] % L
  Euc = (get_euclidian(L, RmodL * SmodL) + L) % L
  return ((NmodL * Euc) % L)

combi1 = get_combi(r2 + c2 + 2, r2 + 1)
combi2 = get_combi(r2 + c1 + 1, c1)
combi3 = get_combi(r1 + c2 + 1, r1)
combi4 = get_combi(r1 + c1, r1)

print (int(combi1 - combi2 - combi3 + combi4))

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7
MAX = r2 + c2 + 10
fact = [1] * (MAX + 1)  # i!
finv = [1] * (MAX + 1)  # (i!)^{-1}
iinv = [1] * (MAX + 1)  # i^{-1}
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


def func(a, b):
    res = 0
    for i in range(a + 1):
        res += comb(i + b + 1, i + 1)
        res %= MOD
    return res


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

Submission status: Time Limit Exceeded

Solution code:
class Combination():
    # コンストラクタ
    def __init__(self, N:int, P:int):
        self.N = N
        self.P = P

        # fact[i] = (i! mod P)
        self.fact = [1, 1]   
        # factinv[i] = ((i!)^(-1) mod P)
        self.factinv = [1, 1]
        # factinv 計算用
        self.inv = [0, 1]    

        for i in range(2, N+1):
            self.fact.append((self.fact[-1] * i) % P)
            self.inv.append((-self.inv[P % i] * (P // i)) % P)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % P)
    
    # nCk (mod P)   (ただし、n<=N)
    def getComb(self, n:int, k:int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] * self.factinv[n-k] % self.P

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

C = Combination(r2+c2+2, MOD)

ans += C.getComb(r2+c2+2, r2+1)
ans -= C.getComb(r2+c1+1, r2+1)
ans -= C.getComb(r1+c2+1, r1)
ans += C.getComb(r1+c1, r1)

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys

def f(r, c, fact, revfact, mod):
    return (fact[r + c] * revfact[r] * revfact[c]) % mod

def g(r, c, fact, revfact, mod):
    if r == c == 0: return 1
    elif r == 0: return c + 1
    elif c == 0: return r + 1
    ans = 0
    for i in range(1, c + 2):
        ans += f(r, i, fact, revfact, mod)
        ans %= mod
    return ans

def solve():
    input = sys.stdin.readline
    r1, c1, r2, c2 = map(int, input().split())
    mod = 7 + 10 ** 9
    fact = [1] * (5 + r2 + c2)
    revfact = [1] * (5 + r2 + c2)
    for i in range(1, 5 + r2 + c2): fact[i] = (i * fact[i-1]) % mod
    revfact[4 + r2 + c2] = pow(fact[4 + r2 + c2], mod - 2, mod)
    for i in reversed(range(1, 4 + r2 + c2)): revfact[i] = ((i + 1) * revfact[i + 1]) % mod

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
def paths(r,c):
  return (facts[r+c]*ifacts[r]*ifacts[c])%mod

mod=10**9+7
r1,c1,r2,c2=map(int,input().split())
facts=[1]
ifacts=[1]
for i in range(1,r2+c2+10):
  facts.append((facts[-1]*i)%mod)
  ifacts.append((ifacts[-1]*pow(i,mod-2,mod))%mod)
ans=0
for i in range(r1+1,r2+2):
  ans+=paths(i,c2)-paths(i,c1-1)
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

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

n = [1]*(r2+c2+1)
mod = 10**9 + 7
for i in range(r2+c2):
    n[i+1] = (n[i]*((i+1)%mod))%mod
    
def calc(r,c):
    x = n[r+c]%mod
    y = (n[r]*n[c])%mod
    return (x*(pow(y,mod-2,mod)%mod))%mod

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

Submission status: Time Limit Exceeded

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

dp = [[0] * (r2 + 1) for _ in range(c2 + 1)]
for i in range(c2 + 1):
    dp[i][0] = 1
for i in range(r2 + 1):
    dp[0][i] = 1

for i in range(c2):
    for j in range(r2):
        dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]

ans = 0
for i in range(c1, c2 + 1):
    for j in range(r1, r2 + 1):
        ans += dp[i][j]
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
r1, c1, r2, c2 = map(int, input().split())
ans = 0
MOD = 1000000007
def f(a, MOD):
  r = 1
  for i in range(2, a + 1):
    r *= i
    
  return r % MOD
  
  

def C(n, m, MOD):
  if m < n:
    m, n = n, m
  return f(m, MOD) // (f(n, MOD) * f(m - n, MOD)) % MOD

for i in range(r1, r2 + 1):
  for j in range(c1, c2 + 1):
    ans += C(i , j + i, MOD)
    ans %= MOD
    
print(ans)

Submission status: Time Limit Exceeded

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

def g(x1,y1,x2,y2):
  if x1 > 0:
    if y1 > 0:
      return g(x1,0,x2,y2) - g(x1,0,x2,y1-1)
    else:
      return f(x2,y2) - f(x1-1,y2)
  else:
    if y1 > 0:
      return f(x2,y2) - f(x2,y1-1)
    else:
      return f(x2,y2)
    
def f(x,y):
  mod = 10**9+7
  res = 1
  for i in range(1,x+y+1):
    res = res*i%mod
  for i in range(1,x+1):
    res = res*pow(i, mod-2, mod)%mod
  for i in range(1,y+1):
    res = res*pow(i, mod-2, mod)%mod
  return res-1



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

Submission status: Time Limit Exceeded

Solution code:
#L, R = map(int,input().split())

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

def g(x1,y1,x2,y2):
  if x1 > 0:
    if y1 > 0:
      return g(x1,0,x2,y2) - g(x1,0,x2,y1-1)
    else:
      return f(x2,y2) - f(x1-1,y2)
  else:
    if y1 > 0:
      return f(x2,y2) - f(x2,y1-1)
    else:
      return f(x2,y2)
    
def f(x,y):
  m = 10**9+7
  res = 1
  for i in range(1,x+y+1):
    res = res*i%m
  for i in range(1,x+1):
    res = res*mod_inv(i,m)%m
  for i in range(1,y+1):
    res = res*mod_inv(i,m)%m
  return res-1


#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m


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

Submission status: Time Limit Exceeded

Solution code:
#L, R = map(int,input().split())

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

def g(x1,y1,x2,y2):
  if x1 > 0:
    if y1 > 0:
      return g(x1,0,x2,y2) - g(x1,0,x2,y1-1)
    else:
      return f(x2,y2) - f(x1-1,y2)
  else:
    if y1 > 0:
      return f(x2,y2) - f(x2,y1-1)
    else:
      return f(x2,y2)
    
def f(x,y):
  return h(x,y)-1

def h(x,y):
  m = 10**9+7
  res = 1
  for i in range(1,x+y+1):
    res = res*i%m
  for i in range(1,x+1):
    res = res*mod_inv(i,m)%m
  for i in range(1,y+1):
    res = res*mod_inv(i,m)%m
  return res


#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m


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

Submission status: Time Limit Exceeded

Solution code:
#F
from operator import mul
from functools import reduce

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

#pre-caluculation of the factorial
num = 10**7
fact=[0] * num
fact[0]=1
for i in range(1, num):
    fact[i] = (fact[i-1] * i) % mod

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def f(rr,cc):
    #(0,0)~(r,c)までのコンビネーションの累積和
    #print(rr+cc+2, cc+1)
    #print(combinations_count(rr+cc+2, cc+1))
    #return combinations_count(rr+cc+2, cc+1) - 1
    return (fact[rr+cc+2]%mod * pow(fact[rr+1]*fact[cc+1], mod-2, mod)) % mod -1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline().rstrip

"""
まず一般に剰余込みでの組み合わせの計算。
n!, (n!)^{-1} mod pの値を配列にまとめておき、nCr = (n!)/(r!)((n-r)!)をO(1)で計算する。

max = (用意する配列の最大長)
mod = （剰余）

(n!)^{-1}の計算は¥Prod_i i^{-1}を計算して求める。
i^{-1} mod pの計算はフェルマーの小定理より、mod pにおいて
0 = p = (p // i) * i + (p % i)
0 = (p // i) + (p % i) * i^{-1}
i^{-1} = -(p // i) * (p % i)^{-1}
"""

max = 10**7
mod = 10**9+7
fact = [1, 1] # fact[n] = (n! mod p)
factinv = [1, 1] # factinv[n] = ((n!)^{-1} mod p)
inv = [0, 1] # inv[n] = (n^{-1} mod p)

for i in range(2, max+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 r > n:
        return 0
    else:
        r = min(r, n-r)
        return fact[n] * factinv[r] * factinv[n-r] % mod


"""
いよいよ本題。
まずは¥Sum_{0¥le i¥le x, 0¥le j¥le y} _{i+j}C_iを計算する。
実際今回の問題は容易にこれに帰着可能。

¥Sum_{0¥le i¥le x, 0¥le j¥le y} _{i+j}C_i
    = ¥Sum_i (¥Sum_j _{i+j}C_i)
    = ¥Sum_i {(T+1)^i + (T+1)^{i+1} + ... + (T+1)^{i+y})のT^iの係数}
    = ¥Sum_i {¥frac{(1+T)^{i+y+1} - (1+T)^i}{T}のT^iの係数}
    = ¥Sum_i _{i+y+1}C_{i+1}

    = ¥Sum_i _{i+y+1}C_y
    = _{y+1}C_y + _{y+2}C_y + ... + _{y+x+1}C_y
    = {(1+T)^{y+1} + (1+T)^{y+2} + ... (1+T)^{y+x+1}のT^yの係数}
    = {¥frac{(1+T)^{x+y+2} - (1+T)^{y+1}}{T}のT^yの係数}
    = _{x+y+2}C_{y+1} - 1
"""
r1, c1, r2, c2 = map(int, input().split())
a = cmb(r2+c2+2, c2+1) - 1
b = cmb(r1+c2+1, c2+1) - 1
c = cmb(r2+c1+1, r2+1) - 1
d = cmb(r1+c1, r1) - 1
ans = a - b - c + d
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#F
from operator import mul
from functools import reduce

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

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def f(rr,cc):
    #(0,0)~(r,c)までのコンビネーションの累積和
    #print(rr+cc+2, cc+1)
    #print(combinations_count(rr+cc+2, cc+1))
    return combinations_count(rr+cc+2, cc+1) - 1

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

Submission status: Time Limit Exceeded

Solution code:
from math import factorial


m = 1000000007


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


def F(r, c):
    r += 1
    c += 1
    path = (factorial(r + c) % m) * pow(factorial(r) * factorial(c), m - 2, m) % m
    return path - 1


r1 -= 1
c1 -= 1

ans = F(r2, c2)
ans -= F(r1, c2)
ans -= F(r2, c1)
ans += F(r1, c1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#0<=i<r,0<=j<cで総和求めて引く
#chooseの+2でよい
mod = 10**9+7
def chs(a,b):
    a+=1;b+=1
    a+=b
    res = 1
    for i in range(a,a-b,-1):
        res *= i
        rev = pow(a-i+1,mod-2,mod)
        res *= rev
        res%=mod
    
    return res


r1,c1,r2,c2 = map(int, input().split( ))
r1 -=1;c1-=1
#print(chs(r2,c2),chs(r1,c2),chs(r2,c1),chs(r1,c1))
ans = chs(r2,c2)-chs(r1,c2)-chs(r2,c1)+chs(r1,c1)
ans%=mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#0<=i<r,0<=j<cで総和求めて引く
#chooseの+2でよい
mod = 10**9+7
def chs(a,b):
    a+=1;b+=1
    a+=b
    res = 1
    for i in range(a,a-b,-1):###
        res *= i
        rev = pow(a-i+1,mod-2,mod)
        res *= rev
        res%=mod
    
    return res


r1,c1,r2,c2 = map(int, input().split( ))
r1 -=1;c1-=1
#print(chs(r2,c2),chs(r1,c2),chs(r2,c1),chs(r1,c1))
ans = chs(r2,c2)-chs(r1,c2)-chs(r2,c1)+chs(r1,c1)
ans%=mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#0<=i<r,0<=j<cで総和求めて引く
#chooseの+2でよい
#10**6なのでpythonにしてみる
mod = 10**9+7
def chs(a,b):
    a+=1;b+=1
    a+=b
    res = 1
    for i in range(a,a-b,-1):
        res *= i 
        res%=mod
    for i in range(1,b+1):
        rev = pow(i,mod-2,mod)
        res *= rev 
        res %=mod 
    return res


r1,c1,r2,c2 = map(int, input().split( ))
r1 -=1;c1-=1
#print(chs(r2,c2),chs(r1,c2),chs(r2,c1),chs(r1,c1))
ans = chs(r2,c2)-chs(r1,c2)-chs(r2,c1)+chs(r1,c1)
ans%=mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#0<=i<r,0<=j<cで総和求めて引く
#chooseの+1でよい
mod = 10**9+7
def chs(a,b):
    a+=1;b+=1##+1?
    a+=b
    res = 1
    for i in range(a,a-b,-1):
        res *= i 
        res%=mod
    for i in range(1,b+1):
        rev = pow(i,mod-2,mod)
        res *= rev 
        res %=mod 
    return res


r1,c1,r2,c2 = map(int, input().split( ))
r1 -=1;c1-=1
#print(chs(r2,c2),chs(r1,c2),chs(r2,c1),chs(r1,c1))
ans = chs(r2,c2)-chs(r1,c2)-chs(r2,c1)+chs(r1,c1)
ans%=mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
t_p= []
t_rp = []

def g(r,c):
    ans = 0
    if r > c:
        r,c = c,r
    for i in range(r+1):
        ans += f(i+1,c)
        ans %= MOD
    return ans

def f(r,c):
    return (p(r+c) * rp(r) * rp(c)) % MOD

def p(n):
    if t_p[n] == 0:
        ans = 1
        for i in range(2,n+1):
            ans *= i
            ans %= MOD
        t_p[n] = ans
    return t_p[n]

def rp(n):
    if n == 0:
        return 1
    if t_rp[n] == 0:
        t_rp[n] = mod_inv(p(n), MOD)
    return t_rp[n]

def extgcd(a,b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2]//w[2]
        ra = w
        wa = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = ra
        w = wa
    #[x,y]
    return [w[0], w[1]]

def mod_inv(a,m):
    x = extgcd(a, m)[0]
    return (m+x%m)%m

r1,c1, r2,c2 = map(int,input().split())
t_p = [0 for _ in range(r2+c2+3)]
t_rp = [0 for _ in range(max(r2,c2)+2)]
ans = g(r2,c2) - g(r1-1,c2) - g(r2,c1-1) + g(r1-1,c1-1)
ans %= MOD
print (ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
t_p= []
t_rp = []

def g(r,c):
    ans = 0
    for i in range(r+1):
        ans += f(i+1,c)
        ans %= MOD
    return ans

def f(r,c):
    return (p(r+c) * rp(r) * rp(c)) % MOD

def p(n):
    if t_p[n] == 0:
        ans = 1
        for i in range(2,n+1):
            ans *= i
            ans %= MOD
        t_p[n] = ans
    return t_p[n]

def rp(n):
    if n == 0:
        return 1
    if t_rp[n] == 0:
        t_rp[n] = mod_inv(p(n), MOD)
    return t_rp[n]

def extgcd(a,b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2]//w[2]
        ra = w
        wa = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = ra
        w = wa
    #[x,y]
    return [w[0], w[1]]

def mod_inv(a,m):
    x = extgcd(a, m)[0]
    return (m+x%m)%m

r1,c1, r2,c2 = map(int,input().split())
t_p = [0 for _ in range(r2+c2+3)]
t_rp = [0 for _ in range(max(r2,c2)+2)]
ans = g(r2,c2) - g(r1-1,c2) - g(r2,c1-1) + g(r1-1,c1-1)
ans %= MOD
print (ans)

Submission status: Time Limit Exceeded

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,fact,factinv
    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]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

N = max(c2+r2+2,c1+r2,c1+r1+1,c2+r1+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(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: Time Limit Exceeded

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,fact,factinv
    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]  # 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: Time Limit Exceeded

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

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

Solution code:


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

Solution code:
r1, c1, r2, c2 = map(int, input().split())
mod = int(1e+9) + 7
def inved(x):
  a, b, c, d, k, l = 1, 0, 0, 1, x, mod
  while l != 0:
    a, b, c, d = c, d, a - c * (k // l), b - d * (k // l)
    k, l = l, k & l
  return a % mod
frac = [1]
for i in range(r2 + c2 + 2):
  frac.append(((i+1) * frac[i]) % mod)
fracr2c2 = frac[r2 + c2 + 2]
fracr1c2 = frac[r1 + c2 + 1]
fracr2c1 = frac[r2 + c1 + 1]
fracr1c1 = frac[r1 + c1]
fracr2 = frac[r2 + 1]
fracr1 = frac[r1]
fracc2 = frac[c2 + 1]
fracc1 = frac[c1]
g = 0
g += (fracr2c2 * inved(fracr2) * inved(fracc2)) % mod
g %= mod
g += (fracr1c1 * inved(fracr1) * inved(fracc1)) % mod
g %= mod
g -= (fracr1c2 * inved(fracr1) * inved(fracc2)) % mod
g %= mod
g -= (fracr2c1 * inved(fracr2) * inved(fracc1)) % mod
g %= mod
print(g)

Submission status: Time Limit Exceeded

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

Solution code:
import sys
import socket

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('f1.in')


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


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


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


def read_str():
    return input()


def g(r, s):
  res = 1
  f = 1
  for i in range(1, r+s+3):
    f *= i
    f %= M

  fs = 1
  for i in range(1, s+2):
    fs *= i
    fs %= M

  fr = 1
  for i in range(1, r+2):
    fr *= i
    fr %= M

  res *= pow(fr, M-2, M)
  res *= pow(fs, M-2, M)

  res *= f
  res %= M
  return res


M = 10 ** 9 + 7
def main():
    r1, c1, r2, c2 = read_int_list()
    res = 0
    res += g(r2, c2) - g(r2, c1-1) - g(r1-1, c2) + g(r1-1, c1-1)
    res %= M
    print(res)


main()

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

def comb(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
    
r1, c1, r2, c2 = [int(i) for i in input().split()]
 
def calc(r, c):
    a = comb(r + c + 2, r + 1) - 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))