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:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


class Combination:
    def __init__(self, mod=10**9+7, n=202020):
        self.f = [0] * n
        self.rf = [0] * n
        self.inv = [0] * n
        self.f[0], self.f[1] = 1, 1
        self.rf[0], self.rf[1] = 1, 1
        self.inv[1] = 1
        self.MOD = mod
        for i in range(2, n):
            self.f[i] = (self.f[i - 1] * i) % self.MOD
            self.inv[i] = (-self.inv[self.MOD % i] * (self.MOD // i)) % self.MOD
            self.rf[i] = (self.rf[i - 1] * self.inv[i]) % self.MOD

    def __call__(self, n, r):
        return (self.f[n] * self.rf[r] * self.rf[n - r]) % self.MOD


C = Combination()
n, k = map(int, input().split())
ans = 1
for i in range(1, min(k, n-1)+1):
    tmp = (C(n, i) * C(n-1, i)) % MOD
    ans = (ans + tmp) % MOD

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
p = pow(10,9)+7
li = [1]*(n+2)

counter = 0
k = min(k,n-1)

for a in range(1,n+1):
    li[a] = a*li[a-1]%p

def comb(a,b):
    if b<1:
        return 1
    return li[a]*pow(li[b],p-2,p)*pow(li[a-b],p-2,p)


for i in range(k+1):
    counter += comb(n,i)*comb(n-1,i)%p
    #nCi*  (n-1)Cn-i-1


    #n人をn-iのぐるーぷに分ける

print(counter%p)

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 #出力の制限
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(min(k+1,n+1)):
    ans += cmb(n,i,mod)*cmb(n-1,i,mod)
    ans %= mod
    
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int, input().split())
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= 2*10 ** 5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p) 階乗のmod
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)


#0の数
zeros=min(K, N-1)
ans=1
for i in range(1,zeros+1):
    ans+=(cmb(N,i,p)*cmb(i+N-i-1, i, p))%p
    #print(pow(N-i, i, p))
    ans%=p

print(ans)

Submission status: Accepted

Solution code:
"""
https://www.planeta.tokyo/entry/5195/
"""
def cmb(n, r, p=10**9+7):
    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 = 2*10**5+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)


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

##移動が起きたとして,部屋にいる人数は高々min(N,k)人である

ans = 0
mod = 10**9 + 7
for i in range(1,min(N,k)+1):
    ans += cmb(N,i)*cmb(N-1,i)

