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

Solution code:
def comb(n,m,p=10**9+7):
    if n < m : return 0
    if n < 0 or m < 0:return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p

def s(n,m):
    return comb(n+m+2, m+1, mod)

mod = 10**9+7

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

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

Submission status: Accepted

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


class Combination:
    def __init__(self, N: int, MOD: int):
        fac = [0 for _ in range(N + 1)]
        fac[0] = 1
        for i in range(1, N + 1):
            fac[i] = fac[i - 1] * i % MOD
        self.fac = fac
        self.N = N
        self.MOD = MOD

    def _modpow(self, x: int, n: int) -> int:
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * x % self.MOD
            x = x * x % self.MOD
            n >>= 1
        return ret

    def _modinv(self, x: int) -> int:
        return self._modpow(x, self.MOD - 2)

    def combination(self, n: int, k: int) -> int:
        if n < k:
            return 0
        return self.fac[n] * self._modinv(self.fac[k]) % self.MOD * self._modinv(self.fac[n - k]) % self.MOD

MOD = 1000000007
comb = Combination(2 * 1000000 + 10, MOD)

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

Submission status: Accepted

Solution code:
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

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

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

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

Submission status: Accepted

Solution code:
# F - Many Many Paths
def get_factorials(lim: int, MOD: int) -> list:
    """Compute a table of factorials (1-indexed)."""
    factorials = [1] * (lim + 1)
    x = 1
    for i in range(1, lim + 1):
        x = (x * i) % MOD
        factorials[i] = x
    return factorials


def mod_comb_with_pow(n: int, k: int, MOD: int) -> int:
    """Compute nCr % MOD using pow(), not an inverse factorial table."""
    return fact[n] * pow(fact[k], MOD - 2, MOD) * pow(fact[n - k], MOD - 2, MOD) % MOD


def main():
    global fact
    MOD = 10 ** 9 + 7
    R1, C1, R2, C2 = map(int, input().split())
    fact = get_factorials(2 * 10 ** 6 + 10, MOD)
    f = lambda x, y: mod_comb_with_pow(x, y, MOD)
    ans = (f(C1 + R1, R1) - f(C1 + R2 + 1, R2 + 1) - f(C2 + R1 + 1, R1) + f(C2 + R2 + 2, R2 + 1)) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[0]*(n+1)
  fac[0]=1
  for i in range(1,n+1):fac[i]=fac[i-1]*i%M
  pr1=pow(fac[r1],M-2,M)
  pc1=pow(fac[c1],M-2,M)
  pr2=pow(fac[r2+1],M-2,M)
  pc2=pow(fac[c2+1],M-2,M)
  a=fac[r2+c2+2]*pr2*pc2
  a-=fac[r2+c1+1]*pr2*pc1
  a-=fac[r1+c2+1]*pr1*pc2
  a+=fac[r1+c1]*pr1*pc1
  print(a%M)
main()

Submission status: Accepted

Solution code:
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[0]*(n+1)
  fac[0]=val=1
  for i in range(1,n+1):fac[i]=val=val*i%M
  pr1=pow(fac[r1],M-2,M)
  pc1=pow(fac[c1],M-2,M)
  pr2=pow(fac[r2+1],M-2,M)
  pc2=pow(fac[c2+1],M-2,M)
  print((fac[r2+c2+2]*pr2*pc2-fac[r2+c1+1]*pr2*pc1-fac[r1+c2+1]*pr1*pc2+fac[r1+c1]*pr1*pc1)%M)
main()

Submission status: Accepted

Solution code:
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[0]*(n+1)
  fac[0]=val=1
  for i in range(1,n+1):fac[i]=val=val*i%M
  pr1=pow(fac[r1],M-2,M)
  pc1=pow(fac[c1],M-2,M)
  pr2=pow(fac[r2+1],M-2,M)
  pc2=pow(fac[c2+1],M-2,M)
  a=fac[r2+c2+2]*pr2*pc2
  a-=fac[r2+c1+1]*pr2*pc1
  a-=fac[r1+c2+1]*pr1*pc2
  a+=fac[r1+c1]*pr1*pc1
  print(a%M)
main()

Submission status: Accepted

