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: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

a1,b1,a2,b2=map(int,input().split())
print(comb(a2+b2+2,a2+1)-comb(a2+b1+1,a2+1)-comb(a1+b2+1,a1)+comb(a1+b1,a1))

Submission status: Wrong Answer

Solution code:

class Combination:
    def __init__(self, n_max, mod=10 ** 9 + 7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max + 1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod - 2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    # "n 要素" は区別できる n 要素
    # "k グループ" はちょうど k グループ

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

    def nCr(self, n, r):
        if not 0 <= r <= n:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

def resolve():
    def f(r, c):
        return cmb.nCr(r+c+2, r+1) - 1

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

    cmb = Combination(r2+c2+5)
    ans = f(r2, c2)
    ans -= f(r1, c2)
    ans -= f(r2, c1)
    ans += f(r1, c1)
    print(ans)
    
if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
def comb(n,k,mod):
  if n<k:
    return 0
  if n-k<k:
    k=n-k
  c=1
  for x in range(n-k+1,n+1):
    c=(c*x)%mod
  d=1
  for x in range(1,k+1):
    d=(d*x)%mod
  c=c*pow(d,mod-2,mod)
  return c%mod
def f(i,j):
  return comb(i+j,i,mod)
ans=f(r2+1,c2+1)-f(r2+1,c1+1)-f(r1+1,c2+1)+f(r1+1,c1+1)
ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
def comb(n,k,mod):
  if n<k:
    return 0
  if n-k<k:
    k=n-k
  c=1
  for x in range(n-k+1,n+1):
    c=(c*x)%mod
  d=1
  for x in range(1,k+1):
    d=(d*x)%mod
  c=c*pow(d,mod-2,mod)
  return c%mod
def f(i,j):
  return comb(i+j,i,mod)
ans=f(r2+1,c2+1)-f(r2+1,c1)-f(r1,c2+1)+f(r1,r2)
ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
def comb(n,k,mod):
  if n<k:
    return 0
  if n-k<k:
    k=n-k
  c=1
  for x in range(n-k+1,n+1):
    c=(c*x)%mod
  d=1
  for x in range(1,k+1):
    d=(d*x)%mod
  c=c*pow(d,mod-2,mod)
  return c%mod
def f(i,j):
  return comb(i+j,i,mod)
ans=f(r2+1,c2+1)-f(r2+1,c1+1)-f(r1+1,c2+1)+f(r1+1,r2+1)
ans%=mod
print(ans)

Submission status: Wrong Answer

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

MOD = 10**9+7
n = r2+c2
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

w = r2 - r1
h = c2 - c1
X, Y = 0, 0
ans = comb(c1+r1, r1)
for i in range(c1+1, c2+1):
    ans += comb(i+r1, r1)
    X += (h-(i-(c1+1)))*comb(i+r1, r1)
for i in range(r1+1, r2+1):
    ans += comb(i+c1, c1)
    Y += (w-(i-(r1+1)))*comb(i+c1, c1)
ans += w*X+h*Y
ans %= MOD
print(ans)

Submission status: Wrong Answer

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

def p_mod(m,n,p):
    a = 1
    for i in range(n):
        a = a*(m-i) % p
    return a

def c_mod(m,n,p):
    return (p_mod(m,n,p)*pow(p_mod(n,n,p),p-2,p)) % p

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    r,c,rr,cc=map(int,input().split())
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,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]=MOD-inv[MOD%i]*(MOD//i)%MOD
            finv[i]=finv[i-1]*inv[i]%MOD
        return fac,finv,inv
    
    fac,finv,inv=COMinit(rr+cc+10,MOD)
    
    def COM(n, k, MOD=MOD):
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    
    ans=COM(rr+cc+2,rr+1)-COM(rr+c+1,c)-COM(r+cc+1,r)+COM(r+c,r)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
FACT_MAX = 2 * 10 ** 6 + 3
fact = [1] * FACT_MAX
for i in range(1, FACT_MAX):
    fact[i] = fact[i - 1] * i % MOD
def comb(n, r):
    return fact[n] * pow(fact[n - r], MOD - 2, MOD) * pow(fact[r], MOD - 2, MOD)
def g(r, c):
    return (comb(r + c + 2, c + 1) - 1) % 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))

Submission status: Wrong Answer

Solution code:
def g(r, c):
    ret = 0
    for i in range(1, r + 2):
        ret += fact[i + c] * fact_inv[i] * fact_inv[c]
        ret %= mod

    return ret


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

mod = 10 ** 9 + 7
MAX = 2 * 10 ** 6 + 10

fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact[i] = (fact[i-1] * i) % mod

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod

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

Submission status: Wrong Answer

Solution code:
def findTrailingZeros(n): 

      

    # If n is odd 

    if (n & 1): 

        return 0

  

    # If n is even 

    else: 

        ans = 0

  

        # Find the trailing zeros 

        # in n/2 factorial 

        n //= 2

        while (n): 

            ans += n // 5

            n //= 5

  

        # Return the required answer 

        return ans 

  
