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

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


MOD = 10**9 + 7

# https://qiita.com/derodero24/items/91b6468e66923a87f39f


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])
      result %= MOD

  return result

print(cmb(n + n - 1, n))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())

MOD = 10 ** 9 + 7

# fac[i] = i!
# inv[i] = iの逆元

fac = [1]
inv = [1]

for i in range(1, 2 * N + 5) :
	fac.append(fac[-1] * i % MOD)
	inv.append(pow(fac[-1], MOD - 2, MOD))

# K の条件無視
ans = fac[2 * N - 1] * inv[N] * inv[N - 1] % MOD

# そっから条件に引っかかるやつを引いてあげる
sikiri = (N - 1) - (K + 1)

if N - K - 3 < 0:
	hiku = 0
else:
	hiku = fac[N - 2] * inv[K + 1] * inv[N - K - 3] * fac[N + sikiri] * inv[N] * inv[sikiri] % MOD

print((ans - hiku) % MOD)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

N, K = map(int, input().split())
MOD = 10 ** 9 + 7


@lru_cache(None)
def F(n, k, m):

    ret = 0

    if n < 0:
        return 0

    if k == 1:
        return 1

    for i in range(m+1):
        t = F(n - i, k - 1, m)
        #print("n,k,ans", n-1, k-1, t)
        t %= MOD
        ret += t

    #print("n,k,ans", n, k, ret)
    return ret


a = F(N, N, min(K + 1, N))

print(a)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
mod = 10 ** 9 + 7
n = N * 2
fact = [1]*(n+1)
rfact = [1]*(n+1)
r = 1
for i in range(1, n+1):
  fact[i] = r = r * i % mod
rfact[n] = r = pow(fact[n], mod-2, mod)
for i in range(n, 0, -1):
  rfact[i-1] = r = r * i % mod
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % mod

if N <= K-1:
  print(comb(n-1,N))
else:
  if K == 1:
    print((N * (N-1)) % mod)
  else:
    ans = (1 + (N * (N-1))) % mod
    for i in range(2,K+1):
      mini_ans = (comb(N,i) * comb(N-1,N-i-1)) % mod
      ans = (ans + mini_ans) % mod
    print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
