Problem:


Score : 500 points

Problem Statement

There is a building with n rooms, numbered 1 to n.

We can move from any room to any other room in the building.

Let us call the following event a move: a person in some room i goes to another room j~ (i \neq j).

Initially, there was one person in each room in the building.

After that, we know that there were exactly k moves happened up to now.

We are interested in the number of people in each of the n rooms now. How many combinations of numbers of people in the n rooms are possible?

Find the count modulo (10^9 + 7).

Constraints

All values in input are integers.

3 \leq n \leq 2 \times 10^5

2 \leq k \leq 10^9

Input

Input is given from Standard Input in the following format:

n k

Output

Print the number of possible combinations of numbers of people in the n rooms now, modulo (10^9 + 7).

Sample Input 1

3 2

Sample Output 1

10

Let c_1, c_2, and c_3 be the number of people in Room 1, 2, and 3 now, respectively. There are 10 possible combination of (c_1, c_2, c_3):

(0, 0, 3)

(0, 1, 2)

(0, 2, 1)

(0, 3, 0)

(1, 0, 2)

(1, 1, 1)

(1, 2, 0)

(2, 0, 1)

(2, 1, 0)

(3, 0, 0)

For example, (c_1, c_2, c_3) will be (0, 1, 2) if the person in Room 1 goes to Room 2 and then one of the persons in Room 2 goes to Room 3.

Sample Input 2

200000 1000000000

Sample Output 2

607923868

Print the count modulo (10^9 + 7).

Sample Input 3

15 6

Sample Output 3

22583772



Sample input:
3 2


Sample output:
10

Submission status: Runtime Error

Solution code:
import sys

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