# Driver code 

  

n = 12

  

print(findTrailingZeros(n))

Submission status: Wrong Answer

Solution code:
nmax = (10**6+1)*2
mod = 10**9+7

fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    for i in range(2,nmax):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - 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

def g(r,c):## r以下かつc以下の経路f(i,j)の総和
    ans = 0
    for i in range(1,r+2):
        ## f(i+1,c) =  f(i,0) + f(i,1) + ...f(i,c)
        ans += ncr(i+c,c)
        ans %=mod
    return ans

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

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

Submission status: Wrong Answer

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

def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1

    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD

    print(comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

def combinations_count(n, r):
    return math.factorial(n + r) // (math.factorial(n) * math.factorial(r))

r1, c1, r2, c2 = map(int, input().split())
ans = combinations_count(r2, c2) 
ans -= combinations_count(r1, c2)
ans -= combinations_count(r2, c1)
ans += combinations_count(r1, r2)
ans = ans % (1000000007)
print(ans)

Submission status: Wrong Answer

Solution code:
import math

def combinations_count(n, r):
    return math.factorial(n + r) // (math.factorial(n) * math.factorial(r))

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

Submission status: Wrong Answer

Solution code:
import math

def combinations_count(n, r):
    return math.factorial(n + r) // (math.factorial(n) * math.factorial(r))

r1, c1, r2, c2 = map(int, input().split())
ans = combinations_count(r2, c2)
ans -= combinations_count(r1, c2)
ans -= combinations_count(r2, c1)
ans += combinations_count(r1, r2)
print(ans)

Submission status: Wrong Answer

Solution code:
import math

def combinations_count(n, r):
    return math.factorial(n + r) // (math.factorial(n) * math.factorial(r))

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

Submission status: Wrong Answer

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) % L)

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

  Euc = (get_euclidian(L, (F[r] * F[n - r]) % L) + L) % L
  return ((F[n] * 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: Wrong Answer

Solution code:
mod = 10**9 + 7

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

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

fac = [1]
for i in range(1, r2 + c2 + 3):
  fac.append(fac[i - 1] * i % mod)

def paths(r, c):
  return fac[r + c + 2] * inv(fac[r + 1] * fac[c + 1]) % mod

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

Submission status: Wrong Answer

Solution code:
r1, c1, r2, c2 = map(int, input().split())
L = 10 ** 9 + 7
  
# 組み合わせ計算
def get_combi (n, k):

  r = k if k > n - k else n - k
  s = n - r
  M = [0] * (s + 1)
  N = 1
  for i in range(n, r, -1):
    for j in range(2, s + 1):
      if M[j] == 0 and i % j == 0:
        i = i / j
        M[j] = 1
    N *= i
    N = N % L

  return (N)

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 (combi1 - combi2 - combi3 + combi4)

Submission status: Wrong Answer

Solution code:
r1, c1, r2, c2 = map(int, input().split())
L = 10 ** 9 + 7
  
# 組み合わせ計算
def get_combi (n, k):

  r = k if k > n - k else n - k
  s = n - r
  M = [0] * (s + 1)
  N = 1
  for i in range(n, r, -1):
    for j in range(2, s + 1):
      if M[j] == 0 and i % j == 0:
        i = i / j
        M[j] = 1
    N *= i
    N = N % L

  return (N)

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 (combi1)
print (combi2)
print (combi3)
print (combi4)
print (combi1 - combi2 - combi3 + combi4)

Submission status: Wrong Answer

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

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

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

a = list(map(int,input().split()))
ans = cmb(a[2]+1,a[2]+a[3]+2,p) - cmb(a[1],a[2]+a[1]+1,p) - cmb(a[0],a[3]+a[0]+1,p) + cmb(a[0],a[0]+a[1],p)
print(ans)

Submission status: Wrong Answer

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)
# brute forceであり、TLEする。


MAX = 10 ** 6 * 2 + 5
def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv

fac, finv = com_init(MAX, mod)

def nCr(n,r):
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod 

def myfunc(r, c):
    return nCr(r + c + 2, r + 1) - 1


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

# The result is the same as the below, but much faster.
# def nCr(n, r):
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

Submission status: Wrong Answer

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)
# brute forceであり、TLEする。


# mod and MAX should be given
mod = 10 ** 9 + 7
MAX = 10 ** 6 * 2 + 5
print(MAX)
def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv

fac, finv = com_init(MAX, mod)

def nCr(n,r):
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod 

def myfunc(r, c):
    return nCr(r + c + 2, r + 1) - 1


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

# The result is the same as the below, but much faster.
# def nCr(n, r):
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

Submission status: Wrong Answer

Solution code:
r1, c1, r2, c2 = map(int, input().split())
ans = 0
for i in range(r1, r2 + 1):
  for j in range(c1, c2 + 1):
    ans += i * j
    
