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:
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
    else:
        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:
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+1))
    r1 -= 1
    c1 -= 1

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


main()

Submission status: Wrong Answer

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 -= sum_rect(r2, c1, table)
    ans -= sum_rect(r1, c2, table)
    ans += sum_rect(r1, c1, table)
    print(ans)


main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def MI(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [LI() for _ in range(N)]
        return map(list, zip(*read_all))

#################

#0!~(n-1)!をmodしつつ求める
def fact_all(n,M=mod):
    f = [1]*n
    ans = 1
    for i in range(1,n):
        ans = ans*i
        ans = ans%M
        f[i] = ans
    return f


#a!をmodしつつ求める
def fact(a,M=mod):
    ans = 1
    for i in range(2,a+1):
        ans = ans*i
        ans = ans%M
    return ans


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


#aの逆元(mod M)を求める（aとMは互いに素）
def mod_inv(a,M=mod):
    x = extgcd(a,M)[0]
    return (M+x%M)%M


#nCkをmodしつつ返す
def nCk(n,k,fact_list=[],inv_list=[],M=mod):
    if fact_list and inv_list:
        return (fact_list[n]*inv_list[k]*inv_list[n-k])%M
    else:
        x = fact(n,M)
        y1 = mod_inv(fact(k,M),M)
        y2 = mod_inv(fact(n-k,M),M)
        return (x*y1*y2)%M


def g(r,c):
    retval = 0
    for i in range(r+1):
        retval += nCk(i+c+1,c,fact_list,inv_list)
        retval %= mod
    return retval

r1,c1,r2,c2 = LI()
fact_list = fact_all(r2+c2+2)
inv_list = [mod_inv(f) for f in fact_list]

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

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7

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

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

total = fact[r2 + c2 + 2] * inv_fact[r2 + 1] * inv_fact[c2 + 1] % mod
total -= fact[r1 + c2 + 1] * inv_fact[r1] * inv_fact[c2 + 1] % mod
total -= fact[r2 + c1 + 1] * inv_fact[c1] * inv_fact[r2 + 1] % mod
total += fact[r1 + c1] * inv_fact[r1] * inv_fact[c1] % mod

print(total)

Submission status: Wrong Answer

Solution code:
def comb(n, r):
    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
MAXN=2000000+10
g1=[1, 1]
g2=[1, 1]
inverse=[0, 1]

for i in range(2, MAXN+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())
s1=comb(r2+c2+2, r2+1)
s2=comb(r1+c2+1, r1)
s3=comb(r2+c1+1, r2+1)
s4=comb(r1+c1, r1)
print(s1-s2-s3+s4)

Submission status: Wrong Answer

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

class factorial:
  def __init__(self, n, p=10**9 + 7):
    self.__p  = p
    self.__fac  = [0] * (n+1)
    self.__inv  = [0] * (n+1)
    self.__finv = [0] * (n+1)

    self.__fac[0] = self.__fac[1] = 1
    self.__inv[1] = 1
    self.__finv[0] = self.__finv[1] = 1

    for i in range(2, n+1):
      self.__fac[i] = self.__fac[i-1] * i % p
      self.__inv[i] = p - self.__inv[p%i] * (p // i) % p
      self.__finv[i] = self.__finv[i-1] * self.__inv[i] % p
  
  def fact(self, n):
    return self.__fac[n]
  
  def perm(self, n, k):
    return self.__fac[n] * self.__finv[n-k] % self.__p
  
  def comb(self, n, k):
    return self.perm(n, k) * self.__finv[k] % self.__p

f = factorial(r2+c2+2)
print(f.comb(r2+c2+2, r2+1) + f.comb(r1+c1, r1) - f.comb(r1+c2+1, r1) - f.comb(c1+r2+1, c1))

Submission status: Wrong Answer

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

    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 = 3*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)

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

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def cmb(n, k):
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

r1, c1, r2, c2 = lr()
MOD = 10 ** 9 + 7
U = 10 ** 7
fact, fact_inv = make_fact(U,MOD)

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

# 16

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 = 6*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())

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

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 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 = 5*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())

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

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 solve():
    r1, c1, r2, c2 = map(int, input().split())
    
    # Combination calculation
    p = 10 ** 9 + 7
    N = r2 + c2 + 2
    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 comb(n, r):
        return fact[n] * factinv[r] * factinv[n - r] % p
    
    def f(i, j):
        return comb(i + j, i)
    
    def g(i, j):
        return f(i + 1, j + 1) - 1
    
    ans = g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)
    
    print(ans)