Solution code:
M=10**9+7
r1,c1,r2,c2=map(int,input().split())
n=r2+c2+2
fac=[0]*(n+1)
fac[0]=val=1
for i in range(1,n+1):fac[i]=val=val*i%M
pr1=pow(fac[r1],M-2,M)
pc1=pow(fac[c1],M-2,M)
pr2=pow(fac[r2+1],M-2,M)
pc2=pow(fac[c2+1],M-2,M)
a=fac[r2+c2+2]*pr2*pc2
a-=fac[r2+c1+1]*pr2*pc1
a-=fac[r1+c2+1]*pr1*pc2
a+=fac[r1+c1]*pr1*pc1
print(a%M)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7


def pow(a, b, mod):
    if b == 0:
        return 1
    if b == 1:
        return a
    if b % 2 == 0:
        return (pow(a, b // 2, mod) ** 2) % mod
    else:
        return (a * pow(a, b // 2, mod) ** 2) % mod


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


MAX = 2 * 10 ** 6 + 3
l = [1] * MAX
for i in range(1, MAX):
    l[i] = (l[i - 1] * i) % mod


def f(r, c):
    return (l[r + c] * inv(l[r], mod) * inv(l[c], mod)) % mod


def g(r, c):
    if r < 0 or c < 0:
        return 0
    ans = f(r+1, c+1) - 1 + mod
    return ans % mod


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

Submission status: Accepted

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

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

def func(r, c):
    if c == 0:
        return r + 1
    return comb(r + c + 2, c + 1, MOD)

def comb(n, r, mod):
    return (g1[n] * g2[r] * g2[n - r]) % mod

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

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

Submission status: Accepted

Solution code:
mod = 10**9+7
MAX_N = 20000000+5

fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1] = pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
    fact_inv[i] = fact_inv[i+1]*(i+1)%mod


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

x,p,y,q = map(int,input().split())
 
res = mod_comb_k(p+x,x,mod) - mod_comb_k(p+y+1,y+1,mod) - mod_comb_k(q+x+1,x,mod) + mod_comb_k(q+y+2,y+1,mod)
print(res%mod)

Submission status: Accepted

Solution code:
mod=1000000007
fact=[1 for i in range(3000000)]
for i in range(1,3000000):
    fact[i]=(fact[i-1]*i)%mod

def inv(a):
    a%=mod
    b=mod
    u=0
    v=1
    while a!=0:
        t=b//a
        b-=t*a
        a,b=b,a
        u-=t*v
        u,v=v,u
    if u<0:
        u+=mod
    return u

def c(n,r):
    return (fact[n]*inv(fact[n-r])*inv(fact[r]))%mod

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

Submission status: Accepted

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

M = r2+c2+10#1000010
mod = 10**9+7

f    = [1]*M
p = 1
for i in range(1, M):
    p = p*i%mod
    f[i] = p
    #finv[i] = pow(p, mod-2, mod)

finv = [1]*M
p = finv[-1] = pow(f[-1], mod-2, mod)
for i in range(M-2, 0, -1):
    p = p*(i+1)%mod
    finv[i] = p

g = [0]*M
p = 0
for i in range(1, M):
  g[i] = p = ((p+1)*2-1)%mod

def comb(n, k):
    return f[n] * finv[n-k] * finv[k] % mod

def count(R,C):
    ret = g[R+C+1] % mod

    for c in range(C):
        x1 = comb(R+c, c)
        x2 = g[C-c]
        ret = (ret-x1*x2) % mod

    for r in range(R):
        x1 = comb(C+r, r)
        x2 = g[R-r]
        ret = (ret-x1*x2) % mod

    return ret

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
def main():
  import sys
  M=10**9+7
  r1,c1,r2,c2=map(int,sys.stdin.buffer.readline().split())
  n=r2+c2+2
  val=1
  fac=[val]
  append=fac.append
  for i in range(1,n+1):
    val=val*i%M
    append(val)
  pr1=pow(fac[r1],M-2,M)
  pc1=pow(fac[c1],M-2,M)
  pr2=pow(fac[r2+1],M-2,M)
  pc2=pow(fac[c2+1],M-2,M)
  print((fac[r2+c2+2]*pr2*pc2-fac[r2+c1+1]*pr2*pc1-fac[r1+c2+1]*pr1*pc2+fac[r1+c1]*pr1*pc1)%M)
main()

Submission status: Accepted

Solution code:
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  val=1
  fac=[val]
  append=fac.append
  for i in range(1,n+1):
    val=val*i%M
    append(val)
  pr1=pow(fac[r1],M-2,M)
  pc1=pow(fac[c1],M-2,M)
  pr2=pow(fac[r2+1],M-2,M)
  pc2=pow(fac[c2+1],M-2,M)
  a=fac[r2+c2+2]*pr2*pc2
  a-=fac[r2+c1+1]*pr2*pc1
  a-=fac[r1+c2+1]*pr1*pc2
  a+=fac[r1+c1]*pr1*pc1
  print(a%M)
main()

Submission status: Accepted

Solution code:
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[1]
  val=1
  append=fac.append
  for i in range(1,n+1):
    val=val*i%M
    append(val)
  f=lambda r,c:fac[r+c+2]*pow(fac[c+1],M-2,M)*pow(fac[r+1],M-2,M)-c-r-2
  print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%M)
main()

Submission status: Accepted

Solution code:
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[0]*(n+1)
  fac[0]=val=1
  for i in range(1,n+1):fac[i]=val=val*i%M
  f=lambda r,c:fac[r+c+2]*pow(fac[c+1],M-2,M)*pow(fac[r+1],M-2,M)-c-r-2
  print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%M)
main()

Submission status: Accepted

Solution code:
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[0]*(n+1)
  fac[0]=before=1
  for i in range(1,n+1):fac[i]=before=before*i%M
  f=lambda r,c:fac[r+c+2]*pow(fac[c+1],M-2,M)*pow(fac[r+1],M-2,M)-c-r-2
  print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%M)
