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

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

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

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

show_flg=False
show_flg=True
 
ans=0

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


cm=Comb(n*2)

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

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

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

print(ans%mo)

Submission status: Time Limit Exceeded

Solution code:
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
from scipy.special import comb
ans=0
for i in range(r1,r2+1):
  for j in range(c1,c2+1):
    ans+=comb(i+j,i,exact=True)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

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

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def comb(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

def g(x,y):
    return comb(x+y+2,y+1)-1

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

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

Submission status: Time Limit Exceeded

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

    MOD = 10**9+7
    n = r2+c2+1
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
      fac[i] = i*fac[i-1]%MOD
      rev[i] = pow(fac[i], MOD-2, MOD)
    
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

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

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

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

n = r2 + c2 + 3
mod = 10 ** 9 + 7
f = [1 for _ in range(n)]
f_inv = [1 for _ in range(n)]
for i in range(1, n):
    f[i] = f[i-1] * i % mod
    f_inv[i] = pow(f[i], mod-2, mod)

def comb(n, k):
    return f[n] * f_inv[k] * f_inv[n-k] % mod
def g(r, c):
    return comb(r+c+2, c+1) - 1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def inv(x):
    return pow(x, mod - 2, mod)

def main():
    r1,c1,r2,c2 = LI()

    r = 0
    t1 = 1
    u1 = c2 + 1
    t2 = 1
    u2 = c1
    for i in range(1, r2+2):
        t1 *= u1
        t1 %= mod
        u1 += 1
        ii = inv(i)
        t1 *= ii
        t1 %= mod
        t2 *= u2
        t2 %= mod
        u2 += 1
        t2 *= ii
        t2 %= mod
        if i > r1:
            r += t1 - t2
            r %= mod

    return r

print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def inv(x):
    return pow(x, mod - 2, mod)

cms = 10**6 * 2 + 5
cm = [0] * cms

def comb_init():
    cm[0] = 1
    for i in range(1, cms):
        cm[i] = cm[i-1] * i % mod

def comb(a, b):
    return (cm[a] * inv(cm[a-b]) % mod) * inv(cm[b]) % mod

def main():
    r1,c1,r2,c2 = LI()
    comb_init()

    r = 0
    for i in range(r1+1, r2+2):
        r += comb(i+c2, c2)
        r -= comb(i+c1-1, c1-1)
        r %= mod

    return r

print(main())

Submission status: Time Limit Exceeded

Solution code:
def COMinit(n,MOD):
    #MODは素数, n < MOD, n <= 10**7
    #計算量:O(n)
    #fac[i]:i!の MOD, inv[i]:MODにおけるiの逆元, finv[i]:(i!)^(-1)のMOD
    fac = [0]*(n+1)
    finv = [0]*(n+1)
    inv = [0]*(n+1)
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2,n+1):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = -inv[MOD%i] * (MOD//i) % MOD
        finv[i] = finv[i-1] * inv[i] %MOD
    return fac, finv, inv

r1,c1,r2,c2 = map(int,input().split())
MOD = 10**9+7
fac, finv, inv = COMinit(r2+c2+2,MOD)

def com(r, c):
        ans = fac[r + c] * finv[r] * finv[c]
        return ans % MOD
 
def g(r, c):
    return (com(r + 1, c + 1) - 1) % MOD

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

Submission status: Time Limit Exceeded

Solution code:
def COMinit(n,MOD):
    #MODは素数, n < MOD, n <= 10**7
    #計算量:O(n)
    #fac[i]:i!の MOD, inv[i]:MODにおけるiの逆元, finv[i]:(i!)^(-1)のMOD
    fac = [0]*(n+1)
    finv = [0]*(n+1)
    inv = [0]*(n+1)
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2,n+1):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = -inv[MOD%i] * (MOD//i) % MOD
        finv[i] = finv[i-1] * inv[i] %MOD
    return fac, finv, inv

r1,c1,r2,c2 = map(int,input().split())
MOD = 10**9+7
fac, finv, inv = COMinit(2 * 10 ** 6 + 3,MOD)

def com(r, c):
        ans = fac[r + c] * finv[r] * finv[c]
        return ans % MOD
 
def g(r, c):
    return (com(r + 1, c + 1) - 1) % MOD

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

Submission status: Time Limit Exceeded

Solution code:
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def nCr(self, n, r):
        r = min(n - r, r)
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def nHr(self, n, r):
        return self.nCr(n - 1 + r, r)


def main():
    MOD = 10 ** 9 + 7

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

    cl = Calc(max_value=r2 + c2 + 1, mod=MOD)
    nCr = cl.nCr

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def nCr(self, n, r):
        r = min(n - r, r)
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        return ((self.fact[n] * self.invs[r]) % self.mod) * self.invs[n - r] % self.mod

    def nHr(self, n, r):
        return self.nCr(n - 1 + r, r)


def main():
    MOD = 10 ** 9 + 7

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

    cl = Calc(max_value=r2 + c2 + 1, mod=MOD)
    nCr = cl.nCr

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def nCr(self, n, r):
        r = min(n - r, r)
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def nHr(self, n, r):
        return self.nCr(n - 1 + r, r)


def main():
    MOD = 10 ** 9 + 7

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

    cl = Calc(max_value=r2 + c2 + 1, mod=MOD)
    nCr = cl.nCr

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
def comb_mod(n,r,mod):
    ans = 1
    for i in range(r):
        ans *= n-i
        ans %= mod
    for i in range(1,r+1):
        ans *= pow(i,mod-2,mod)
        ans %= mod
    return ans

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

ans = comb_mod(C+D+2,C+1,mod)-comb_mod(B+C+1,B,mod)-comb_mod(A+D+1,A,mod)+comb_mod(A+B,A,mod)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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

C = Factorial(2 * 10 ** 6 + 5, MOD).comb

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

ans = 0
for i in range(c2 - c1 + 1):
    tmp = C(r2 + c2 + 1 - i, r2) - C(r1 + c2 - i, r1 - 1)
    # print (tmp, C(r2 + c2 + 1 - i, r2), C(r1 + c2 - i, r1 - 1))

    ans += tmp
    ans %= MOD

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

def main():
  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] 
  g2 = [1, 1] 
  inverse = [0, 1]
  for i in range( 2, r2+c2+1):
      g1.append( ( g1[-1] * i ) % mod )
      inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
      g2.append( (g2[-1] * inverse[-1]) % mod )
  ans=0
  for r in range(r1,r2+1):
    for c in range(c1,c2+1):
      ans+=cmb(r+c,r,mod)
      ans%=mod
  print(ans)

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
N = 2 * 10 ** 6 + 10

