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: Runtime Error

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

al -= sub_r+sub_c
al += add_rc

print(al%mod)

Submission status: Runtime Error

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

al -= sub_r+sub_c
al += add_rc

print(al%mod)

Submission status: Runtime Error

Solution code:
r,c,R,C=map(int,input().split())
m=10**9+7
max_n=2*10**6
fac=[1]*(max_n+1)
inv=[1]*(max_n+1)
ifac=[1]*(max_n+1)
for n in range(2,max_n+1):
    fac[n]=(fac[n-1]*n)%m
    inv[n]=m-inv[m%n]*(m//n)%m
    ifac[n]=(ifac[n-1]*inv[n])%m
def comb(n,k):
    if n<k or n<0 or k<0:
        return 0
    return (fac[n]*ifac[k]*ifac[n-k])%m
def f(r,c):
    return sum([comb(i+1+c,c) for i in range(r+1)])%m
print((f(R,C)-f(R,c-1)-f(r-1,C)+f(r-1,c-1))%m)

Submission status: Runtime Error

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

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

        ret += tmp
        ret %= MOD

    return ret

def main():
    r1, c1, r2, c2 = getlist()
    # factorial = [1]
    # tmp = 1
    # t1 = time.time()
    # for i in range(1, r2 + c2 + 5):
    #     tmp *= i
    #     tmp %= MOD
    #     factorial.append(tmp)
    # print(time.time() - t1)
    # gyaku = [pow(i, MOD - 2, MOD) for i in factorial]
    # print(time.time() - t1)
    SIZE = 2 * 10 ** 6 + 10 ** 5
    SIZE = 10000
    MOD = 10 ** 9 + 7  # 998244353 #ここを変更する

    SIZE += 1
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
    factorial = fac
    gyaku = finv
    # print(time.time() - t1)
    # return
    # gyaku = [1 for i in range(2000000)]
    # print(routes_from_zero(r2, c2))
    # print(routes_from_zero(r1, c2))
    # print(routes_from_zero(r2, c1))
    # print(routes_from_zero(r1, c1))
    ans = routes_from_zero(r2, c2, factorial, gyaku) - routes_from_zero(r1 - 1, c2, factorial, gyaku)\
          - routes_from_zero(r2, c1 - 1, factorial, gyaku) + routes_from_zero(r1 - 1, c1 - 1, factorial, gyaku)
    print(ans % MOD)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;
 
#define rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;

ll gcd ( ll a, ll b ) { if ( b == 0 ) return a; else return gcd ( b, a%b ); }
ll lcm ( ll a, ll b ) { return a * b / gcd(a, b); }

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1e9+7;
struct mint {
  typedef long long ll;
  ll x;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  bool operator>(const mint a) const {
    mint res(*this);
    return res.x > a.x;
  }
  bool operator<(const mint a) const {
    mint res(*this);
    return res.x < a.x;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

constexpr int premax = 200020; 
std::array<mint, premax> f, rf; 
bool mymodflag = false;
mint nCk (int n, int k) {
  if ( n == k ) return mint(1);
  if ( n < k  ) return mint(0);
  if ( !mymodflag ) {
    f[0] = 1; for(int i=1; i<premax; i++) f[i] = f[i-1]*i;
    rf[premax-1] = f[premax-1].pow(mod-2); for(int i=premax-2; i>=0; i--) rf[i] = rf[i+1]*(i+1);
    mymodflag = true;
  }
  return f[n]*rf[n-k]*rf[k];
}

mint nPk (int n, int k) {
  if ( n < k  ) return mint(0);
  if ( !mymodflag ) {
    f[0] = 1; for(int i=1; i<premax; i++) f[i] = f[i-1]*i;
    rf[premax-1] = f[premax-1].pow(mod-2); for(int i=premax-2; i>=0; i--) rf[i] = rf[i+1]*(i+1);
    mymodflag = true;
  }
  return f[n]*rf[n-k];
}

mint func(int r, int c) {
  return nCk(r+c, r);
}

int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int r1, c1, r2, c2; std::cin >> r1 >> c1 >> r2 >> c2;

  mint ans = 0;
  for(int i=r1; i<=r2; i++) for(int j=c1; j<=c2; j++) ans += func(i,j);
  std::cout << ans.x << std::endl;
  return 0;
}

Submission status: Runtime Error

Solution code:

import numpy as np

def f (r, c, mod) :
    return cmb(r+c, r, mod)

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 = 10**4
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(np.int, input().split())
ans = 0
for i in range(r1, r2+1) :
    for j in range(c1, c2+1) :
        ans += f(i,j,mod) 
        ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
import sys

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

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

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

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))

class BigCombination(object):

    def __init__(self, mod: int=10**9+7, max_n: int=10**6):
        fac, inv=[1], []
        fac_append, inv_append=fac.append, inv.append

        for i in range(1, max_n+1):
            fac_append(fac[-1] * i % mod)

        inv_append(pow(fac[-1], mod-2, mod))

        for i in range(max_n, 0, -1):
            inv_append(inv[-1] * i % mod)

        self.mod, self.factorial, self.inverse=mod, fac, inv[::-1]

    def get_combination(self, n, r):
        if n < r:
            return 0
        return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod

    def get_permutation(self, n, r):
        if n < r:
            return 0
        return self.factorial[n] * self.inverse[n-r] % self.mod