solve()

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
rng = 2000100
fctr = [1]+[0]*(rng-1)

for i in range(1,rng):
  fctr[i] = fctr[i-1]*i%mod

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
rng = 2000100
fctr = [1]+[0]*(rng-1)
finv = [1]+[0]*(rng-1)
for i in range(1,rng):
  fctr[i] = fctr[-1]*i%mod
for i in range(1,rng):
  finv[i] = pow(fctr[i],mod-2,mod)
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod

x1,y1,x2,y2 = map(int,input().split())
print((cmb(x2+y2+2,x2+1)-cmb(x2+y1+1,y1)-cmb(x1+y2+1,x1)+cmb(x1+y1,x1))%mod)

Submission status: Wrong Answer

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

    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 = 3*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)

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from math import factorial
mod = 10**9 + 7
r1, c1, r2, c2 = map(int, input().split())
def comb(r, c):
    return factorial(r+c) // (factorial(r) * factorial(c))
if r2 - r1 < c2 - c1:
    l = [comb(r1, c1)]
    ans = l[0]
    for r in range(r1+1, r2+1):
        l.append((l[-1] * (r+c1) // (r)) % mod)
    for c in range(c1+1, c2+1):
        l.append((l[-1] * (r2+c) // c) % mod)
    cnt = 1
    for i in range(r2-r1+1):
        ans += l[i] * cnt
        ans %= mod
        cnt += 1
    c_cnt = 1
    for i in range(r2 - r1, c2 - c1 + r2 - r1+1):
        if c_cnt > (c2 - c1) - (r2 - r1):
            cnt -= 1
        else:
            cnt += 1
        ans += l[i] * cnt
        ans %= mod
else:
    # rのがでかい
    t = 0
    l = [comb(r1, c1)%mod]
    for c in range(c1+1, c2+1):
        l.append((l[-1] * (r1+c) // c) % mod)
    for r in range(r1+1, r2+1):
        l.append((l[-1] * (r+c2) // r) % mod)
    ans = 0
    cnt = 1
    for i in range(c2-c1):
        # print("cnt", cnt)
        ans += l[i] * cnt
        ans %= mod
        cnt += 1
        t += 1
    # print("ans", ans)
    # print("cnt", cnt)
    # print("t", t)
    for i in range(t, len(l)-(c2-c1)-1):
        ans += l[i] * cnt
        ans %= mod
        t += 1
    # print("t", t)
    # print("ans", ans)
    # print("cnt", cnt)
    for i in range(t, len(l)):
        ans += l[i] * cnt
        ans %= mod
        cnt -= 1
        t += 1
print(ans % mod)
# print((r2 - r1) - (c2 - c1))
# print(t)
# print(len(l))

Submission status: Wrong Answer

Solution code:
n = 1000000007

def comb(p,q):
    r = 1
    for i in range(q):
        r = r * (p-i) // (1+i)
    return r%n
    
    
r1,c1,r2,c2 = list(map(int,input().split()))


y = comb(r2+c2+2,c2+c1) - comb(r2+c1+1,c1) - comb(r1+c2+1,c2+1) + comb(r1+c1,c1)
print(y % n)

Submission status: Wrong Answer

Solution code:
import math
def comb(p,q):
    return math.factorial(p)//math.factorial(q)//math.factorial(p-q)
    
r1,c1,r2,c2 = list(map(int,input().split()))

n = 1000000007
y = comb(r2+c2+2,c2+c1) - comb(r2+c1+1,c1) - comb(r1+c2+1,c2+1) + comb(r1+c1,c1)
print(y % n)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
N = 2 * 10 ** 6 + 2
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)


def f(r, c):
    if r == 0 or c == 0:
        return 0
    tmp = g1[r + c + 2] * g2[r + 1] * g2[c + 1] % mod
    return (tmp - (r + c + 2)) % mod


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

Submission status: Wrong Answer

Solution code:


from functools import reduce
import operator
MOD = 10**9+7


# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


# mを法とするaの乗法的逆元
def modinv(a, m=MOD):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


product = lambda it: reduce(lambda x,y:(x*y)%MOD,it,1)
comb = lambda n, k: product(range(n-k+1,n+1))*modinv(product(range(1,k+1)), MOD)

R1,C1,R2,C2 = map(int,input().split())


if R2-R1 > C2-C1:
    R1,C1,R2,C2 = C1,R1,C2,R2

T = R1+C1

P = comb(R1+C1,R1)%MOD
# print(P)
y = P
x = P
temp = P
s = P

for i in range(1,R2-R1+1):
    x0,y0 = x,y
    y *= (T+i)*modinv(R1+i)
    x *= (T+i)*modinv(C1+i)
    y %= MOD
    x %= MOD
    temp = 2*temp + x + y - x0 - y0
    temp %= MOD
    # print('x',x,y,temp)
    s += temp
    s %= MOD

for i in range(R2-R1+1,C2-C1+1):
    x0,y0 = x,y
    y *= (T+i)*modinv(R1+i)
    x *= (T+i)*modinv(R1+i-(R2-R1))
    y %= MOD
    x %= MOD
    temp = 2*temp + y - x0 - y0
    temp %= MOD
    # print('y',x,y,temp)
    s += temp
    s %= MOD


for i in range(C2-C1+1, R2+C2-C1-R1+1):
    x0,y0 = x,y
    y *= (T+i)*modinv(C1+i-(C2-C1))
    x *= (T+i)*modinv(R1+i-(R2-R1))
    y %= MOD
    x %= MOD
    temp = 2*temp - x0 - y0
    temp %= MOD
    # print('z',x,y,temp)
    s += temp
    s %= MOD

print(s)

Submission status: Wrong Answer

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

mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod

def F(r,c):
  ans=0
  for i in range(r+c+1):
    ans+=pow(2,i,mod)
    ans%=mod
  '''
  d=0
  s=0
  for i in range(r-1,-1,-1):
    s+=comb((r-i-1)+c,c)
    d+=pow(2,i,mod)*s
    s%=mod
    d%=mod
  ans=(ans+(mod-d))%mod
  d=0
  s=0
  for i in range(c-1,-1,-1):
    s+=comb((c-i-1)+r,r)
    d+=pow(2,i,mod)*s
    s%=mod
    d%=mod
  ans=(ans+(mod-d))%mod
  '''
  return ans

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

Submission status: Wrong Answer

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

mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod

def F(r,c):
  ans=0
  for i in range(r+c+1):
    ans+=pow(2,i,mod)
    ans%=mod
  d=0
  s=0
  for i in range(r-1,-1,-1):
    s+=comb((r-i-1)+c,c)
    d+=pow(2,i,mod)*s
    s%=mod
    d%=mod
  ans=(ans+(mod-d))%mod
  d=0
  s=0
  for i in range(c-1,-1,-1):
    s+=comb((c-i-1)+r,r)
    d+=pow(2,i,mod)*s
    s%=mod
    d%=mod
  ans=(ans+(mod-d))%mod
  return ans

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

Submission status: Wrong Answer

Solution code:
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
n_max=2*(10**6+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
Inv=[0]*(n_max+1)
Inv[1]=1
for i in range(2,n_max):
  Inv[i]=pow(i,mod-2,mod)


for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=(FI[i]*Inv[i+1])%mod
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

Submission status: Wrong Answer

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def f(r,c):
    d = c
    prod = 1
    div = 1
    divacc = 1
    for i in range(r-1):
        prod = (prod*d)%R
        divacc = (divacc*div)%R
        d += 1
        div += 1
    ret = (prod*modinv2(divacc,R))%R
    #ddprint("f r {} c {} ret {}".format(r,c,ret))
    return ret

r1,c1,r2,c2 = inm()
r1 += 1
c1 += 1
r2 += 1
c2 += 1
print(f(r2+1,c2+1)-f(r2+1,c1)-f(r1,c2+1)+f(r1,c1))

Submission status: Wrong Answer

Solution code:
r1, c1, r2, c2 = map(int,input().split())
def comb(n,k):
    p=10**9+7
    from math import factorial
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    a=factorial(n) %p
    b=factorial(k) %p
    c=factorial(n-k) %p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p

def doubleComb(n,m):
    # x+y C x x=1 to n
    return (m+2)*comb(m+n+2, n)/(n+1) - 1

def func(r1,c1,r2,c2):
    return doubleComb(r2,c2) - doubleComb(r1-1,c2) - doubleComb(r2,c1-1) + doubleComb(r1-1,c1-1)
ans = func(r1, c1, r2, c2)
print(ans)

Submission status: Wrong Answer

Solution code:
# r1, c1, r2, c2 = map(int,input().split())
def comb(n,k):
    p=10**9+7
    from math import factorial
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    a=factorial(n) %p
    b=factorial(k) %p
    c=factorial(n-k) %p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p

def doubleComb(n,m):
    # x+y C x x=1 to n
    return (m+2)*comb(m+n+2, n)/(n+1) - 1

def func(r1,c1,r2,c2):
    return doubleComb(r2,c2) - doubleComb(r1-1,c2) - doubleComb(r2,c1-1) + doubleComb(r1-1,c1-1)
r1, c1, r2, c2 = 1,1,2,2
ans = func(r1, c1, r2, c2)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial as f
def co(n,r):
  if n<r:
    return 0
  else:
    return f(n)//(f(n-r)*f(r))
a,b,c,d=map(int,input().split())
m=10**9+7
print(co(c-a+d-b,c-a)%m)

Submission status: Wrong Answer

Solution code:
nnnnn = 3000001
P = 10**9+7

fa = [1]
for i in range(1, nnnnn):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, nnnnn)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]


CC = lambda a, b: fa[a+b] * fainv[a] * fainv[b] % P

r1, c1, r2, c2 = map(int, input().split())
s = CC(r1, c1)
ans = s
for i in range(r2+c2-r1-c1+1):
    s *= 2
    if r1+i+1 <= r2:
        s += CC(r1+i+1, c1-1)
    else:
        s += CC(r2+1, c1+r1+i-1-c2)
        s -= CC(r2+1, c1+r1+i-c2)
    if c1+i+1 <= c2:
        s += CC(c1+i+1, r1-1)
    else:
        s += CC(c2+1, r1+c1+i-1-r2)
        s -= CC(c2+1, r1+c1+i-r2)
    ans = (ans + s) % P

print(ans)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

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


[r1,c1,r2,c2]=[int(x) for x in input().split()]
YY=1000000000+7

a=combinations_count(r1+c1, r1)
X=[combinations_count(c1+x, x) for x in range(r1+1, r2+1)]
Y=[combinations_count(r1+x, x) for x in range(c1+1, c2+1)]
KX=[x*(c2-c1)*(r2-x+1) for x in range(r1+1, r2+1)]
KY=[x*(r2-r1)*(c2-x+1) for x in range(c1+1, c2+1)]
NX=len(X)
NY=len(Y)
ans=a%YY
for i in range(NX):
    ans+=X[i]*KX[i]%YY
for i in range(NY):
    ans+=Y[i]*KY[i]%YY
print (ans%YY)

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
#from scipy.special import comb
"""
nCr_dict = {}
def combination(n, r):
    try:
        nCr_dict[(n-1, r)]
    except KeyError:
        nCr_dict[(n-1, r)] = comb(n-1, r, exact=True)
    else:
        pass
    pass
    try:
        nCr_dict[(n-1, r-1)]
    except KeyError:
        nCr_dict[(n-1, r-1)] = comb(n-1, r-1, exact=True)
    else:
        pass
    nCr_dict[(n, r)] = nCr_dict[(n-1, r)] + nCr_dict[(n-1, r-1)]
    return nCr_dict[(n, r)]
"""
r1, c1, r2, c2 = map(int, input().split())
x = r2-r1+1
y = c2-c1+1

s1 = 0
s2 = 0
for j in range(c1, c2+1):
    s1 += comb(r1+j, r1)
for i in range(r1+1, r2+1):
    s2 += comb(i+c1-1, c1-1)
answer = s1*x+s2*y

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

Submission status: Wrong Answer

Solution code:
import math
def combi(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
mod = 10**9 + 7
r1,c1,r2,c2 = map(int,input().split())
#x0,y0からx1,y1への経路数の和をdpで求める
dp = [[ 0 for _ in range(r2+1)] for _ in range(c2+1)]
dp[0][0] = combi(r1+c1,min(r1,c1))
hasi = combi(r1+c1-2,min(r1-1,c1-1))
#print(dp)
for i in range(c2-c1+1):
    for j in range(r2-r1+1):
        if i == 0 and j == 0:continue
        if i >= 1 and j >= 1:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        elif i >= 1:
            dp[i][j] = dp[i-1][j] + hasi
        else:
            dp[i][j] = dp[i][j-1] + hasi
    #print(dp)
ans = 0
for i in range(len(dp)):
    ans += sum(dp[i])%mod
print(ans%mod)

Submission status: Wrong Answer

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



def modpow(a,n,md):
    res = 1
    while True:
        if n <=0:
            break
        if (n & 1):
            res = res * a % md
        a = a * a %md
        n >>= 1
    return res

def modinv (a, md):
    return modpow(a,md -2, md)






def jun(r,c):
    

    d = r + c
    ans = 1
    for i in range(c):
        ans *= d
        ans %= m
        d -= 1

    ans2 = 1
    while True:
        if c == 1:
            break
        ans2 *= c
        ans2 %= m
        c -=1

    return ans  * modinv(ans2, m)

ans = 0

#r1,c1
ans += jun(r1, c1) %m
#r1,c2
ans += jun(r1, c2) %m
#r2,c1
ans += jun(r2, c1) %m
#r2,c2
ans += jun(r2, c2) %m


print(ans%m)

Submission status: Wrong Answer

Solution code:
r1, c1, r2, c2 = map(int,input().split())
def comb(n,k):
    p=10**9+7
    from math import factorial
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    a=factorial(n) %p
    b=factorial(k) %p
    c=factorial(n-k) %p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p

def doubleComb(n,m):
    # x+y C x x=1 to n
    return (m+2)*comb(m+n+2, n)/(n+1) - 1

def func(r1,c1,r2,c2):
    return doubleComb(r2,c2) - doubleComb(r1,c2) - doubleComb(r2,c1) + doubleComb(r1,c1)
    # r1, c1, r2, c2 = 1,1,2,2
ans = func(r1, c1, r2, c2)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

r1, c1, r2, c2 = map(int, input().split(" "))
val = 10 ** 9 + 7
tate = np.array([1 for _ in range(r2 - 1)])
yoko = np.array([1 for _ in range(c2 - 1)])
ans = 0
for st in range(1, max(c2, r2)):
    tate_base, yoko_base = tate[0], yoko[0]

    tate = np.cumsum(tate) + yoko_base
    tate = np.mod(tate, val)

    yoko = np.cumsum(yoko) + tate_base
    yoko = np.mod(yoko, val)
    if st >= c1 and st >= r1:
        ans += tate_base + yoko_base
    if len(tate) > 1:
        if st >= c1:
            ans += np.sum(tate[max(1, r1 - st + 1) :]) % val
        tate = tate[1:]

    if len(yoko) > 1:
        if st >= r1:
            ans += np.sum(yoko[max(1, c1 - st + 1) :]) % val
        yoko = yoko[1:]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

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

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

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

for j in range(c1,c2+1):
    ans+=cmb(i+r1-1,i)*cmb(c2-i+1+r2-r1+1,r2-r1+1)

ans%=1000000007
ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
nnnnn = 3000001
P = 10**9+7

fa = [1]
for i in range(1, nnnnn):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, nnnnn)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]

print(fa[:20])
print(fainv[:20])

CC = lambda a, b: fa[a+b] * fainv[a] * fainv[b] % P

r1, c1, r2, c2 = map(int, input().split())
s = CC(r1, c1)
ans = s
for i in range(r2+c2-r1-c1+1):
    s *= 2
    if r1+i+1 <= r2:
        s += CC(r1+i+1, c1-1)
    else:
        s += CC(r2+1, c1+r1+i-1-c2)
        s -= CC(r2+1, c1+r1+i-c2)
    if c1+i+1 <= c2:
        s += CC(c1+i+1, r1-1)
    else:
        s += CC(c2+1, r1+c1+i-1-r2)
        s -= CC(c2+1, r1+c1+i-r2)
    ans = (ans + s) % P

print(ans)

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
Q = 10**9+7
def getInv(N):#Qはmod
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

# def getFactorialInv(N):
#     inv = [0] * (N + 1)
#     inv[0] = 1
#     inv[1] = 1
#     ret = [1]*(N+1)
#     for i in range(2, N + 1):
#         inv[i] = (-(Q // i) * inv[Q%i]) % Q
#         ret[i] = ret[i-1]*inv[i]
#     return ret

def getFactorial(N):
    ret = [1]*(N+1)
    for i in range(2,N+1):
        ret[i] = ret[i-1]*i%Q
    return ret

def main():
    r1, c1, r2, c2 = map( int, input().split())
    F = getFactorial(2*(10**6))
    J = getInv(2*(10**6))
    I = [0]*(10**6+1)
    I[0] = 1
    I[1] = 1
    for i in range(2,10**6+1):
        I[i] = I[i-1]*J[i]%Q
    #print(F[5]*I[5]%Q)
    a = 0
    b = 0
    c = 0
    d = 0
    for i in range(1, c2+1):
        a += F[r2+i+1]*I[i+1]%Q*I[r2]%Q-1
#        print(F[r2+i+1]*I[i+1]%Q*I[r2]%Q-1)
        a %= Q
    if r1 == 1:
        b = 0
    else:
        for i in range(1, c2+1):
            b += F[r1+i]*I[i]%Q*I[r1]%Q-1
            b %= Q
    if c1 == 1:
        c = 0
    else:
        for i in range(1, c1):
            c += F[r2+i+1]*I[i+1]%Q*I[r2]%Q-1
            c %= Q
    if c1 == 1 or r1 == 1:
        d = 0
    else:
        for i in range(1, c1):
            d += F[r1+i]*I[i]%Q*I[r1]%Q-1
            d %= Q
#    print(a, b,c, d)
    print((a-b-c+d)%Q)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

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


[r1,c1,r2,c2]=[int(x) for x in input().split()]
Y=1000000000+7

a=combinations_count(r1+c1, r1)
X=[combinations_count(c1+x, x) for x in range(r1+1, r2+1)]
Y=[combinations_count(r1+x, x) for x in range(c1+1, c2+1)]
KX=[x*(c2-c1)*(r2-x+1) for x in range(r1+1, r2+1)]
KY=[x*(r2-r1)*(c2-x+1) for x in range(c1+1, c2+1)]
NX=len(X)
NY=len(Y)
ans=a
for i in range(NX):
    ans+=X[i]*KX[i]
for i in range(NY):
    ans+=Y[i]*KY[i]
print (ans)

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
Q = 10**9+7
def getInv(N):#Qはmod
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

# def getFactorialInv(N):
#     inv = [0] * (N + 1)
#     inv[0] = 1
#     inv[1] = 1
#     ret = [1]*(N+1)
#     for i in range(2, N + 1):
#         inv[i] = (-(Q // i) * inv[Q%i]) % Q
#         ret[i] = ret[i-1]*inv[i]
#     return ret

def getFactorial(N):
    ret = [1]*(N+1)
    for i in range(2,N+1):
        ret[i] = ret[i-1]*i%Q
    return ret

def main():
    r1, c1, r2, c2 = map( int, input().split())
    F = getFactorial(2*(10**6))
    J = getInv(2*(10**6))
    I = [0]*(2*(10**6)+1)
    I[0] = 1
    I[1] = 1
    for i in range(2,2*(10**6)+1):
        I[i] = I[i-1]*J[i]%Q
    #print(F[5]*I[5]%Q)
    a = 0
    b = 0
    c = 0
    d = 0
    for i in range(1, c2+1):
        a += F[r2+i+1]*I[i+1]%Q*I[r2]%Q-1
#        print(F[r2+i+1]*I[i+1]%Q*I[r2]%Q-1)
        a %= Q
    if r1 == 1:
        b = 0
    else:
        for i in range(1, c2+1):
            b += F[r1+i]*I[i]%Q*I[r1]%Q-1
            b %= Q
    if c1 == 1:
        c = 0
    else:
        for i in range(1, c1):
            c += F[r2+i+1]*I[i+1]%Q*I[r2]%Q-1
            c %= Q
    if c1 == 1 or r1 == 1:
        d = 0
    else:
        for i in range(1, c1):
            d += F[r1+i]*I[i]%Q*I[r1]%Q-1
            d %= Q
#    print(a, b,c, d)
    print((a-b-c+d)%Q)
if __name__ == '__main__':
    main()