mod = 10**9+ 7 
def power_(n, p, mod):
    if p == 1:
        return n
    if p % 2 == 0:
        return (power_(n, p//2, mod) ** 2) % mod
    else:
        return n * (power_(n, p//2, mod) ** 2) % mod
#互いに素なa,bについて、a*x+b*y=1の一つの解
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
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
#a/b = a*(b`)となるb`を求める
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod
fact = [1 for i in range(n*2+1)]
for i in range(1,n*2+1):
    fact[i] = (fact[i-1] * i) % mod
if k + 1 >= n:
    child = fact[n * 2  - 1]
    mother = mod_inv(fact[n], mod) * mod_inv(fact[n-1], mod)
    print((child * mother) % mod)
else:
    #k人までは自由に振り分け、そのあとはnCn-k
    bow = n - k - 1
    """
    child = fact[bow + k]
    mother = (mod_inv(fact[k], mod) * mod_inv(fact[bow], mod)) % mod
    combi = (fact[n] * mod_inv(fact[n - k],mod) * mod_inv(fact[k],mod)) % mod
    aa = power_(n,k,mod)
    aa -= combi
    """
    ans = 0
    #実際に移動する人数を固定
    for i in range(1,k+1):
        if (k - i) % 2 != 0:
            continue
        bow = n - i - 1
        child = fact[bow + i]
        mother = (mod_inv(fact[i], mod) * mod_inv(fact[bow], mod)) % mod
        combi = (fact[n] * mod_inv(fact[n - i],mod) * mod_inv(fact[i],mod)) % mod
        ans += (child * mother * combi) % mod
        ans %= mod
    print(ans % mod)

Submission status: Wrong Answer

Solution code:
def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res

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

MOD = 1000000007

if n-1 > k:
    ans = 1
    com1 = 1
    com2 = 1
    for i in range(k):
        com1 = com1 * (n-1-i) * modpow(i+1, MOD-2, MOD) % MOD
        com2 = com2 * (n-i) * modpow(i+1, MOD-2, MOD) % MOD
        ans += com1 * com2
    print(ans)
else:
    ans = 1
    for i in range(n-1):
        ans = ans * (n*2-1-i) * modpow(i+1, MOD-2, MOD) % MOD
    print(ans)

Submission status: Wrong Answer

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

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

Solution code:
from math import factorial
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: Wrong Answer

Solution code:
n,k = map(int,input().split())
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
print(combination(n+n-1,n))

Submission status: Wrong Answer

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

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

#階乗計算
kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

# コンビネーション計算
def cmb(n, r):
	return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

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

if k < n - 1:
    ans -= cmb(2 * n -2 -k, n-1)

print(ans % mod)

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
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル



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


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

ans = 0
if k >= n-1:
    print(cmb(2*n-1,n-1,mod))
else:
    ans = cmb(2*n-1,k,mod)
    print(ans)

Submission status: Wrong Answer

Solution code:
def modc(a,b,m):
    c = 1
    for i in range(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

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

factorial = [1]
inverse = [1]
for i in range(1, n+1):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))

def comb(n, r, mod):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


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

Submission status: Wrong Answer

Solution code:
MAX_NUM = 10**6 + 1
MOD = 10**9+7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2,MAX_NUM):
    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 combinations(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD
n, k = map(int, input().split())
print(combinations(2*n-1, n-1))

Submission status: Wrong Answer

Solution code:
p = 10 ** 9 + 7
N = (10 ** 5)*2 +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)

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


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

ans = [1]

# i人が動いた
# iのときi-1を再現可能
# iを考えるときi部屋は空になる
# 残りのn-i部屋から選ぶ
# 1,6,3

for  i in range(1,N+1):
    mm1 = cmb(N,i,p)
    # mm2 = (cmb(N-i,1,p)*ans[i-1])%p
    # nHr n:n-i, r:i
    mm2 = cmb(N-i+i-1,i,p)

    ans.append((mm1*mm2)%p)

mm = 0
for i in range(N):
    mm += ans[i]
    mm %= p
print(mm)

# 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 = 2 * 10**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)

def modPow(a, n, mod):
    if n == 1:
        return a
    if n % 2 == 1:
        return (a * (modPow(a, n//2, mod) ** 2)) % mod
    else:
        return (modPow(a, n//2, mod) ** 2) % mod


def modInverse(a, p):
    # calculates the modular multiplicative of a mod m.
    # (assuming p is prime).
    return modPow(a, p-2, p)


def modBinomial(n, k, p):
    # calculates C(n,k) mod p (assuming p is prime).

    numerator = 1  # n * (n-1) * ... * (n-k+1)
    for i in range(k):
        numerator = (numerator * (n-i)) % p

    denominator = 1  # k!
    for i in range(1, k+1):
        denominator = (denominator * i) % p

    # numerator / denominator mod p.
    return (numerator * modInverse(denominator, p)) % p

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

if n <= k:
    print(modBinomial(2*n-1,n,mod))
    exit()
ans = 0
if k % 2 == 0:
    ans += 1
for i in range(1,k+1):
    ans = (ans + cmb(n,i,mod) * cmb(n-1,i,mod)) % mod

print(ans)

Submission status: Wrong Answer

Solution code:
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]]
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod + x % mod)% mod
def comb(n,k,mod):
    c = 1
    for i in range(k):
        c = c*(n-i)%mod
        c = c*mod_inv(i+1,mod)%mod
    return c
n,k = map(int,input().split())
mod = 10**9+7
if k >= n-1:
    print(comb(n+n-1,n,mod))
else:
    ans = 0
    c = 1
    c2 = 1
    for i in range(k):
        c = c*(n-1-i)%mod
        c2 = c2*(n-i)%mod
        c = c*mod_inv(i+1,mod)%mod
        c2 = c2*(mod_inv(i+1,mod))%mod
        ans += c*c2
        ans %= mod
    if k % 2 == 0:
        ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
n, k = 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 = 200000
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 )

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

    else:
        for i in range(n-1):
            ans += cmb(n-1, i, mod) * cmb(n, i, mod)
            ans %= mod

else:
    for i in range(k+1):
        ans += cmb(n-1, i, mod) * cmb(n, i, mod)
        ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
N, _ = map(int, input().split())

def cb(n, k):
    ret = a = b = 1
    mod = 10**9 + 7
    for i in range(k):
        a *= n-i
        a %= mod
        b *= i + 1
        b %= mod
    m = mod-2
    while m > 0:
        if m % 2 != 0:
            ret *= b
            ret %= mod
        b *= b
        b %= mod
        m //= 2
    ret *= a
    ret %= mod
    return ret

print(cb(N + N - 1, N))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
mod = 10**9+7
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)

Submission status: Wrong Answer

Solution code:
def main():
    mod=1000000007
    n,k=map(int,input().split())
    m=2*n
    Fact=[1] #階乗
    for i in range(1,m+1):
        Fact.append(Fact[i-1]*i%mod)
    Finv=[0]*(m+1) #階乗の逆元
    Finv[-1]=pow(Fact[-1],mod-2,mod)
    for i in range(m-1,-1,-1):
        Finv[i]=Finv[i+1]*(i+1)%mod
    def comb(n,r):
        if n<r:
            return 0
        return Fact[n]*Finv[r]*Finv[n-r]%mod
    
    if k==1:
        return (n*(n-1))%mod
    if k>=n-1:
        return comb(2*n-1,n-1)
    ans=1
    for i in range(1,k+1):
        ans+=(comb(n,i)*comb(n-1,n-i-1))%mod
    return ans
    
if __name__=='__main__':
    print(main())

Submission status: Time Limit Exceeded

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

mod = 1000000007

def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

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

def fac(n):
    ret = 1
    for i in range(1, n + 1):
        ret = (ret * i) % mod
    return ret

def cmb(n, k):
    if k < 0 or k > n:
        return 0
    return (fac(n) * inv(fac(k)) * inv(fac(n - k))) % mod

x = max(0, n - k - 1)
ret = cmb(n * 2 - 1, n - 1)
for i in range(x):
    ret = (ret - cmb(n, i + 1) * cmb(n - 1, i)) % mod
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
import bisect
from functools import reduce
def main():
    def comb(n, r):
        numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
        denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
        return numerator * pow(denominator, mod - 2, mod) % mod
    mod = 10 ** 9 + 7
    N, K = MI()
    if K >= N - 1:
        ans = comb(2 * N - 1, N - 1)
        print(ans)
    else:
        N_r = pow(N, mod - 2, mod)
        ans = N * (N - 1) % mod
        if K >= 2:
            ans += 1
        for i in range(2, K + 1):
            ans += ((comb(N, i) ** 2 % mod) * ((N - i) % mod) * N_r) % mod
            ans %= mod
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

n, k = map(int, input().split())
P = int(1e9+7)


def cmb(n, r, P):
    r = min(r, n - r)
    inv_y = 1
    for i in range(1, r + 1):
        inv_y = (inv_y * i) % P
    inv_y = pow(inv_y, P - 2, P)
    x = 1
    for i in range(n - r + 1, n + 1):
        x = x * i % P
    return (x * inv_y) % P


if k >= n:
    print(cmb(2*n-1, n, P))
    sys.exit()
if k == 1:
    print((n * n - 1) % P)
    sys.exit()
ans = 0
for i in range(0, k + 1):
    ans = (ans + cmb(n - 1, i, P) * cmb(n, i, P)) % P
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
mod=10**9+7
def comb(n,k,mod):
  if k>n-k:
    k=n-k
  c=1
  for i in range(n-k+1,n+1):
    c*=i
    c%=mod
  d=1
  for i in range(1,k+1):
      d*=i
      d%=mod
  return(c*pow(d,mod-2,mod))%mod
ans=0
for k in range(0,min(K+1,N)):
  ans+=(comb(N,k,mod)*comb(N-1,k,mod))%mod
print(ans%mod)

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(2147483647)

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 = n+1  # 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)

ans=1
for i in range(1,k+1):
    ans+=(cmb(n, i, p)*cmb(n-1,n-i-1,p))%p
    
    #print(i,cmb(n, i, p),cmb(n-1,n-i-1,p))

print(ans%p)

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(2147483647)

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]  # 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)

ans=1
for i in range(1,k+1):
    ans+=(cmb(n, i, p)*cmb(n-1,n-i-1,p))%p
    
    #print(i,cmb(n, i, p),cmb(n-1,n-i-1,p))

print(ans%p)

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(2147483647)

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]  # 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)