print(ans%mod+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
factorial=[1]
for i in range(1,2*n):
  factorial.append((factorial[i-1]*(i+1))%(10**9+7))
inv=[]
for i in range(n):
  inv.append(pow(factorial[i],10**9+5,10**9+7))
if k>=n-1:
  print((factorial[2*n-2]*inv[n-1]*inv[n-2])%(10**9+7))
else:
  ans=1
  for i in range (k):
    ans=(ans+factorial[n-1]*inv[i]*inv[n-i-2]*factorial[n-2]*inv[i]*inv[n-i-3])%(10**9+7)
  if k==1:
    ans-=1
  print(ans)

Submission status: Accepted

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

Solution code:
mod = 10 ** 9 + 7
n, k = map(int, input().split())
binomial = [1]
cum = 1
for i in range(1, n + 2):
    cum *= i
    cum = cum % mod
    binomial.append(cum)
inv = []
tmp = pow(cum, mod - 2, mod)
inv.append(tmp)
for j in range(n + 1, 0, -1):
    tmp = j * tmp % mod
    inv.append(tmp)
inv.reverse()

def comb(n, k):
    return binomial[n] * inv[n - k] % mod * inv[k] % mod if n >= k else 0
k = min(k, n - 1)
ans = 0
for m in range(k + 1):
        tmp = comb(n, m) * binomial[n - 1] * inv[n - 1 - m] * inv[m]
        ans += tmp % mod
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0


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

K = min(K, N - 1)

F = Factorial(N + 1, MOD)

ans = 0
for k in range(K + 1):
    tmp = F.comb(N, k) * F.factorial(N - 1) * F.ifactorial(N - 1 - k) * F.ifactorial(k)
    ans += (tmp % MOD)
    ans %= MOD

print (ans)

Submission status: Accepted

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

MOD = 10 ** 9 + 7
MAX = 4 * 10 ** 5 + 10
modinv = lambda a, mod=MOD: pow(a, mod - 2, mod)
fac, inv = [1] * MAX, [1] * MAX
for i in range(1, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = modinv(fac[i])
comb = lambda n, k: fac[n] * inv[k] * inv[n - k] % MOD

if K >= N - 1:
    print(comb(2 * N - 1, N - 1))
else:
    ans = 0
    for i in range(K + 1):
        ans = (ans + comb(N - 1, N - 1 - i) * comb(N, i)) % MOD
    print(ans)

Submission status: Accepted

Solution code:
def memfact(a,m):
    temp = 1
    yield temp
    for i in range(1,a+1):
        temp = temp * i % m
        yield temp
def comb(n,r,m):
    if r == 0: return 1
    return memf[n]*pow(memf[r],m-2,m)*pow(memf[n-r],m-2,m)

n,k = map(int, open(0).read().split())
dp = [0] * n
dp[0] = 1
m = 1000000007
dp[1] = (n * (n-1)) % m
memf = []
mfappend = memf.append
for x in memfact(n,m):
    mfappend(x)
for i in range(2,min(k+1,n)):
    dp[i] = (dp[i-1]+comb(n,i,m)*comb(n-1,i,m)) % m
print((dp[min(n-1,k)]+1)%m)

Submission status: Accepted

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(min(k+1, n)):
    tmp = c(n,l)*c(n-1, n-l-1)
    ans += tmp%mod
print(ans%mod)

Submission status: Accepted

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

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

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


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

Solution code:
class Combination:
    def __init__(self, mod, max_num):
        self.mod = mod
        self.fac = [0] * max_num
        self.finv = [0] * max_num
        self.inv = [0] * max_num

        self.fac[0], self.fac[1] = 1, 1
        self.finv[0], self.finv[1] = 1, 1
        self.inv[1] = 1

        for i in range(2, max_num):
            self.fac[i] = self.fac[i-1] * i % mod
            self.inv[i] = mod - self.inv[mod % i] * (mod // i) % mod
            self.finv[i] = self.finv[i - 1] * self.inv[i] % mod

    def calc(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


n, k = map(int, input().split())
com = Combination(1000000007, 500000)

ret = 1

min_val = min(n, k)

for i in range(1, min_val+1):
    if i != n:
        ret += com.calc(n, i) * com.calc(n-1, i)
        ret %= 10 ** 9 + 7
    else:
        ret += 0

print(ret)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    #2n-1Cn

    fac1=1
    fac2=1
    facs=[1,1]
    for i in range(2,2*N):
        facs.append(facs[-1]*i%mod)

    # fac1=pow(facs[N],mod-2,mod)
    # fac2=pow(facs[N-1],mod-2,mod)
    # tot=facs[2*N-1]*fac1%mod
    # tot*=fac2
    # tot%=mod
    def comb(N,r):
        fac1=pow(facs[r],mod-2,mod)
        fac2=pow(facs[N-r],mod-2,mod)
        tot=(facs[N]*fac1%mod)*fac2%mod
        return tot
    tot=comb(2*N-1,N)
    if N-1<=K:
        print(tot)
    
    
    else:#0のへやがk+1より多くあるとボツ
        r=0
        for i in range(1,N-(K+1)+1):
            n=N-i
            r+=comb(N,i)*comb(n+i-1,i-1)%mod
            r%=mod
        print((tot-r)%mod)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

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

    mod = 1000000007
    def make_fact(n):
        fact = [1]*(n+1)
        ifact = [1]*(n+1)
        for i in range(1, n+1):
            fact[i] = fact[i-1]*i % mod
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = ifact[i]*i % mod
        return fact, ifact
    fact, ifact = make_fact(n)

    def comb(n, k):
        if k < 0 or k > n: return 0
        return fact[n]*ifact[k]*ifact[n-k] % mod

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

    print(ans)

main()

Submission status: Accepted

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

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

fac = [1]*(n+1)
inv = [1]*(n+1)
for i in range(1,n+1):
  fac[i] = (fac[i-1]*i) % mod  
inv[n] = pow(fac[n], mod-2, mod)
for i in range(n, 0, -1):
  inv[i-1] = (inv[i]*i) % mod
    
def cmb(n, r):
     
  if r < 1:
        return 1
  return (((fac[n] * inv[r])%mod) * inv[n-r]) % mod
 


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

Solution code:
n,k=map(int,input().split())
mod=10**9+7
lim=n
fcl=[1]*(lim+1)
for i in range(1,lim+1):
  fcl[i]=(fcl[i-1]*i)%mod
def comb(x,y,p):
  return ((fcl[x]*pow(fcl[y],p-2,p))%p*pow(fcl[x-y],p-2,p))%p
ans=0
for i in range(min(n,k+1)):
  ans+=comb(n-1,n-i-1,mod)*comb(n,i,mod)
  ans%=mod
print(ans)

Submission status: Accepted

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

f = [ 1 ] * ( n + 1 ) 
inv = [ 1 ] * ( n + 1 )

for i in range( 1, n + 1 ):
  f[ i ] = ( f[ i - 1 ] * i ) % mod
  
inv[ n ] = pow( f[ n ], mod - 2, mod )
for i in range( n, 0, - 1 ):
  inv[ i - 1 ] = ( inv[ i ] * i ) % mod
  
def nCr( n, r ):
  if r < 1:
    return 1
  return ( f[ n ] * inv[ r ] % mod ) * inv[ n - r ] % mod

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

Submission status: Accepted

Solution code:
n, k = map( int, input().split() )
mod = 10 ** 9 + 7
 
numer = [ 1 ] * ( n + 1 )
demon = [ 1 ] * ( n + 1 )
 
for i in range( 1, n + 1 ):
  numer[ i ] = numer[ i - 1 ] * i % mod

demon[ n ] = pow( numer[ n ], mod - 2, mod )
for i in range( n, 0, -1 ):
  demon[ i - 1 ] = ( demon[ i ] * i ) % mod

def nCr( n, r ):
  if r < 1:
    return 1
  return ( numer[ n ] * demon[ r ] % mod ) * demon[ n - r ] % mod
 
ans = 0
for i in range( min( k, n - 1) + 1 ):
  ans = ( ans + nCr( n, i ) * nCr( n - 1, i )) % mod
print( ans )

Submission status: Accepted

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

mod = 10 ** 9 + 7
N = n + 1

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y // 2) ** 2 % mod
    else            : return power(x, y // 2) ** 2 * x % mod

factorial = [1]
for i in range(1, N):
    factorial.append(factorial[i - 1] * i % mod)

inverseFactorial = [0] * N
inverseFactorial[N - 1] = power(factorial[N - 1], mod - 2)
for i in range(N - 2, -1, -1):
    inverseFactorial[i] = inverseFactorial[i + 1] * (i + 1) % mod

def comb(x, y):
    return factorial[x] * inverseFactorial[y] * inverseFactorial[x - y] % mod

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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
mod = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

fac = [0]*(n+1)
fac[0] = 1
fac[1] = 1
for i in range(2,n+1):
    fac[i] = fac[i-1] * i % mod

def combi(n,r,mod=10**9+7):
    return( ( fac[n] * modinv(fac[r]) )%mod * modinv(fac[n-r]) % mod)

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

Submission status: Accepted

Solution code:
def power(a,n):
    x=1
    L=list(format(n,'b'))
    l=len(L)
    for i in range(l):
        if int(L[l-i-1])==1:        
            x=(x*a)%(10**9+7)
        a=(a*a)%(10**9+7)
    return x
n,k=map(int,input().split())
a=1
b=1
y=0
for i in range(n):
    a=(a*(i+1))%(10**9+7)
    b=(b*(2*n-i-1))%(10**9+7)
aa=power(a,10**9+5)
x=(b*aa)%(10**9+7)
if k<n-1:
    c=1
    d=1
    e=1
    f=1
    for i in range(k+1):
        c=(c*(n-i))%(10**9+7)
        d=(d*(i+1))%(10**9+7)
    d=power(d,10**9+5)
    c=(c*d)%(10**9+7)
    for i in range(n-k-2):
        e=(e*(n-1-i))%(10**9+7)
        f=(f*(i+1))%(10**9+7)
    f=power(f,10**9+5)
    e=(e*f)%(10**9+7)
    y=(c*e)%(10**9+7)
    if k+2<=n-1:
        for i in range(k+2,n):
            c=(c*(n-i+1))%(10**9+7)
            d=power(i,10**9+5)
            c=(c*d)%(10**9+7)
            e=(e*(n-i))%(10**9+7)
            f=power(i,10**9+5)
            e=(e*f)%(10**9+7)
            y+=(c*e)%(10**9+7)
            y=y%(10**9+7)
x=x-y
if x<0:
    x=10**9+7+x
print(x)

Submission status: Accepted

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

def createFacArr(n, mod):
    '''
    二項係数計算用の配列の作成

    Parameters
    n : int
        配列のサイズ
    mod : int
        あまり

    Returns
    fac : list
        階乗のリスト
    finv : list
        modの逆元のリスト
    ivn : list
    '''
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, n):
        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

def comb(n ,k, mod, fac, finv):
    '''
    二項係数の計算

    Parameters
    n : int
        元集合
    k : int
        元集合から選択する数
    mod : int
        あまり
    fac : list
        階乗のリスト
    finv : list
        逆元のリスト
    
    Returns
    c : int
        nCkの組み合わせの数
    '''
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

K = min(N-1, K)
ans = 0
MOD = 10 ** 9 + 7
fac, finv = createFacArr(N+100, MOD)

for i in range(K+1):
    # iは0の個数
    ans += comb(N, i, MOD, fac, finv) * comb(N-1, N-i-1, MOD, fac, finv) % MOD
    ans %= MOD
print(ans)

Submission status: Accepted

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

    # 0人部屋が0~k個の時の場合の数の和
    # Σ(i=[0,k]){comb(n,i)*pow((n-i),i)} を求めれば良い
    # しかし上式ではpowの計算量がデカすぎるので、捉え方を変えて下式まで変形
    # Σ(i=[0,k]){comb(n,i)*comb((n-1),i)} を求めれば良い
    # 注:i=0のとき、つまり0人部屋がない、つまり全部屋に1人ずつ、のケースは1通り
    # comb(n,i+1) = comb(n,i) * (n-i)/(i+1) であることを利用する
    ans = 0
    k1 = 1
    k2 = 1
    for i in range(min(k+1,n)):
        ans += k1*k2
        ans %= MOD
        k1 *= (n-i)*pow(i+1,MOD-2,MOD)
        k1 %= MOD
        k2 *= (n-1-i)*pow(i+1,MOD-2,MOD)
        k2 %= MOD
    print(int(ans))

main()

Submission status: Accepted

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

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

comb = Combination(5*10**5)

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): 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 LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

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 = MOD #出力の制限
N = 5*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 )

N,K = MI()
ans = cmb(2*N-1,N-1,MOD)
if K<N-1:
    for i in range(K+1,N):
        ans -= cmb(N,i,MOD)*cmb(N-1,i,MOD)
print(ans%MOD)

Submission status: Accepted

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

fac = [1]*(n+1)
inv = [1]*(n+1)
for i in range(1,n+1):
  fac[i] = (fac[i-1]*i) % mod  
inv[n] = pow(fac[n], mod-2, mod)
for i in range(n, 0, -1):
  inv[i-1] = (inv[i]*i) % mod
    
def nCr(n,r):  
  if r < 1:
    return 1
  return (((fac[n] * inv[r])%mod) * inv[n-r]) % mod

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

print(ans)

Submission status: Accepted

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

#nCrをmodで割った余りを求める。Nに最大値を入れて使用。
N = n
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
def cmb(n,r,mod):
    if r<0 or r>n :
        return 0
    r = min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod
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
for i in range(min(n-1,k)+1):
    di = cmb(n,i,mod)*cmb(n-1,i,mod)%mod
    ans = (ans+di)%mod

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
mi = min(n-1,k)
di = 10**9+7
def pow_k(x,i):
    if i==0:
        return 0
    K=1
    while i>1:
        if i % 2 != 0:
            K = (K*x)%di
        x = (x*x)%di
        i //= 2

    return (K * x)%di

lis = [i for i in range(n+1)]
lisr = [i for i in range(n+1)]
lis[0]=1
for i in range(1,n+1):
    lis[i]=(lis[i-1]*lis[i])%di
    lisr[i] = pow_k(lisr[i],di-2)

lisr[0]=1
for i in range(1,n+1):
    lisr[i]=(lisr[i-1]*lisr[i])%di

#print(lis,lisr)

su = 1
for i in range(1,mi+1):
    pl = ((((lis[n-1]*lisr[i])%di)*lisr[n-1-i])%di)
    plu = (pl*((((lis[n]*lisr[i])%di)*lisr[n-i])%di))%di
    su+=plu
    su%=di
print(su)

Submission status: Accepted

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

mod = 10 ** 9 + 7

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

ans = 0
for i in range(min(n-1, k) + 1):
    com1 = fact[n] * fact_inv[i] * fact_inv[n-i] % mod
    com2 = fact[n-1] * fact_inv[i] * fact_inv[n-i-1] % mod
    mul = com1 * com2 % mod
    ans = (ans + mul) % mod

print(ans)

Submission status: Accepted

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

mod = 10 ** 9 + 7
'''
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
for i in range(2, n+1):
    fac.append(fac[-1] * i % mod)
    inv.append(-inv[mod%i] * (mod // i) % mod)
    finv.append(finv[-1] * inv[-1] % mod)
'''
fac = [1]
finv = [0]*(n+4)
for i in range(n+3):
    fac.append(fac[-1]*(i+1)%mod)

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

ans = 0
for i in range(min(n-1, k) + 1):
    com1 = fac[n] * finv[i] * finv[n-i] % mod
    com2 = fac[n-1] * finv[i] * finv[n-i-1] % mod
    mul = com1 * com2 % mod
    ans = (ans + mul) % mod

print(ans)

Submission status: Accepted

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

mod = 10 ** 9 + 7

fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
for i in range(2, n+1):
    fac.append(fac[-1] * i % mod)
    inv.append(-inv[mod%i] * (mod // i) % mod)
    finv.append(finv[-1] * inv[-1] % mod)

ans = 0
for i in range(min(n-1, k) + 1):
    com1 = fac[n] * finv[i] * finv[n-i] % mod
    com2 = fac[n-1] * finv[i] * finv[n-i-1] % mod
    mul = com1 * com2 % mod
    ans = (ans + mul) % mod

print(ans)

Submission status: Accepted

Solution code:
SIZE=4*10**5+1; 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
 
def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
 
def chofuku(ball,box): # nHk mod MOD の計算
    return choose(box+ball-1,box)



N,K=map(int,input().split())
ans=0
for i in range(min(N,K+1)):
    ans+=choose(N,i)*chofuku(N-i,i)%MOD

print(ans%MOD)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,K = LI()
    f = [1]
    r = [1]

    s = 1
    for i in range(1,N+2):
        s = (s * i) % MOD
        f.append(s)
        r.append(pow(s,MOD-2,MOD))


    def comb(a,b):
        return f[a] * r[b] * r[a-b]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
mod=pow(10,9)+7
# max:comb(2*n-1,n-1)

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1]
for i in range( 2, 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-1:
  print(cmb(2*n-1,n-1,mod))
else:
  ans=0
  for i in range(k+1):
    ans+=cmb(n,i,mod)*cmb(n-1,i,mod)
    ans%=mod
  print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
mod = 10**9 + 7
def setFact(n, mod):
    global fact
    fact = [1]
    global ifact
    ifact = [1] * (n+1)
    for i in range(1, n+1):
        fact.append(fact[i-1]*i%mod)
    ifact[-1] = pow(fact[-1], mod-2, mod)
    for i in range(2, n+2):
        ifact[-i] = ifact[-i+1]*(n-i+2) %mod
def combination(n, k , mod):
    global fact
    global ifact
    if k < 0 or k > n:
        return 0
    else:
        return fact[n] * ifact[n-k] * ifact[k] % mod
setFact(n, mod)
ans = 0
for i in range(min(n+1, k+1)):
    ans += combination(n,i,mod) *combination(n-1,i, mod) %mod
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7

@lru_cache(None)
def combination(n, k):
    if k == 0:
        return 1
    else:
        return ((combination(n, k-1) * (n-k+1) % MOD) * pow(k, MOD-2, MOD)) % MOD

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

s = 0
for m in range(0, min(k+1, n)):
    s += combination(n, min(m, n - m)) * combination(n - 1, min(m, n - m - 1))
    s %= MOD

print(s)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
n,k = map(int,input().split())
MOD = 10**9 + 7
def comb(n, k, mod):
    if n<0 or k<0 or n<k:
        return 0
    if n==0 or k==0:
        return 1
    k=k if k<=n-k else n-k
    x = 1
    y = 1
    for i in range(k):
        x=x*(n-i)%mod
        y=y*(i+1)%mod
    return (x*pow(y,mod-2,mod))%mod
#こっちは計算量O(N)
fac = [1, 1]
inv = [0, 1]
finv = [1, 1]
for i in range(2, 2*n+1):
    fac.append(fac[-1] * i % MOD)
    inv.append(MOD - inv[MOD%i] * (MOD//i) % MOD)
    finv.append(finv[-1] * inv[-1] % MOD) 
def comb_mod(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m
if k >= n-1:
    ans = comb_mod(2*n-1,n,MOD)
    print(ans%MOD)
elif k == 1:
    print(n*(n-1)%MOD)
else:
    ans = 0
    for i in range(k+1):
        ans += comb_mod(n-1,i,MOD)*comb_mod(n,i,MOD)
    print(ans%MOD)