main()

Submission status: Accepted

Solution code:
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[0]*(n+1)
  fac[0]=1
  for i in range(1,n+1):fac[i]=fac[i-1]*i%M
  f=lambda r,c:fac[r+c+2]*pow(fac[c+1],M-2,M)*pow(fac[r+1],M-2,M)-c-r-2
  print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%M)
main()

Submission status: Accepted

Solution code:
def main():
  M=10**9+7
  r1,c1,r2,c2=map(int,input().split())
  n=r2+c2+2
  fac=[1]+[0]*n
  for i in range(1,n+1):fac[i]=fac[i-1]*i%M
  f=lambda r,c:fac[r+c+2]*pow(fac[c+1],M-2,M)*pow(fac[r+1],M-2,M)-c-r-2
  print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%M)
main()

Submission status: Accepted

Solution code:
def main():
  M=10**9+7
  a,b,c,d=map(int,input().split())
  n=c+d+2
  fac=[0]*(n+1)
  fac[0]=lt=1
  for i in range(1,n+1):fac[i]=lt=lt*i%M
  inv=lambda n:pow(fac[n],M-2,M)
  f=lambda r,c:fac[r+c+2]*inv(c+1)*inv(r+1)-c-r-2
  print((f(c,d)-f(c,b-1)-f(a-1,d)+f(a-1,b-1))%M)
main()

Submission status: Accepted

Solution code:
def main():
  M=10**9+7
  a,b,c,d=map(int,input().split())
  n=c+d+2
  fac=[0]*(n+1)
  fac[0]=lt=1
  for i in range(1,n+1):fac[i]=lt=lt*i%M
  inv=[0]*(n+1)
  inv[n]=lt=pow(fac[n],M-2,M)
  for i in range(n,0,-1):inv[i-1]=lt=lt*i%M
  comb=lambda n,k:fac[n]*inv[n-k]*inv[k]
  f=lambda r,c:fac[r+c+2]*inv[c+1]*inv[r+1]-c-r-2
  print((f(c,d)-f(c,b-1)-f(a-1,d)+f(a-1,b-1))%M)
main()

Submission status: Accepted

Solution code:
class Factorial:
    def __init__(self,n,mod):
        self.f=f=[0]*(n+1)
        f[0]=b=1
        self.mod=mod
        for i in range(1,n+1):f[i]=b=b*i%mod
        self.inv=inv=[0]*(n+1)
        inv[n]=b=pow(self.f[n],mod-2,mod)
        for i in range(n,0,-1):inv[i-1]=b=b*i%mod
    def factorial(self,i):
        return self.f[i]
    def ifactorial(self,i):
        return self.inv[i]
    def comb(self,n,k):
        if n>=k:
            return self.f[n]*self.inv[n-k]%self.mod*self.inv[k]%self.mod
        else:
            return 0
M=10**9+7
a,b,c,d=map(int,input().split())
comb=Factorial(c+d+2,M).comb
f=lambda r,c:comb(c+r+2,r+1)-c-r-2
print((f(c,d)-f(c,b-1)-f(a-1,d)+f(a-1,b-1))%M)

Submission status: Accepted

Solution code:
class Factorial:
    def __init__(self,n,mod):
        self.f=[1]
        self.mod=mod
        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 comb(self,n,k):
        return self.f[n]*self.i[n-k]%self.mod*self.i[k]%self.mod if n>=k else 0
M=10**9+7
a,b,c,d=map(int,input().split())
comb=Factorial(c+d+2,M).comb
f=lambda r,c:comb(c+r+2,r+1)-c-r-2
print((f(c,d)-f(c,b-1)-f(a-1,d)+f(a-1,b-1))%M)

Submission status: Accepted

Solution code:
class Factorial:
    def __init__(self,n,mod):
        self.f=f=[0]*(n+1)
        f[0]=b=1
        self.mod=mod
        for i in range(1,n+1):f[i]=b=b*i%mod
        self.inv=inv=[0]*(n+1)
        inv[0]=b=pow(self.f[n],mod-2,mod)
        for i in range(1,n+1):inv[i]=b=b*(n+1-i)%mod
        self.inv.reverse()
    def factorial(self,i):
        return self.f[i]
    def ifactorial(self,i):
        return self.inv[i]
    def comb(self,n,k):
        return self.f[n]*self.inv[n-k]%self.mod*self.inv[k]%self.mod if n>=k else 0
M=10**9+7
a,b,c,d=map(int,input().split())
comb=Factorial(c+d+2,M).comb
f=lambda r,c:comb(c+r+2,r+1)-c-r-2
print((f(c,d)-f(c,b-1)-f(a-1,d)+f(a-1,b-1))%M)

Submission status: Accepted

Solution code:
MOD = 10**9+7

fact = [1]*(2*10**6+10)
for i in range(1, len(fact)):
    fact[i] = (fact[i-1]*i)%MOD

def comb(n, k):
    return fact[n]*pow(fact[n-k], MOD-2, MOD)*pow(fact[k], MOD-2, MOD)

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

r1, c1, r2, c2 = list(map(int, input().split()))
print((path(r2, c2)-path(r1-1, c2)-path(r2, c1-1)+path(r1-1, c1-1))%(10**9+7))

Submission status: Accepted

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

p = 10 ** 9 + 7
size = 1010000 * 2
f_list = [1] * size
for i in range(1, size):
    f_list[i] = (f_list[i - 1] * i) % p

def cmb(n, r):
    return f_list[n + r] * pow(f_list[n], p-2, p) * pow(f_list[r], p-2, p) % p

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

