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: Accepted

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

n_max = 4 * 10**5
fac = [1 for _ in range(n_max)]
inv = [1 for _ in range(n_max)]
finv = [1 for _ in range(n_max)]
def init():
  for i in range(2, n_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    
  
def nCk(n, k, mod):
  return (fac[n] * finv[k] % mod)* finv[n-k] % mod
  
def nHm(n, m, mod):
  return nCk(n+m-1, m, mod)

init()
total = 1
n_max = min(n, k + 1)
for m in range(1, n_max):
  diff = nCk(n, m, mod) * nHm(n - m, m, mod) % mod
  total = total + diff
  

print(total % mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


class Combination(object):

    def __init__(self, N, mod):
        fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
        fac[:2] = 1, 1
        finv[:2] = 1, 1
        inv[1] = 1
        for i in range(2, N+1):
            fac[i] = fac[i-1]*i % mod
            inv[i] = -inv[mod % i]*(mod//i) % mod
            finv[i] = finv[i-1]*inv[i] % mod
        self.N = N
        self.MOD = mod
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def __call__(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return self.fac[n] * (self.finv[k]*self.finv[n-k] % self.MOD) % self.MOD


def div(a, b):
    return (a * pow(b, MOD-2, MOD)) % MOD


def solve(n: int, k: int):

    cmb = Combination(2*n, MOD)
    if n - 1 <= k:
        print(cmb(2*n-1, n))
        return
    else:
        b = 0
        for i in range(k+1):
            b += cmb(n-1, i)*cmb(n, i)
            b %= MOD
        print(b % MOD)
        return
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    k = int(next(tokens))  # type: int
    solve(n, k)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
MOD = 10 ** 9 + 7
SIZE = 10 ** 5 * 2 + 1
fact = [0] * SIZE
inv = [0] * SIZE
finv = [0] * SIZE
fact[0], fact[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1
for i in range(2, SIZE):
    fact[i] = fact[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD


def combination(n, r):
    if n < 0 or r < 0 or n < r:
        return 0
    return fact[n] * (finv[r] * finv[n - r] % MOD) % MOD

k = min(k, n - 1)

ans = 0
for i in range(k + 1):
    ans += combination(n, i) * combination(n - 1, i)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
mod=10**9+7
def cmb(n,r,mod):
  return A[n]*B[n-r]*B[r]%mod
A=[1,1]
B=[1,1]
for i in range(n):
  A.append(A[-1]*(i+2)%mod)
  B.append(B[-1]*pow((i+2),mod-2,mod)%mod)
if k<n:
  ans=0
  for i in range(k+1):
    ans=(ans+cmb(n,i,mod)*cmb((n-1),i,mod))%mod
  print(ans)
else:
  ans=0
  for i in range(n):
    ans=(ans+cmb(n,i,mod)*cmb((n-1),i,mod))%mod
  print(ans)

Submission status: Accepted

Solution code:
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r: return self.combination(n, n - r)
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod


def main():
    mod = 10 ** 9 + 7

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

    cl = Calc(max_value=n, mod=mod)

    m = min(k, n - 1)

    ret = 0
    for i in range(m + 1):
        t = cl.combination(n, i)
        t = t * cl.combination(n - 1, i) % mod
        ret = (ret + t) % mod

    print(ret)


if __name__ == '__main__':
    main()

# 解説放送

# 和がn
# 0はk個以下

# 0の個数を固定して、
# [0,k]個の0について総和を取る

# 0がi箇所
# 1以上がn-i箇所 -> 扱いにくいので、全体から1を引いて0以上にする
# 和がn

# 0以上がn-i箇所
# 和がn-(n-i)=i

# n-i箇所にi個のボールを入れる問題になる
# H(n-i,i)

# n-i-1本の仕切り線とi個のボールの並べ方になる
# choose((n-i-1)+i,i)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

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

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


def main():
    N, K = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7

    a = min(N - 1, K)

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

    ans = 1
    for i in range(1, a + 1):
        ans += cmb(N, i, MOD) * cmb(N - 1, N - i - 1, MOD) % MOD

    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

mod = 10**9+7 #出力の制限
N = 10**5 * 2
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * 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 )
# a = cmb(n,r)

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

n,k = m()

co = 0

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


print(co)

Submission status: Accepted

Solution code:
def make_tables(n, p):
    fac = [1, 1]  # 階乗テーブル
    ifac = [1, 1]  # 逆元の階乗テーブル
    inverse = [0, 1]  # 逆元テーブル

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % p)
        inverse.append((-inverse[p % i] * (p//i)) % p)
        ifac.append((ifac[-1] * inverse[-1]) % p)
    return fac, ifac

def cmb(n, r, p, fac, ifac):
    if r < 0 or r > n:
        return 0
    return fac[n] * ifac[r] * ifac[n-r] % p


def resolve():
    n, k = map(int, input().split())
    p = 10 ** 9 + 7
    
    k = min(n-1, k)
    sum = 0
    fac, ifac = make_tables(n, p)
    for i in range(0, k+1):
        sum += cmb(n, i, p, fac, ifac) * cmb(n-1, i, p, fac, ifac) % p

    print(sum % p)



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
m=10**9+7;f=[1];n,k=map(int,input().split())
for i in range(10**6):f+=[f[i]*(i+1)%m]
def c(a,b):return f[a]*pow(f[b],m-2,m)*pow(f[a-b],m-2,m)%m
s=c(n*2-1,n-1)
if k>n-2:print(s)
else:print((s+(m-sum(c(n-1,i)*c(n,n-i)for i in range(n-1,k,-1))%m))%m)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
list_size = 400001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 
n, k = map(int, input().split())
k = min(k, n-1)
ans = comb(2*n-1, n)
for i in range(n-k-1):
	ans -= comb(n, i+1) * comb(n-1, i)
	ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

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

def cmb(n, r, mod=10**9+7):
    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)+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 )

if k>n:
    k=n

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

Submission status: Accepted

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):
    return kaijo[n] * inv(kaijo[n-k]) % MOD

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

MOD = 10**9+7

kaijo = [0] * 400020
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)H1
# z=2 nC2 * (n-2)H2
# z=3 nC3 * (n-3)H3
# z   nCz * (n-z)Hz

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

print(ans%MOD)

Submission status: Accepted

Solution code:
mod=10**9+7
n,k=map(int,input().split())
ans=0
comb1=1
comb2=1
for i in range(min(k+1,n)):
  ans+=comb1*comb2
  ans%=mod
  comb1*=(n-i)*pow(i+1,mod-2,mod)
  comb1%=mod
  comb2*=(n-1-i)*pow(i+1,mod-2,mod)
  comb2%=mod
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, k = (int(i) for i in input().split())
    MOD = 10**9 + 7
    m = 2*n + 5
    fac = [0] * m
    finv = [0] * m
    inv = [0] * m

    def COMBinitialize(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                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 COMB(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

    COMBinitialize(m)
    if k >= n - 1:
        print(COMB(2*n-1, n))
    else:
        k = min(k, n-1)  # ここなに？？？？？
        ans = 0
        for m in range(k+1):
            ans += COMB(n, m) * COMB(n-1, n-m-1)
            ans %= MOD
        print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N, K = lr()
MOD = 10 ** 9 + 7

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

U = N + 10 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
K = min(N-1, K)
x = fact[N] * fact_inv[0:K+1] % MOD * fact_inv[N-K:N+1][::-1] % MOD
y = fact[N-1] * fact_inv[0:K+1] % MOD * fact_inv[N-K-1:N][::-1] % MOD
answer = (x * y % MOD).sum()
print(answer % MOD)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
k = min(k,n-1)
mod=10**9+7
fact = [1]*(2*10**5+1)
for i in range(2,2*10**5+1):
  tmp = fact[i-1]*i
  tmp%=mod
  fact[i]=tmp
fact_inv = [0]*(2*10**5+1)
for i in range(2*10**5+1):
  fact_inv[i]=pow(fact[i],mod-2,mod)
  
ans=0
def comb(a,b):
  tmp = (fact[a]*fact_inv[a-b]%mod)*fact_inv[b]
  tmp%=mod
  return tmp


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

Submission status: Accepted

Solution code:

class combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        # 1/n!を逆元で求める
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

    def choose(self, n, r):
        if r < 0 or r > n:
            return 0
        ret = (self.fact[n]*self.ifact[r]) % self.mod
        return (ret*self.ifact[n-r]) % self.mod


n, k = map(int, input().split())
k = min([n-1, k])
MOD = 10**9+7
c = combination(n, MOD)
ans = 0
for i in range(k+1):
    ans += c.choose(n, i) * c.choose(n-1, i)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
k = min(k,n-1)
mod=10**9+7
fact = [1]*(5*10**5+1)
for i in range(2,5*10**5+1):
  tmp = fact[i-1]*i
  tmp%=mod
  fact[i]=tmp
fact_inv = [0]*(5*10**5+1)
for i in range(5*10**5+1):
  fact_inv[i]=pow(fact[i],mod-2,mod)
  
ans=0
def comb(a,b):
  tmp = (fact[a]*fact_inv[a-b]%mod)*fact_inv[b]
  tmp%=mod
  return tmp


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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod


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

mc = ModComb(2 * N)

ans = mc.nCk(2 * N - 1, N - 1)
if K + 1 < N:
    ans += sum((mod - mc.nCk(N, i)) * mc.nCk(N - 1, i) % mod for i in range(K + 1, N)) % mod

print(ans % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
from functools import reduce

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

MOD = 10 ** 9 + 7

def mul(a, b):
  return a * b % MOD

def power(x, y):
  res = 1
  while True:
    if y & 1:
      res = res * x % MOD
    if y == 1:
      return res
    x = x * x % MOD
    y >>= 1

def div(a, b):
  return a * power(b, MOD - 2) % MOD

def dict1():
  return {0: 1}

numer_cache = defaultdict(dict1)
denom_inv_cache = dict1()

def combinations_count(n, r):
  r = min(r, n - r)
  numer_cache_n = numer_cache[n]
  if r not in numer_cache_n:
    numer_cache_n[r] = mul(numer_cache_n[r - 1], n - r + 1)
  if r not in denom_inv_cache:
    denom_inv_cache[r] = div(denom_inv_cache[r - 1], r)
  return mul(numer_cache_n[r], denom_inv_cache[r])

print(sum(mul(combinations_count(n, i), combinations_count(n - 1, i)) for i in range(min(n, k + 1))) % MOD)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

MOD = 10**9 +7

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret *= kaijo(n)
  ret %= MOD;
  ret *= gyaku_kaijo(r)
  ret %= MOD;
  ret *= gyaku_kaijo(n-r)
  ret %= MOD;
  return ret




 
n,k = map(int, input().split())
 
################
#p = 10**9 + 7
#def comb(n,k,p):
#  ans = 1
#  for i in range(1,k+1):
#    ans = ans * (n - (i-1)) % p
#    ans = ans * pow(i, p-2, p)
#  return ans
################
 
if k >= n:
  ans = nCr(2*n-1, n) % MOD
else:
  ans = 0
  for i in range(0,k+1):
    temp = (nCr(n-1, i) % MOD) * (nCr(n, i) % MOD) % MOD
    ans = (ans + temp) % MOD
    
print(ans)

Submission status: Accepted

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 = 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 )
if k>=n:
  k=n-1
ans=0
for i in range(n-k,n+1):
  ans+=cmb(n,i,mod)*cmb(n-1,i-1,mod)
  ans%=mod
if k==1:
  ans=(ans-1+mod)%mod
print(ans)

Submission status: Accepted

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 N - 1 <= K or 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: Accepted

Solution code:
N=2*10**5+3
mod=10**9+7
fac=[1]*(N+1)
for i in range(1,N+1):
    fac[i]=fac[i-1]*i%mod
inv_fac=[1]*(N+1)
inv_fac[N]=pow(fac[N],mod-2,mod)
for i in range(N-1,0,-1):
    inv_fac[i]=inv_fac[i+1]*(i+1)%mod
def nCr(n,r):
    if n<=0 or r<0 or r>n:
        return 0
    return fac[n]*inv_fac[r]%mod*inv_fac[n-r]%mod

n,k=map(int,input().split())
def count(n,x):
    ret=nCr(n,x)*nCr(n-1,n-x-1)%mod
    return ret

ans=0
x=0
if k==1:
    x=1
while x<=k and x<n:
    ans=(ans+count(n,x))%mod
    x+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
from bisect import *
import copy

n,k=map(int,input().split())
mod=10**9+7
fac=[0,1]
for i in range(2,2*n+1):
    fac.append(fac[i-1]*i%mod)
ifac=[pow(i,mod-2,mod) for i in fac]

def comb(a,b):
    if a>=0 and b==0:return(1)
    if a<b or a<0:return(0)

    return((fac[a]*ifac[a-b]*ifac[b])%mod)

count=1
for m in range(1,min(k+1,n)):

    count=(count+comb(n,m)*comb(n-1,n-m-1))%mod
print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    n,k=map(int,input().split())
    
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,n+1)
        fac[0]=fac[1]=1
        finv[0]=finv[1]=1
        inv[1]=1
        for i in range(2,(n+1)):
            fac[i]=fac[i-1]*i%MOD
            inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
            finv[i]=finv[i-1]*inv[i]%MOD
        return fac,finv,inv
    
    fac,finv,inv=COMinit(n,MOD)
    
    def COM(n, k, MOD):
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    
    if k>=n:
        k=n-1
    ans=1
    for i in range(1,k+1):
        ans+=COM(n,i,MOD)*COM(n-1,i,MOD)
        ans%=MOD
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# min(n-1,k)以下の自然数mに対してnCm*n-1Cmの和を求める
n, k = map(int, input().split())
p = 10 ** 9 + 7
g1 = [1, 1]
g2 = [1, 1]

# 先にn!と(n!)^(-1)のリストを作っておく
for i in range(2, 2 * 10 ** 5 + 1):
    g1.append((g1[-1] * i) % p)
    g2.append((g2[-1] * pow(i, p-2, p)) % p)


def cmb(n, r):
    return g1[n] * g2[r] * g2[n - r] % p


ans = 0
for m in range(min(n - 1, k) + 1):
    ans += cmb(n, m) * cmb(n - 1, m) % p
print(ans % p)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	n,k = MI()
	mod = 10**9+7

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

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

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

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

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
mod=10**9+7
n,k=map(int,input().split())
ans=1
coef1=n
coef2=n-1
for i in range(1,min(k+1,n)):
  tmp=1
  tmp*=coef1
  tmp%=mod
  tmp*=coef2
  tmp%=mod
  ans+=tmp
  ans%=mod  
  coef1*=n-i
  coef1%=mod
  coef1*=pow(i+1,mod-2,mod)
  coef1%=mod
  coef2*=n-1-i
  coef2%=mod
  coef2*=pow(i+1,mod-2,mod)
  coef2%=mod
print(ans)

Submission status: Accepted

Solution code:
def e_roaming(MOD=10**9 + 7):
    N, K = [int(i) for i in input().split()]

    class Combination(object):
        """参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb"""
        __slots__ = ['mod', 'factorial', 'inverse']

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

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

            # inv_append(pow(fac[-1], -1, mod)) (after Python 3.8)
            inv_append(pow(fac[-1], mod - 2, mod))

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

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

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

    comb = Combination(N).combination
    if K >= N:
        K = N - 1  # N 回以上移動することは、N-1 回移動することと同じ結果を生む
    return sum(comb(N, k) * comb(N - 1, k) % MOD for k in range(K + 1)) % MOD

print(e_roaming())

Submission status: Accepted

Solution code:
#import time
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())
#start = time.time()
p = 10 ** 9 + 7
N = 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)

#elapsed_time = time.time() - start
#print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

aki = [0] * n
aki[0] = 1
for i in range(1, min(k+1, n)):
    # aki ni suru heya
    aki[i] = cmb(n, i, p)
    # ireru heya
    tmp = fact[n-1]*pow(fact[i], p-2, p)*pow(fact[n - i - 1], p-2, p)
    aki[i] = (aki[i] * tmp) % p
#print(aki)
ans = 0
for a in aki[:k+1]:
    ans = (ans + a) % p
print(ans)
##print(aki)
#for i in range(len(aki)-1):
#    print(aki[i+1]/sum(aki[:i+1]))

Submission status: Accepted

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

MAXN = N+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def comb(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

def nhr(n,r):
    return comb(n+r-1, r)

ans = 0
K = min(K,N-1)
for i in range(K+1):
    ans += comb(N,i) * nhr(N-i,i)
    ans %= MOD
print(ans)

Submission status: Accepted

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())
k = min(n, k)
MOD = 10**9 + 7
fl = [-1]*(n+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**2
    res %= MOD
    fl[i] = res
    return res

if k <= n//2:
  ans = 0
  for i in range(k+1):
    ans += f(i)
    ans %= MOD
else:
  fl[k] = comb(n, k) * comb(n-1, k) % MOD
  ans = 0
  for i in range(k+1, n+1):
    ans += f(i)
    ans %= MOD
  ans = comb(2*n-1, n) - ans
  ans %= MOD

print(ans % MOD)

Submission status: Accepted

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 >= n:
    print(comb(2*n-1,n))
else:
    ans = 0
    for i in range(min(n,k+1)):
        ans += comb(n,i)*comb(n-1,i)
        ans %= mod
    print(ans)

Submission status: Accepted

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

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

N = 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 )



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