fac = [0] * N
finv = [0] * N
inv = [0] * N

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, N):
    fac[i] = fac[i - 1] * i % mod
    # mod pにおける1, 2, ..., nの逆元
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def com(n, k):
    global fac, finv, mod
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod

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

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

answer = g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)
answer %= mod
print(answer)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
N = 2 * 10 ** 6

fac = [0] * N
finv = [0] * N
inv = [0] * N

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, N):
    fac[i] = fac[i - 1] * i % mod
    # mod pにおける1, 2, ..., nの逆元
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def com(n, k):
    global fac, finv, mod
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


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

for r in range(r1, r2 + 1):
    for c in range(c1, c2 + 1):
        answer += com(r + c, c)
        answer %= mod
print(answer)

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

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

r1,c1,r2,c2 = map(int, input().split())
ans = cmb(r2+c2+2,c2+1,mod)-cmb(r2+c1+1,c1,mod)-cmb(r1+c2+1,c2+1,mod)+cmb(r1+c1,c1,mod)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    r1, c1, r2, c2 = map(int, read().split())
    mod = 10 ** 9 + 7

    def generate_inv(n, mod):
        """
        逆元行列
        n >= 2
        Note: mod must bwe a prime number
        """
        ret = [0, 1]
        for i in range(2, n + 1):
            next = -ret[mod % i] * (mod // i)
            next %= mod
            ret.append(next)
        return ret

    inv = generate_inv(2 * 10 ** 6, mod)

    def comb_mod2(n, a, mod):
        """
        return: [n, a] % mod
        Note: mod must be a prime number
        """
        if a == 0 or n == 0:
            return 1
        ret = 1
        for i in range(1, a + 1):
            ret *= n - i + 1
            ret %= mod
            ret *= inv[i]
            ret %= mod
        return ret


    def calc(i,j):
        ret = 0
        agg = comb_mod2(j, 0, mod)
        for k in range(1, i+2):
            agg *= (j+k)%mod
            agg *= inv[k]
            agg %= mod
            ret += agg
        return ret


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

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:


class ModInt:

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

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

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

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

mod = 1000000007

modint = ModInt(mod)


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


def F(r, c):
    ret = 0
    for i in range(c + 1):
        ret += r_sum(r, i)
    return ret % mod



r_from, c_from, r_to, c_to = map(int, input().split())

ans = F(r_to, c_to)
ans -= F(r_to, c_from - 1)
ans -= F(r_from - 1, c_to)
ans += F(r_from - 1, c_from - 1)
ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:


class ModInt:

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

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

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

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

mod = 1000000007

modint = ModInt(mod)


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


def F(r, c):
    ret = 0
    for i in range(c + 1):
        ret += r_sum(r, i)
    return ret % mod



r_from, c_from, r_to, c_to = map(int, input().split())

ans = F(r_to, c_to)
ans -= F(r_to, c_from - 1)
ans -= F(r_from - 1, c_to)
ans += F(r_from - 1, c_from - 1)
ans %= mod

print(ans)

Submission status: Time Limit Exceeded

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

MOD=10**9+7

def comb(n, r): 
    if r<0 or r>n: 
        return 0
    r=min(r, n-r)
    res=1
    for i in range(r): 
        res=res*(n-i)%MOD*pow(i+1, MOD-2, MOD)%MOD
    return res

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

print(ans%MOD)

Submission status: Time Limit Exceeded

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

import numpy as np
graph = [[1]*(r2+1) for _ in range(c2+1)]
graph = np.array(graph)

for i in range(1, c2+1):
    graph[i][1:] = (graph[0][:-1] + np.cumsum(graph[i-1][1:]))%mod

cum_graph = (np.cumsum(np.cumsum(graph, axis=0), axis=1))%mod

print((cum_graph[c2][r2]-cum_graph[c1-1][r2]-cum_graph[c2][r1-1]+cum_graph[c1-1][r1-1])%mod)

Submission status: Time Limit Exceeded

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

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

mod = 10**9+7 #出力の制限
N = 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 )

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