print( ans % 1000000007)

Submission status: Wrong Answer

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

mod = 10**9+7

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):
  res = factorial(x+y)
  res = res*pow(factorial(x), mod-2, mod)%mod
  res = res*pow(factorial(y), mod-2, mod)%mod
  return res-1

def factorial(p):
  res = 1
  for i in range(1,p+1):
    res = res*i%mod
  return res



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

Submission status: Wrong Answer

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

mod = 10**9+7

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):
  res = factorial(x+y)
  res = res*pow(factorial(x), mod-2, mod)%mod
  res = res*pow(factorial(y), mod-2, mod)%mod
  return res

def factorial(p):
  res = 1
  for i in range(1,p+1):
    res = res*i%mod
  return res



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

Submission status: Wrong Answer

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**6 * 2 + 3 # ここでRE出しまくってた。。。
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: Wrong Answer

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

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


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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
r1,c1,r2,c2=map(int,input().split())
MOD=10**9+7
idx=r2+c2+3
perm=[1]*(idx+1)
for i in range(1,idx+1):
    perm[i]=perm[i-1]*i
    perm[i]%=MOD
def inv_mod(a):
  return pow(a,MOD-2,MOD)
def comb(i,j):
    buf=perm[i+j+2]
    buf*=inv_mod(perm[i+1])
    buf%=MOD
    buf*=inv_mod(perm[j+1])
    buf%=MOD
    return buf
res=comb(r2,c2)
res-=comb(r2,c1-1)
res-=comb(r1-1,c2)
res+=comb(r1-1,c1-1)
print(res)

Submission status: Wrong Answer

Solution code:
m = 1000000007


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

nf = 10 ** 6 * 2 + 100
fact = [0] * (nf + 1)
fact[0] = 1
for i in range(nf):
    fact[i + 1] = fact[i] * (i + 1) % m


def F(r, c):
    path = (fact[r + c + 2] % m) * pow(fact[r + 1] * fact[c + 1], 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: Wrong Answer

Solution code:
r1,c1,r2,c2=map(int,input().split())
MOD=10**9+7
idx=r2+c2+2
perm=[1]*(idx+1)
perm_inv=[1]*(idx+1)
for i in range(1,idx+1):
    perm[i]=perm[i-1]*i
    perm[i]%=MOD
def inv_mod(a):
  return pow(a,MOD-2,MOD)
perm_inv[-1]=inv_mod(perm[-1])
for i in range(idx-1,-1,-1):
    perm_inv[i]=perm_inv[i+1]*(i+1)
    perm_inv[i]%=MOD
def comb(i,j):
    buf=perm[i+j+2]
    buf*=perm_inv[i+1]
    buf%=MOD
    buf*=perm_inv[j+1]
    buf%=MOD
    return buf
res=comb(r2,c2)
res-=comb(r2,c1-1)
res-=comb(r1-1,c2)
res+=comb(r1-1,c1-1)
print(res)

Submission status: Wrong Answer

Solution code:
m = 1000000007


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

nf = 10 ** 6 * 2 + 100
fact = [0] * (nf + 1)
fact[0] = 1
for i in range(nf):
    fact[i + 1] = fact[i] * (i + 1) % m


def F(r, c):
    r += 1
    c += 1
    path = (fact[r + c] % m) * pow(fact[r] * fact[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: Wrong Answer

Solution code:

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



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



directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count


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

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

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

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

    return numerator // denominator


r1,c1,r2,c2=acinput()

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

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

Submission status: Wrong Answer

Solution code:

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



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



directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count


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])
            #print(result)
            result %= (10**9+7)

    return result

r1,c1,r2,c2=acinput()

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

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

Submission status: Wrong Answer

Solution code:
import sys
import socket

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


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


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


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


def read_str():
    return input()

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

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

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


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


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


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import socket

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


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


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


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


def read_str():
    return input()

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

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


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


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)


r1, c1, r2, c2 = map(int, input().split())
MOD = 1e9 + 7
score = [0]
database = [[0 for i in range(c2+1)] for j in range(r2+1)]


def dp(x, y):
    if database[x][y]:
        return database[x][y]
    if not any((x, y)):
        return 0
    if x == 0:
        return 1
    if y == 0:
        return 1
    r = (dp(x - 1, y) + dp(x, y - 1)) % MOD
    database[x][y] = r
    if r1 <= x <= r2 and c1 <= y <= c2:
        score[0] = (score[0] + r) % MOD
        # print(x, y, r)
    return r


dp(r2, c2)
print(score[0])

Submission status: Wrong Answer

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: Wrong Answer

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 r == c == 0:
        return 1
    if r == 0:
        return c + 1
    if c == 0:
        return r + 1
    return comb(r + c + 2, r + 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: Wrong Answer

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):
    return comb(r + c + 2, r + 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))