ans=1
for i in range(1,k+1):
    ans+=cmb(n, i, p)*cmb(n-1,n-i-1,p)
    
    #print(i,cmb(n, i, p),cmb(n-1,n-i-1,p))

print(ans%p)

Submission status: Time Limit Exceeded

Solution code:
n,k = 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 #出力の制限
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 )

ans = 0
#con = cmb(n,k,mod)
#print(con)
for i in range(k+1):
    ans += cmb(n,i,mod)*cmb(n-1,i,mod)
    ans %= mod
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*n):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
ans=comb(2*n-1,n-1)
for i in range(n-1,k,-1):ans=(ans-comb(n,n-i)*comb(n-1,i))%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Cmb:
    def __init__(self, N, mod=10**9+7):
        self.fact = [1,1]
        self.fact_inv = [1,1]
        self.inv = [0,1]
        
        """ 階乗を保存する配列を作成 """
        for i in range(2, N+1):
            self.fact.append((self.fact[-1]*i) % mod)
            self.inv.append((-self.inv[mod%i] * (mod//i))%mod)
            self.fact_inv.append((self.fact_inv[-1]*self.inv[i])%mod)
    
    """ 関数として使えるように、callで定義 """
    def __call__(self, n, r, mod=10**9+7):
        if (r<0) or (n<r):
            return 0
        r = min(r, n-r)
        return self.fact[n] * self.fact_inv[r] * self.fact_inv[n-r] % mod

n,k = map(int,input().split())
mod = 10**9+7
c = Cmb(N=n)
ans = 0
for l in range(k+1):
    tmp = c(n,l)*c(n-1, n-l-1)
    ans += tmp%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
input=sys.stdin.readline
mod = 10 ** 9 + 7
 
def cmb(n, r):

    r = min(r, n - r)
    x = 1
    y = 1
    for i in range(r):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    y = pow(y, mod-2, mod)
    return x * y % mod
 
n,k = map(int,input().split())
 
ans=0
k=min(k,n-1)
for i in range(k+1):
    ans += cmb(n,i) * cmb(n-1,i) %mod
 
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007#い　つ　も　の
n,k = map(int,input().split())

nCk = 1#nC0
ans = 1

if k > n-1:
    k = n-1

for i in range(1,k+1,1):
    nCk = (((nCk*(n-i+1))%MOD)*pow(i,1000000005,1000000007))%MOD
    ans = (ans%MOD + ((((nCk*nCk)%MOD)*(n-i)%MOD)*pow(n,1000000005,1000000007)%MOD)%MOD)%MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right


def combination_mod(n, r, mod):
    if r > n:
        return 0  # このような通りの数は無いため便宜上こう定義する
    r = min(r, n - r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
    return nf * pow(rf, mod - 2, mod) % mod
# https://atcoder.jp/contests/abc156/tasks/abc156_e


MOD = 10**9 + 7
n, k = read_ints()
# n<=kのときは簡単
if n <= k:
    print(combination_mod(n + n - 1, n, MOD))
    exit()
# n>kのときはどうしよう

ans = 1
for a in range(1, k + 1):
    ans += combination_mod(n, a, MOD) * combination_mod(n - 1, a, MOD)
    ans %= MOD
print(ans)

# print(combination_mod(n + n - 1, n, MOD))
# print(combination_mod(n + k - 1, k - 1, MOD) * )

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7
class Fp(int):
    def __new__(self,x=0):return super().__new__(self,x%MOD)
    def inv(self):return self.__class__(super().__pow__(MOD-2,MOD))
    def __add__(self,value):return self.__class__(super().__add__(value))
    def __sub__(self,value):return self.__class__(super().__sub__(value))
    def __mul__(self,value):return self.__class__(super().__mul__(value))
    def __floordiv__(self,value):return self.__class__(self*self.__class__(value).inv())
    def __pow__(self,value):return self.__class__(super().__pow__(value%(MOD-1), MOD))
    __radd__=__add__
    __rmul__=__mul__
    def __rsub__(self,value):return self.__class__(-super().__sub__(value))
    def __rfloordiv__(self,value):return self.__class__(self.inv()*value)
    def __iadd__(self,value):self=self+value;return self
    def __isub__(self,value):self=self-value;return self
    def __imul__(self,value):self=self*value;return self
    def __ifloordiv__(self,value):self=self //value;return self
    def __ipow__(self,value):self=self**value;return self
    def __neg__(self):return self.__class__(super().__neg__())

class Combination:
    def __init__(self,max_n):
        self.max_n=0
        self.fact=[Fp(1)]
        self.ifact=[Fp(1)]
        self.make_fact_list(max_n)
    def C(self,n,k):return self.fact[n]*self.ifact[k]*self.ifact[n-k] if 0<=k<=n else 0
    def H(self,n,k):return self.C(n+k-1,k) if n or k else 1
    def P(self,n,k):return self.fact[n]*self.ifact[n-k] if 0<=k<=n else 0
    def make_fact_list(self,max_n):
        if max_n<=self.max_n: return
        self.fact+=[Fp(0)]*(max_n-self.max_n)
        self.ifact+=[Fp(0)]*(max_n-self.max_n)
        for i in range(self.max_n+1,max_n+1):
            self.fact[i]=self.fact[i-1]*i
            self.ifact[i]=self.ifact[i-1]//i
        self.max_n=max_n

N,K=map(int, input().split())
K=min(N-1,K)
C=Combination(N*2)
ans=Fp(1)
for i in range(1,K+1):
    ans+=C.C(N,i)*C.H(N-i,i)
print(ans)

Submission status: Time Limit Exceeded

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

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

def mod_inv_table(k):
    table = [-1]*(k+1)
    for i in range(1,k+1):
        table[i] = mod_inv(i,mod)
    return table

def comb(n,k,table,mod):
    ret = 1
    for i in range(k):
        ret *= n-i
        ret *= table[i+1]
        ret %= mod
    return ret

ans = 0
table = mod_inv_table(n)
for i in range(min(n,k+1)):
    ans = (ans + (comb(n,i,table,mod) * comb(n-1,n-i-1,table,mod))%mod)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, k = map(int, input().split())
mod = 10**9+7

fact = np.zeros(n+1, np.int64)
inv = np.zeros(n+1, np.int64)

fact[0], fact[1] = 1, 1
inv[0], inv[1] = 1, 1

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

if k >= n:
	k = n-1

def C(a,b):
	out = fact[a]
	out *= inv[b]
	out %= mod
	out *= inv[a-b]
	out %= mod
	return out

ans = 0
for m in range(k+1):
	ans += (C(n,m) * C(n-1,n-m-1)) % mod
	ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod) 
  
def comb(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

n,k = [int(i) for i in input().split()]
mod = 10**9+7
ans = 0

for i in range(min(n,k+1)):
  ans += (comb(n,i,mod)*comb(n-1,i,mod)%mod)
  ans %= mod
  
print(ans)

Submission status: Time Limit Exceeded

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

# Function of Combination mod M
# set n >= max p expected
M = 10**9+7


if k >= n-1:
    fac = [1]+[0]*(2*n-1)
    for i in range(1,2*n): fac[i] = fac[i-1]*i %M
    comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = comb(2*n-1,n-1)
    
else:
    y = 1
    c1,c2=1,1
    for i in range(1,k+1):
        c1 *= (n+1-i)*pow(i,M-2,M)%M
        c2 *= (n-i)*pow(i,M-2,M)%M
        y += c1*c2%M
print(y%M)

Submission status: Time Limit Exceeded

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

# Function of Combination mod M
# set n >= max p expected
M = 10**9+7


if k >= n-1:
    fac = [1]+[0]*(2*n-1)
    for i in range(1,2*n): fac[i] = fac[i-1]*i %M
    comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = comb(2*n-1,n-1)
    
else:

    y = 1
    c1,c2=1,1
    for i in range(1,k+1):
        c1 = c1*(n+1-i)*pow(i,M-2,M) #//i 
        c2 = c2*(n-i)*pow(i,M-2,M)
        y += c1*c2%M
print(y%M)

Submission status: Time Limit Exceeded

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

# Function of Combination mod M
# set n >= max p expected
M = 10**9+7


if k >= n-1:
    fac = [1]+[0]*(2*n-1)
    for i in range(1,2*n): fac[i] = fac[i-1]*i %M
    comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = comb(2*n-1,n-1)
    
else:
    fac = [1]+[0]*n
    for i in range(1,n+1): fac[i] = fac[i-1]*i %M
    comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = 1
    for i in range(1,k+1):
        y += (comb(n,i)*comb(n-1,n-1-i))%M
print(y%M)