Submission status: Time Limit Exceeded

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

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

mod = 10**9+7 #出力の制限
N = 10**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 )

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

Submission status: Time Limit Exceeded

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

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

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

    return mod_c

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

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

ans = 0

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

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

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

ans = 0

for c in range(c1, c2 + 1):
    ans += comb.ncr(r2 + c + 1, c + 1) - comb.ncr(r1 + c, c + 1)

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:

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


def kai(x):
    return kai_[x]


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


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


def s(r, c):
    a = 0
    for i in range(1, r + 1):
        a += comb(i + c + 1, c)
        a %= p
    return a


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

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
r1,c1,r2,c2 = map(int,readline().split())
mod = 10**9+7
def pow(n,p,mod=10**9+7): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod
def factrial_memo(n=20**6+1,mod=10**9+7):
    fact = [1, 1]
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % mod)
    return fact
def fermat_cmb(n, r, mod=10**9+7): #needs pow,factrial_memo(only fact). return nCk
    return fact[n] * pow(fact[r],mod-2) * pow(fact[n-r],mod-2) %mod
fact = factrial_memo()
r1,c1,r2,c2 = r1+1,c1+1,r2+1,c2+1
al = fermat_cmb(r2+c2,r2)
sub_r = fermat_cmb(r1-1+c2,r1-1)
sub_c = fermat_cmb(r2+c1-1,c1-1)
add_rc = fermat_cmb(r1-1+c1-1,r1-1)

al -= sub_r+sub_c
al += add_rc

print(al%mod)

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