def main():
    R1,C1,R2,C2 = MI()
    ans = ModInt(0)
    B = BigCombination()
    for r in range(R1,R2+1):
        ans += B.get_combination(C2+r+1,C2) - B.get_combination(C1-1+r+1,C1-1)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
p = 10 ** 9 + 7 # mod
N = (10 ** 6) + 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: Runtime Error

Solution code:
r1,c1,r2,c2 = map(int,input().split())
n = [[1]*(c2+1) for i in range(r2+1)]
mod = 10**9 + 7
ans = 0
for r in range(r2):
    for c in range(c2):
        n[r+1][c+1] = (n[r][c+1] + n[r+1][c])%mod
        if r >= r1-1 and c >= c1-1:
            ans += n[r+1][c+1]
            ans %= mod
            
print(ans)

Submission status: Runtime Error

Solution code:
mod = 10**9+7


def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
        x,y = w[0],w[1]    # a*x+y*mod = 1
        return (mod+x%mod)%mod

max_num = 2*10**5+1
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

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

ifact[max_num-1] = inv(fact[max_num-1],mod)

for i in range(2,max_num):
    ifact[max_num-i] = (ifact[max_num-i+1] * (max_num-i+2)) %mod

def comb(x,y):
    return fact[x] * ifact[y] * ifact[x-y] % mod


def solve(r, c):
    ans = 0
    for i in range(r+1):
        ans += comb(c+i+1, c)
        ans %= mod
    return ans


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

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

print(ans)

Submission status: Runtime Error

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 + 1

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: Runtime Error

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 + 1

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: Runtime Error

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

def C(a, b, MOD):
  return f(m, MOD) // (f(n, MOD) * f(m - n, MOD)) % MOD

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

Submission status: Runtime Error

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

def C(a, b, MOD):
  return f(m, MOD) // (f(n, MOD) * f(m - n, MOD)) % MOD

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

Submission status: Runtime Error

Solution code:
import sys
from itertools import product
from collections import defaultdict
read = sys.stdin.read
sys.setrecursionlimit(1000000)

r1, c1, r2, c2 = map(int, read().split())
mod = 10 ** 9 + 7
dic = defaultdict(lambda: 1)


def count(r, c):
    if r * c == 0:
        return 1
    if (r - 1, c) in dic:
        a = dic[(r - 1, c)]
    else:
        a = dic[(r - 1, c)] = count(r - 1, c) % mod
    if (r, c - 1) in dic:
        b = dic[(r, c - 1)]
    else:
        b = dic[(r, c - 1)] = count(r, c - 1) % mod
    return (a + b) % mod


dic[(r1 - 1, c2)] = count(r1 - 1, c2)
dic[(r2, c1 - 1)] = count(r2, c1 - 1)
res = 0
for r, c in product(range(r1, r2 + 1), range(c1, c2 + 1)):
    tmp = dic[(r, c)] = dic[(r - 1, c)] + dic[(r, c - 1)]
    res += tmp % mod
print(res % mod)

Submission status: Runtime Error

Solution code:
import sys
from itertools import product
from collections import defaultdict
read = sys.stdin.read
sys.setrecursionlimit(1000000)

r1, c1, r2, c2 = map(int, read().split())
mod = 10 ** 9 + 7
dic = {}


def count(r, c):
    if r * c == 0:
        return 1
    if (r - 1, c) in dic:
        a = dic[(r - 1, c)]
    else:
        a = dic[(r - 1, c)] = count(r - 1, c) % mod
    if (r, c - 1) in dic:
        b = dic[(r, c - 1)]
    else:
        b = dic[(r, c - 1)] = count(r, c - 1) % mod
    return (a + b) % mod


dic[(r1 - 1, c2)] = count(r1 - 1, c2)
dic[(r2, c1 - 1)] = count(r2, c1 - 1)
res = 0
for r, c in product(range(r1, r2 + 1), range(c1, c2 + 1)):
    tmp = dic[(r, c)] = dic[(r - 1, c)] + dic[(r, c - 1)]
    res += tmp % mod
print(res % mod)

Submission status: Runtime Error

Solution code:
import sys
from itertools import product
read = sys.stdin.read
sys.setrecursionlimit(1000000)

r1, c1, r2, c2 = map(int, read().split())
mod = 10 ** 9 + 7
dic = {}


def count(r, c):
    if r * c == 0:
        return 1
    if (r - 1, c) in dic:
        a = dic[(r - 1, c)]
    else:
        a = dic[(r - 1, c)] = count(r - 1, c) % mod
    if (r, c - 1) in dic:
        b = dic[(r, c - 1)]
    else:
        b = dic[(r, c - 1)] = count(r, c - 1) % mod
    return (a + b) % mod


dic[(r1 - 1, c2)] = count(r1 - 1, c2)
dic[(r2, c1 - 1)] = count(r2, c1 - 1)
res = 0
for r, c in product(range(r1, r2 + 1), range(c1, c2 + 1)):
    tmp = dic[(r, c)] = dic[(r - 1, c)] + dic[(r, c - 1)]
    res += tmp % mod
print(res % mod)

Submission status: Runtime Error

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

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

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

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

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

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

Submission status: Runtime Error

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 + 1 # ここで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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
# 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
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: Runtime Error

Solution code:
from sys import stdin
sys.setrecursionlimit(10**7)
# input = 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
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: Runtime Error

Solution code:
from sys import stdin
# input = 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
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: Runtime Error

Solution code:
from sys import stdin
from operator import mul
from functools import reduce
input = 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
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)