def input():
    return sys.stdin.readline().strip()


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """

    def __init__(self, n_max, mod=10 ** 9 + 7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n + 1):
            fac.append(fac[i - 1] * i % self.mod)
            facinv.append(facinv[i - 1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n + 1)
        modinv[1] = 1
        for i in range(2, n + 1):
            modinv[i] = self.mod - self.mod // i * modinv[self.mod % i] % self.mod
        return modinv


def main():
    N, K = map(int, input().split())
    comb = Combination(n_max=10 ** 5 * 2 + 10)

    if N <= K:
        ans = comb(2 * N - 1, N)
    else:
        if K == 1:
            ans = comb(N, 1) * comb(N - 1, 1)
        else:
            ans = 0
            # mはゼロとなる数
            for m in range(K + 1):
                ans += comb(N, m) * comb(N - 1, m)
                ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

    return result

N,K=map(int,input().split())
k=min(K,N-1)
x=0
A=[0]*(k+1)
B=[0]*(k+1)
for i in range(k+1):
 B[i]=cmb(N-1,i)%(10**9+7)
 A[i]=cmb(N,i)%(10**9+7)
for i in range(k+1):
 x+=(A[i]*b[i])%(10**9+7)
print(x%(10**9+7))

Submission status: Runtime Error

Solution code:
from scipy.special import comb

n, k = map(int, input().split())

def co(n, r):
    x = comb(n, r, exact=True) % (10 ** 9 + 7)
    return x

if k >= n:
    ans = (2 ** (n-1)) % (10 ** 9 + 7)
else:
    ans = 0

    for i in range(k+1):
        y = (co(n-1, i) * co(n, i)) % (10 ** 9 + 7)
        ans += y

    ans % (10 ** 9 + 7)

print(ans)

Submission status: Runtime Error

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n,k = mi()
#a^-1 (mod P)
mod = 10 ** 9 +7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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

'''
ここは任意
'''

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

def main():
    if k >= n -1:
        ans = combination(2*n -1,n-1)
        print(ans)
    else:
        ans = 1
        for i in range(1,k+1):
            zero_comb = combination(n,i)
            cou = combination(n-1,n-i-1) * zero_comb % mod
            #print(cou)
            ans = (ans +cou) % mod
        print(ans)
main()

Submission status: Runtime Error

Solution code:
mod = 7+10**9

def expo(x):
  ans = 1
  n = mod-2
  if memo_e[x]:
    return memo_e[x]
  while n>0:
    if n%2 == 1:
      ans = ans*x%mod
    x = x*x%mod
    n = n >> 1
  memo_e[x] = ans
  return ans

def combi(n,k):
  return (fac[n]*(expo(fac[k]))%mod)*expo(fac[n-k])%mod

n,k = map(int,input().split())
fac = [1]+[0]*n
for i in range(1,n+1):
  fac[i] = fac[i-1]%mod

memo_e = [0]*(n**n+1)
ans = 0
for i in range(min(n,k+1)):
  ans = (ans + combi(n,i)*combi(n-1,i)%mod)%mod
print(ans)

Submission status: Runtime Error

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

mod = 7+10**9

def expo(x,n):
  ans = 1
  while n>0:
    if n%2 == 1:
      ans = ans*x%mod
    x = x*x%mod
    n = n >> 1
  return ans

def fac(n):
  if not memo_f[n]:
    memo_f[n] = (n*fac(n-1))%mod
  return memo_f[n]

def combi(n,k):
  return (((fac(n)*(expo(fac(k),mod-2)))%mod)*expo(fac(n-k),mod-2))%mod


n,k = map(int,input().split())
memo_f = [1]+[0]*n

if k == 1:
  ans = combi(n-1,k)*combi(n,k)%mod
elif k >= n:
  ans = 0
  for i in range(n):
    ans = (ans + combi(n,i)*combi(n-1,i)%mod)%mod
else:
  ans = 0
  for i in range(k+1):
    ans = (ans + combi(n,i)*combi(n-1,i)%mod)%mod
print(ans)

Submission status: Runtime Error

Solution code:
mod = 7+10**9

def expo(x,n):
  ans = 1
  while n>0:
    if n%2 == 1:
      ans = ans*x%mod
    x = x*x%mod
    n = n >> 1
  return ans

def fac(n):
  if not memo_f[n]:
    memo_f[n] = (n*fac(n-1))%mod
  return memo_f[n]

def combi(n,k):
  return (((fac(n)*(expo(fac(k),mod-2)))%mod)*expo(fac(n-k),mod-2))%mod


n,k = map(int,input().split())
memo_f = [1]+[0]*n

if k == 1:
  ans = combi(n-1,k)*combi(n,k)%mod
elif k >= n:
  ans = 0
  for i in range(n):
    ans = (ans + combi(n,i)*combi(n-1,i)%mod)%mod
else:
  ans = 0
  for i in range(k+1):
    ans = (ans + combi(n,i)*combi(n-1,i)%mod)%mod
print(ans)

Submission status: Runtime Error

Solution code:
mod = 7+10**9

def expo(x,n):
  ans = 1
  if x%2 == 1:
    ans = ans*x
  x = x*x
  n = n >> 1
  return ans

def fac(n):
  if not memo_f[n]:
    return (n*fac(n-1))%mod
  else:
    return memo_f[n]

def combi(n,k):
  return (((fac(n)*(expo(fac(k),mod-2)))%mod)*expo(fac(n-k)))%mod


n,k = map(int,input().split())
memo_f = [1]+[0]*n

if k == 1:
  ans = combi(n-1,k)*combi(n,k)%mod
elif k >= n:
  ans = 0
  for i in range(n):
    ans = (ans + combi(n,i)*combi(n-1,i)%mod)%mod
else:
  ans = 0
  for i in range(k+1):
    ans = (ans + combi(n,i)*combi(n-1,i)%mod)%mod
print(ans)

Submission status: Runtime Error

Solution code:
#input
n, k = map(int, input().split())

#output
mod = pow(10, 9) + 7

n_ = 3*10**5
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

if n <= k-1:
    print(cmb(2*n-1, n))
else:
    answer = 0
    for m in range(k+1):
        answer += cmb(n, m)*cmb(n-1, m) % mod
        answer %= mod
    print(answer)

Submission status: Runtime Error

Solution code:
#input
n, k = map(int, input().split())

#output
mod = pow(10, 9) + 7

n_ = 2*10**5 + 3
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

if n <= k-1:
    print(cmb(2*n-1, n))
else:
    answer = 0
    for m in range(k+1):
        answer += cmb(n, m)*cmb(n-1, m) % mod
        answer %= mod
    print(answer)

Submission status: Runtime Error

Solution code:
#input
n, k = map(int, input().split())

#output
mod = pow(10, 9) + 7

n_ = 2*10**5
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

if n <= k-1:
    print(cmb(2*n-1, n))
else:
    answer = 0
    for m in range(k+1):
        answer += cmb(n, m)*cmb(n-1, m) % mod
        answer %= mod
    print(answer)

Submission status: Runtime Error

Solution code:
#input
n, k = map(int, input().split())

#output
mod = pow(10, 9) + 7

def cmb(n, r):
    res = 1
    fac = 1
    for i in range(r):
        res *= (n-i)
        res %= mod
        fac *= (i+1)
        fac %= mod
    return res*pow(fac, mod-2, mod) % mod

if n <= k-1:
    print(cmb(2*n-1, n))
else:
    answer = 0
    for m in range(k+1):
        answer += cmb(n, m)*cmb(n-1, m) % mod

print(answer % mod)

Submission status: Runtime Error

Solution code:
#input
n, k = map(int, input().split())

#output
mod = pow(10, 9) + 7

def cmb(n, r):
    res = 1
    fac = 1
    for i in range(r):
        res *= (n-i)
        res %= mod
        fac *= (i+1)
        fac %= mod
    return res*pow(fac, mod-2, mod) % mod

if n <= k-1:
    print(cmb(2*n-1, n))
else:
    answer = 0
    for m in range(k+1):
        answer += cmb(n, m)*cmb(n-1, a) % mod

print(answer % mod)

Submission status: Runtime Error

Solution code:
#input
n, k = map(int, input().split())

#output
mod = pow(10, 9) + 7

def cmb(n, r):
    res = 1
    fac = 1
    for i in range(r):
        res *= (n-i)
        res %= mod
        fac *= (i+1)
        fac %= mod
    return res*pow(fac, mod-2, mod) % mod

if n <= k-1:
    print(cmb(2*n-1, m))
else:
    answer = 0
    for m in range(k+1):
        answer += cmb(n, m)*cmb(n-1, a) % mod

print(answer % mod)

Submission status: Runtime Error

Solution code:
N=2*10**5+1
mod=10**9+7
f=[None]*N
f[0]=1
for i in range(1,N):
  f[i]=i*f[i-1]%mod
for i in range(1,N):
  fi[i]=pow(f[i],mod-2,mod)
def com(n,k):
  return f[n]*fi[n-k]%mod*fi[k]%mod
def hcom(n,k):
  return com(n+k-1,n-1)
n,k=map(int,input().split())
ans=1
for i in range(1,min(k,n)):
  ans=(ans+com(n,i)*hcom(n-i,i)%mod)%mod
print(ans)

Submission status: Runtime Error

Solution code:
N=2*10**5+2
mod=10**9+7
f=[None]*N
f[0]=1
for i in range(1,N):
  f[i]=i*f[i-1]%mod
for i in range(1,N):
  fi[i]=pow(f[i],mod-2,mod)
n,k=map(int,input().split())
ans=1
for i in range(1,min(k,n)):
  ans+=f[n]*fi[k]%mod*fi[k]%mod*f[n+1]*%mod*fi[i-1]%mod
  ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
N=2*10**5+1
mod=10**9+7
f=[None]*N
f[0]=1
for i in range(1,N):
  f[i]=i*f[i-1]%mod
for i in range(1,N):
  fi[i]=pow(f[i],mod-2,mod)
n,k=map(int,input().split())
ans=1
for i in range(1,min(k,n)):
  ans+=f[n]*fi[k]%mod*fi[k]%mod*f[n+1]*%mod*fi[i-1]%mod
  ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
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 ** 5+15  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
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 solve():
  n,k = (int(i) for i in input().split())
  mod = 10**9+7
  if n-k <= 1:
    #任意の部屋に移動可能
    comba = 1
    inva = 1
    for i in range(1,n+1):
      comba *= (n+i-1)
      inva *= i
      comba %= mod
      inva %= mod
    comba *= pow(inva,10**9+5,mod)
    comba %= mod
    print(comba)
  else:
    #n <= 2**10^5
    #k <= 2**10^5
    ans = 0
    
    
    
    for i in range(0,k+1):
      ans += cmb(n,i,mod)*cmb(n-1,i,mod)
      ans %= mod
    
    print(ans)
  
solve()

Submission status: Runtime Error

Solution code:
Point = complex


N, *XY = map(int, open(0).read().split())

P = [Point(x, y) for x, y in zip(*[iter(XY)] * 2)]

def max_distance(center):
    return max(abs(center - p) for p in P)

def ternary_search(f, left, right, MAX_ITER=100):
    for _ in range(MAX_ITER):
        m1 = (left * 2 + right) / 3
        m2 = (left + right * 2) / 3
        if f(m1) < f(m2):
            right = m2
        else:
            left = m1
    return f(left)

def g(x):
    return ternary_search(lambda y: max_distance(Point(x, y)), -1000, 1000)

print(ternary_search(g, -1000, 1000))

Submission status: Runtime Error

Solution code:
from functools import lru_cache


CHECK = False

N, K = list(map(int, input().split()))

MOD = 10 ** 9 + 7


@lru_cache(maxsize=None)
def modInverse(a, p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a, p - 2, p)


if CHECK:
    fact = [1]
    for i in range(1, 2 * N + 1):
        fact.append((fact[-1] * i) % MOD)

    def nCr(n, r, p=MOD):
        # Modulo binomial coefficients
        return (fact[n] * modInverse(fact[r], p) * modInverse(fact[n - r], p)) % p


if N - 1 <= K:
    # Any combo is achievable so this is stars and bars
    # N people into N rooms, which means N - 1 dividers
    stars = N
    bars = N - 1
    print(nCr(stars + bars, bars))
else:
    # Group by number of empty rooms
    # With K moves there can only be at most K empty rooms
    # Max of N - 1 empty rooms in general
    assert K + 1 < N
    tot = 0
    comb1 = 1
    comb2 = 1
    for numEmpty in range(K + 1):
        way3 = comb1 * comb2
        if CHECK:
            numNonEmpty = N - numEmpty
            stars = numEmpty  # Everyone moving into an occupied room
            bars = numNonEmpty - 1  # Number of dividers
            way1 = nCr(stars + bars, bars) * nCr(N, numEmpty)

            way2 = nCr(N, numEmpty) * nCr(N - 1, numEmpty)

            assert way1 % MOD == way2 % MOD == way3 % MOD
        tot += way3

        j = numEmpty + 1
        invJ = modInverse(j, MOD)
        comb1 = (N + 1 - j) * comb1 * invJ % MOD
        comb2 = (N - j) * comb2 * invJ % MOD
    print(tot % MOD)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())

mod = 10**9+7

m = 10**5 * 4 +10 
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

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

if k*2 >= n:
    print(comb(2*n-1,n))
    1/0
else:
    ans = 0
    for i in range(k+1):
        ans += comb(n,i)*comb(n-1,i)
        ans %= mod
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
import os
f = open('../../input.txt', 'r')
sys.stdin = f

n,k = map(int, input().split())
mod = 10**9 + 7

ans = 0
lim = 2*(10**5) + 5
mothers = [1] * lim
mothers_inv = [1] * lim
for i in range(1, lim):
    mothers[i] = mothers[i-1] * i % mod
    mothers_inv[i] = pow(mothers[i], mod-2, mod)


def calc(n,k):
    child = mothers[n] * mothers_inv[n-k] % mod
    mother_inv = mothers_inv[k]
    return((child * mother_inv)%mod)

def calc2(n,k):
    child = 1
    for i in range(n, n-k, -1):
        child = child * i % mod
    mother_inv = mothers_inv[k]
    return((child * mother_inv)%mod)

if( n <= k+1):
    ans = calc2(2*n-1, n-1)
    print(ans)
    exit()

ans = calc2(2*n-1, n-1)

for i in range(1,n-k):
    if(i ==1):
        c1 = 1
    else:
        c1 = calc(n-1, i-1)

    c2 = calc(n, i)
    ans = (ans - c1 * c2)%mod


print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
mod = 10**9 + 7

ans = 0
lim = 2*(10**5) + 5
mothers = [1] * lim
mothers_inv = [1] * lim
for i in range(1, lim):
    mothers[i] = mothers[i-1] * i % mod
    mothers_inv[i] = pow(mothers[i], mod-2, mod)


def calc(n,k):
    child = mothers[n] * mothers_inv[n-k] % mod
    mother_inv = mothers_inv[k]
    return((child * mother_inv)%mod)

def calc2(n,k):
    child = 1
    for i in range(n, n-k, -1):
        child = child * i % mod
    mother_inv = mothers_inv[k]
    return((child * mother_inv)%mod)

if( n <= k+1):
    ans = calc2(2*n-1, n-1)
    print(ans)
    exit()

ans = calc(2*n-1, n-1)

tmp = 0
for i in range(1,n-k):
    if(i ==1):
        c1 = 1
    else:
        c1 = calc(n-1, i-1)

    c2 = calc(n, i)
    ans = (ans - c1 * c2)%mod


print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
mod = 10**9 + 7

ans = 0
lim = 2*(10**5) + 5
mothers = [1] * lim
mothers_inv = [1] * lim
for i in range(1, lim):
    mothers[i] = mothers[i-1] * i % mod
    mothers_inv[i] = pow(mothers[i], mod-2, mod)


def calc(n,k):
    child = mothers[n] * mothers_inv[n-k] % mod
    mother_inv = mothers_inv[k]
    return((child * mother_inv)%mod)

if( n <= k+1):
    ans = calc(2*n-1, n-1)
    print(ans)
    exit()

ans = calc(2*n-1, n-1)

tmp = 0
for i in range(1,n-k):
    if(i ==1):
        c1 = 1
    else:
        c1 = calc(n-1, i-1) 

    c2 = calc(n, i) 
    ans = (ans - c1 * c2)%mod


print(ans)

Submission status: Runtime Error

Solution code:
[n,a,b]=list(map(int,input().split()))
MOD=10**9+7
ans=pow(2,n,MOD)-1

nCk=[1]
for i in range(b+1):
    tuika=nCk[i]*(n-i)/(i+1)
    nCk.append(tuika)
ans=ans-(nCk[a]%MOD)-(nCk[b]%MOD)
print(ans%MOD)

Submission status: Runtime Error

Solution code:
def factorial(n, mod=10**9+7):
    a = 1
    for i in range(1,n+1):
        a = a * i % mod
    return a


def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


def comb(n, k, mod=10**9+7):
    if n < k or k < 0:
        result = 0
    else:
        a = factorial(n, mod=mod)
        b = factorial(k, mod=mod)
        c = factorial(n-k, mod=mod)
        result = (a * power(b, mod-2, mod=mod) * power(c, mod-2, mod=mod)) % mod
    return result

n, k = map(int, input().split())
MOD = 10**9 + 7

if k >= n:
  print(comb(2*n-1, n))
  quit()

def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


fl = [-1]*(k+1)
fl[0] = 1
def f(i):
  global fl
  if fl[i] > 0: return fl[i]
  else:
    if i <= n//2:
      res = f(i-1)*(n-i+1)*(n-i)
      t = power(i, MOD-2)
      res *= t
      res %= MOD
      res *= t
      res %= MOD
      fl[i] = res
      return res
    else:
      res = f(n-i) * (n-i)
      res *= power(i, MOD-2)
      res %= MOD
      fl[i] = res
      return res


if k <= n//2:
  fl = [-1]*(k+1)
  fl[0] = 1
  def f(i):
    global fl
    if fl[i] > 0: return fl[i]
    else:
      res = f(i-1)*(n-i+1)*(n-i)
      t = power(i, MOD-2)
      res *= t
      res %= MOD
      res *= t
      res %= MOD
      fl[i] = res
      return res

  ans = 0
  for i in range(k+1):
    ans += f(i)
    ans %= MOD
else:
  fl = [-1]*(n+1)
  fl[0] = comb(n, k) * comb(n-1, k) % MOD
  def f(i):
    global fl
    if fl[i-k] > 0: return fl[i-k]
    else:
      res = f(i-1)*(n-i+1)*(n-i)
      t = power(i, MOD-2)
      res *= t
      res %= MOD
      res *= t
      res %= MOD
      fl[i-k] = res
      return res
  
  ans = 0
  for i in range(k+1, n+1):
    ans += f(i)
    ans %= MOD
  ans = comb(2*n-1, n) - ans
  ans %= M0D


print(ans % MOD)

Submission status: Runtime Error

Solution code:
from sys import stdin
from math import factorial


def pattern(n, k):
    pass


def combinational(n, x):
    return (factorial(n) % (1e9+7.)) // ((factorial(n - x) %
                                          (1e9+7.) * factorial(x) % (1e9+7.)))


def main():
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    if K >= N - 1:
        return combinational(2*N - 1, N) % (1e9+7)
    else:
        return int(combinational(2*N - 1, N) % (1e9+7))


if __name__ == "__main__":
    print(main())

Submission status: Runtime Error

Solution code:
def modinv(a,m):
    return pow(a,m-2,m)


n,k = map(int,input().split())
P = 10**9+7

if n-1 <= k:

    ans = 1
    for i in range(1,n):
        ans = ans*(N+1-i)*modinv(i,P)%P

else:
    ans = 0
    nCl = 1
    n1Cl = 1
    for l in range(1,k+1):
        nCl = nCl*(n+1-l)*modinv(l,P)%P
        n1Cl = n1Cl*(n-l)*modinv(l,P)%P
        ans = (ans+nCl*n1Cl)%P

print((ans+1)%P)

Submission status: Runtime Error

Solution code:
MOD=10**9+7
n,k=map(int,input().split())

def pow_mod(x,n):
  if n==0:
    return 1
  elif n==1:
    return x
  else:
    xn2=pow_mod(x,n//2)
    if n%2==0:
      return (xn2*xn2)%MOD
    else:
      return (xn2*xn2*x)%MOD

def fact_mod(a):
  if a<=1:
    return 1
  else:
    return a*fact_mod(a-1)%MOD
  
def perm_mod(n,a):
  if a==1:
    return n
  else:
    return (n*perm_mod(n-1,a-1))%MOD

def inv_mod(a):
  return pow_mod(a,MOD-2)%MOD
  
def comb_mod(na,fa):
  ainv=inv_mod(fa)
  return (na*ainv)%MOD
  
if k>=n-1:  
  #nHn=(2n-1)Cn
  perm=perm_mod(2*n-1,n)
  fact=fact_mod(n)
  comb=comb_mod(perm,fact)
  #print(perm,fact,comb)
  print(comb)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def combi(n,k,p):
    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
mod=10**9+7
def do():
    n,k=INTM()
    if n-1<=k:
        ans=combi(2*n-1,n-1,mod)
    elif k<=n//2:
        ct=0
        for i in range(k+1):
            ct+=combi(n,i,mod)*combi(n-1,i,mod)
            #print(ct)
        ans=ct
    else:
        ct=combi(2*n-1,n-1,mod)
        for i in range(1,n-k):
            #print(i)
            ct-=combi(n,i,mod)*combi(n-1,i-1,mod)
        ans=ct
    print(ans)
if __name__ == '__main__':
    do()

Submission status: Runtime Error

Solution code:
import math
import sys
from functools import lru_cache
#from scipy.special import comb
from operator import mul
from functools import reduce

n,a,b=map(int,input().split())
'''
def memoize(f): #メモ化関数
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memoize
def memFrac(n):
    if ( n==0 ):
        return 1
    else:
        return n*memFrac(n-1)

def perm(n,r):
    return memFrac(n) // (memFrac(n - r)*memFrac(r))

sys.setrecursionlimit(1000000007)
@lru_cache(maxsize=1000)
def frac(n):
    if n<2:
        return n
    else:
        return n*frac(n-1)

def perm(n,r):
    return frac(n) // (frac(n - r)*frac(r))
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 ** 10  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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)
'''
p = 10 ** 9 + 7

sys.setrecursionlimit(1000000007)
@lru_cache(maxsize=1000)
def frac(n):
    if n<2:
        return n
    else:
        return n*frac(n-1)

def perm(n,r):
    return frac(n) // (frac(n - r)*frac(r))


a1=perm(n,a)
b1=perm(n,b)

#a1=cmb(n,a)
#b1=cmb(n,b)

print((pow(2,n)-1-a1-b1)%p)

Submission status: Runtime Error

Solution code:
import sys
t = int(sys.stdin.readline())
stack = [[] for i in range(1000010)]
for __ in range(t):
	s = map(lambda x: ord(x)-ord('0'), sys.stdin.readline().rstrip())
	a,h = map(int, sys.stdin.readline().split())
	h %= len(s)
	ans = "".join(map(str,s))
	vis = set()
	sidx = 0
	
	def push(val):
		global ans,sidx
		hs = "".join(map(str,val))
		if hs in vis: return
		ans = min(ans, hs)
		vis.add(hs)
		stack[sidx] = val
		sidx += 1
	
	push(s)
	while sidx > 0:
		cur = stack[sidx-1]
		sidx -= 1
		push(cur[h:]+cur[:h])
		for i in range(1,len(cur),2):
			cur[i] = (cur[i]+a)%10
		push(cur)
	print ans

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;

set<string>mp;
int add,shift;
void dfs( string tmp)
{
  //cout<<tmp<<endl;
  mp.insert(tmp);
  string next=tmp;
  int i,n=tmp.size();
  for(i=0;i<n;i++)
  {
    next[(i+shift)%n]=tmp[i];
  }
  if(mp.find(next)==mp.end())
    dfs(next);
  next=tmp;
  for(i=0;i<n;i++)
  {
    if(i%2)
    next[i]= '0'+ (next[i]-'0'+add)%10;
  }
  if(mp.find(next)==mp.end())
    dfs(next);
  return;
}
int main()
{
  // freopen("in.txt","r",stdin);
  // freopen("out","w",stdout);
  ios_base::sync_with_stdio(0);
  int t;
  cin>>t;
  assert(1<=t && t<=10);
  while(t--)
  {
    string inp;
    cin>>inp>>add>>shift;
    mp.clear();
    dfs(inp);
    cout<<*(mp.begin());
    if(t>0)
      cout<<endl;
  }
 return 0;
}

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

def nPk(n,k):
    
    # x=1
    # for a in range(n-k+1, n+1):
    #     x = x * a % MOD
    # return x
    return kaijo[n] * inv(kaijo[k-1]) % MOD

def nCk(n,k):
    return nPk(n,k) * inv(kaijo[k])

MOD = 10**9+7

kaijo = [0] * 200005
kaijo[0] = 1
for i in range(1, len(kaijo)):
    kaijo[i] = kaijo[i-1] * i % MOD

n,k = get_nums_l()

if k >= n-1:
    print(nCk(n+n-1, n) % MOD)
    exit()

# 0人の部屋=zがk以下であるような人数の並べ方の個数

# z=0 1
# z=1 nC1 * (n-1)**1
# z=2 nC2 * (n-2)**2
# z=3 nC3 * (n-3)**3

ans = 1
for z in range(1,k+1):
    ans += nCk(n,z) * nCk(n-1, z) % MOD

print(ans%MOD)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
def make_fact(n):#0~nの階乗を求める
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i%mod
    return fact
fact = make_fact(n*2) #＠
def make_fact_inv(n):#0~nの階乗のmodに関する逆元を求める
    fact_inv = [1]*(n+1)
    fact_inv[n] = pow(fact[n], mod-2, mod)#フェルマーの小定理
    for i in range(n, 0, -1):
        fact_inv[i-1] = fact_inv[i]*i%mod
    return fact_inv
fact_inv = make_fact_inv(n*2)#＠
def comb(n, k):#nCk
    return fact[n]*fact_inv[k]*fact_inv[n-k]%mod
mod = 10**9+7
ans = 0
for i in range(n):
    m = n-i
    c = n-m
    if c+i>k*2 or (c+i)%2 != k%2:
        continue
    ans+=comb(n, i)*comb(m+c-1, m-1)%mod
    ans%=mod
print(ans)