MOD = 10**9+7
MAXN = r2+c2+5
fac = [1,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD

def inv(n):
    return pow(n,MOD-2,MOD)

def comb(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * inv(fac[r]) * inv(fac[n-r]) % MOD

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

Submission status: Accepted

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

fac = [1]
for i in range(1, r2 + c2 + 10) :
  fac.append(fac[-1] * i % mod)
inv = [pow(fac[-1], mod - 2, mod)]
for i in range(r2 + c2 + 9, 0, -1) :
  inv.append(inv[-1] * i % mod)
inv = inv[::-1]

def comb(n, r) :
  return fac[n] * inv[n-r] * inv[r] % mod

def g(x, y) :
  return comb(x + y, y)

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

print(ret)

Submission status: Accepted

Solution code:
MOD = 10**9+7


def make_combination_table(n):
    fact = [1]
    for i in range(1, n+1):
        fact.append(fact[i-1] * i % MOD)

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


def mod_combination(n, r, table):
    if r > n:
        return 0
    return table[0][n] * table[1][n - r] * table[1][r] % MOD


def sum_rect(r, c, table):
    return (mod_combination(r+c+2, r+1, table)-1) % MOD


def main():
    r1, c1, r2, c2 = map(int, input().split())
    table = make_combination_table((r2+c2+2))
    r1 -= 1
    c1 -= 1

    ans = sum_rect(r2, c2, table)
    ans %= MOD
    ans -= sum_rect(r2, c1, table)
    ans %= MOD
    ans -= sum_rect(r1, c2, table)
    ans %= MOD
    ans += sum_rect(r1, c1, table)
    ans %= MOD
    print(ans)


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[求めたいもの]
Σ(r1<=i<=r2)Σ(c1<=j<=c2) f(i,j)

g(R,C) := Σ(0<=i<=R)Σ(0<=j<=C)f(i,j) とすると
ans = g(r2,c2) - g(r2,c1-1) - g(r1-1,c2) + g(r1-1,c1-1)

[性質(パスカルの三角形)]
・f(r+1,c) = f(r,c) + f(r,c-1) + ... + f(r,0)
・g(R,C) = Σ(0<=i<=R)f(i+1,C)
       = f(R+1,C+1) - 1

g(r2,c2) = f(r2+1+c2+1,r2+1) - 1
g(r2,c1-1) = f(r2+1+c1,r2+1) - 1
g(r1-1,c2) = f(r1+c2+1,c2+1) - 1
g(r1-1,c1-1) = f(r1+c1,r1) - 1
"""
def nCr(n,r):
    return fact[n]*pow(fact[n-r],mod-2,mod)*pow(fact[r],mod-2,mod) % mod

r1,c1,r2,c2 = LI()

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def nCr(n,r):
    return fact[n]*pow(fact[n-r],mod-2,mod)*pow(fact[r],mod-2,mod) % mod

r1,c1,r2,c2 = LI()

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

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

Submission status: Accepted

Solution code:
NN = 2020202
MOD = 10**9+7
INF = float("inf")

f = [0]*NN
rf = [0]*NN
inv = [0]*NN
f[0], f[1] = 1, 1
rf[0], rf[1] = 1, 1
inv[1] = 1

for i in range(2, NN):
    f[i] = (f[i-1] * i) % MOD
    inv[i] = (-inv[MOD % i] * (MOD // i)) % MOD
    rf[i] = (rf[i-1] * inv[i]) % MOD


def C(n, r):
    # if r < 0 or n < r:
    #     return 0
    # r = min(r, n - r)
    return (f[n] * rf[r] * rf[n-r]) % MOD


r1, c1, r2, c2 = map(int, input().split())
ans = 0
for r in range(r1+1, r2+2):
    ans += (C(c2+r, r) - C(c1+r-1, r)) % MOD
    # print(ans)
print(ans % MOD)

Submission status: Accepted

Solution code:
NN = 2020202
MOD = 10**9+7
INF = float("inf")

f = [0]*NN
rf = [0]*NN
inv = [0]*NN
f[0], f[1] = 1, 1
rf[0], rf[1] = 1, 1
inv[1] = 1

for i in range(2, NN):
    f[i] = (f[i-1] * i) % MOD
    inv[i] = (-inv[MOD % i] * (MOD // i)) % MOD
    rf[i] = (rf[i-1] * inv[i]) % MOD


def C(n, r):
    # if r < 0 or n < r:
    #     return 0
    # r = min(r, n - r)
    return (f[n] * rf[r] * rf[n-r]) % MOD


r1, c1, r2, c2 = map(int, input().split())
ans = C(r2+c2+2, r2+1) - C(r1+c2+1, r1) - C(r2+c1+1, c1) + C(r1+c1, r1)
print(ans % MOD)

Submission status: Accepted

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

size = 1010000*2
f_list = [1]*(size)
for i in range(1,size):
    f_list[i] = (f_list[i-1]*i)%MOD

def func(r,c):
    return (f_list[r+c]*pow(f_list[r],MOD-2,MOD)*pow(f_list[c],MOD-2,MOD))

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

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

def inv(v, mod):
    return pow(v, mod-2, mod)
def main():
    r1, c1, r2, c2 = rip()

    MM = int(2e6+10)
    fact = [0] * MM
    finv = [0] * MM
    fact[0] = 1
    finv[0] = 1
    mod = int(1e9) + 7
    for i in range(1,MM): fact[i] = (fact[i-1] * i % mod)
    '''
    finv[MM-1] = inv(fact[MM-1], mod)
    for i in reversed(range(1,MM-1)):
        finv[i] = finv[i + 1] * (i + 1) % mod
    def sum_naive(r, c):
        #[0, r) * [0, c)
        ret = 0
        for i in range(r):
            ret += fact[i + 1 + c - 1] * finv[i + 1] * finv[c - 1] % mod
        return ret
    def sum(r, c):
        #[0, r) * [0, c)
        ret = fact[r + c] * finv[r] * finv[c] % mod
        ret += -1 + mod
        ret %= mod
        return ret
    '''
    def sum(r, c):
        #[0, r) * [0, c)
        ret = fact[r + c] * inv(fact[r], mod) * inv(fact[c], mod) % mod
        ret += -1 + mod
        ret %= mod
        return ret
    ans = 0
    ans += sum(r2 + 1, c2 + 1)
    ans -= sum(r2 + 1, c1)
    ans -= sum(r1, c2 + 1)
    ans += sum(r1, c1)
    ans %= mod
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

def inv(v, mod):
    return pow(v, mod-2, mod)
def main():
    r1, c1, r2, c2 = rip()

    MM = int(2e6+10)
    fact = [0] * MM
    finv = [0] * MM
    fact[0] = 1
    finv[0] = 1
    mod = int(1e9) + 7
    for i in range(1,MM): fact[i] = (fact[i-1] * i % mod)
    finv[MM-1] = inv(fact[MM-1], mod)
    for i in reversed(range(1,MM-1)):
        finv[i] = finv[i + 1] * (i + 1) % mod
    def sum_naive(r, c):
        #[0, r) * [0, c)
        ret = 0
        for i in range(r):
            ret += fact[i + 1 + c - 1] * finv[i + 1] * finv[c - 1] % mod
        return ret
    def sum(r, c):
        #[0, r) * [0, c)
        ret = fact[r + c] * finv[r] * finv[c] % mod
        ret += -1 + mod
        ret %= mod
        return ret

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



if __name__ == "__main__":
    main()

Submission status: Accepted

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


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

mod=10**9 + 7
fact=[1,1]
factinv=[1,1]
inv=[0,1]
N=r2+c2+3
mod=10**9+7
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)
    
#二次元累積和もどき，i,jのマスを考える，
a=cmb(r2+c2+2,r2+1,mod) 
b=cmb(r1+c2+1,r1,mod)
c=cmb(r2+c1+1,c1,mod)
d=cmb(r1+c1,r1,mod)
ans=a-b-c+d
print(ans%mod)

Submission status: Accepted

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

MOD = 10**9+7
MAXN = 2*10**6+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

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

Submission status: Accepted

Solution code:
def mod_inverse(n, mod=10**9+7):
    return pow(n, mod-2, mod)


def combination(n, k, mod=10**9+7):
    numer = denom = 1
    for i in range(k):
        numer = (numer * (n-i)) % mod
        denom = (denom * (i+1)) % mod
    return (numer * mod_inverse(denom, mod)) % mod


mod = 10**9+7
r1, c1, r2, c2 = map(int, input().split())
ans = combination(r1+c1, r1) - combination(1+r2+c1, 1+r2) - combination(1+r1+c2, r1) + combination(2+r2+c2, 1+r2)
print(ans % mod)

Submission status: Accepted

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

ans = 0

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

F = Factorial(r2 + c2 + 3, MOD)

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

print (ans % MOD)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = [1]
    r = 1
    for inv in mod_invs(max, mod)[1:]:
        r = r * inv % mod
        ret.append(r)
    return ret


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


R1, C1, R2, C2 = list(map(int, sys.stdin.buffer.readline().split()))

comb = Combination(max=10 ** 6 * 2 + 100, mod=MOD)


# 解説
# ある要素に注目して残りを選ぶ数を数えると分かる
# ncr(n, r) == ncr(n-1,r) + (n-1,r-1)
# nhr(n, r) == sum([nhr(n-1,k) for k in range(r)])

# g(r, c) を f(i, j) (0<=i<=r, 0<=j<=c) の総和とすると
# g(R2, C2) - g(R1-1, C2) - g(R2, C1-1) + g(R1-1, C1-1)

def f(n, r):
    return comb.ncr(n + r, r)


# @debug
def g(r, c):
    # ret = 0
    # for i in range(1, c + 2):
    #     ret += f(r, i)
    #     ret %= MOD

    # f(r,k) (k=[1,c+1]) の和
    return f(r + 1, c + 1) - f(r, 0)


ans = g(R2, C2) - g(R1 - 1, C2) - g(R2, C1 - 1) + g(R1 - 1, C1 - 1)
ans %= MOD
print(ans)