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

Submission attempts (in order):
n,k=map(int,input().split())
MOD=10**9+7
ans=1

#Combination 1 O()
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 = 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

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

print(ans&MOD)

n,k=map(int,input().split())
MOD=10**9+7
ans=1
#Combination 1 O()
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 = 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 n-1<=k:
    print(cmb(2*n-1,n,MOD)%MOD)

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

n,k=map(int,input().split())
MOD=10**9+7
ans=1
#Combination 1 O()
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 = 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 n-1<=k:
    print(cmb(2*n-1,n,MOD)%MOD)

else:
    for i in range(1,k+1):
        ans+=(cmb(n,i,MOD)*cmb(n-1,i,MOD))
    print(ans&MOD)

n,k=map(int,input().split())
mod=10**9+7
ans=1
#Combination 1 O()
class Combination:
    
    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):
        
        
        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):
        
        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(10**6)

if n-1<=k:
    print(comb(2*n-1,n)%mod)

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

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted