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

Submission status: Accepted

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

mod = 10 ** 9 + 7 # (modの値をすごく大きくすれば（5乗とか）、普通のnCrとして使える)
MAX = 2 * (10 ** 5) + 1 # これは変動するので注意。せいぜい10 ** 6くらいまでがTLEの限界

def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, 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
    return fac, finv

fac, finv = com_init(MAX, mod)

def nCr(n, r):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def nHk(n, k):
    '''
    Duplicated Combination
    '''
    return nCr(n - 1 + k, n - 1)

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))

    comb1 = [0] * (n + 1)
    comb2 = [0] * (n + 1)

    comb1[0] = 1
    comb2[0] = 1

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

    r = min(k, n - 1)
    ans = 0
    for i in range(r + 1):
        ans += comb1[n - i] * comb2[n - 1 - i]
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def make_array_for_comb(N, mod=10**9+7):
    fact = [1,1]
    fact_inv = [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)
        fact_inv.append((fact_inv[-1]*inv[i]) % mod)
    return fact, fact_inv

def comb(n, r, mod=10**9+7):
  if (r < 0) or (n < r):
      return 0
  r = min(r, n - r)
  return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

n,k = [int(i) for i in input().split()]
mod = 10**9+7
fact, fact_inv = make_array_for_comb(n,mod)
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: Accepted

Solution code:
import sys
input = sys.stdin.readline
# int(input()) # 入力が1つ
n, k = map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字
mod = 10 ** 9 + 7 # (modの値をすごく大きくすれば（5乗とか）、普通のnCrとして使える)
MAX = 2 * 10 ** 5 + 1 # これは変動するので注意。せいぜい10 ** 6くらいまでがTLEの限界

def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, 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
    return fac, finv

fac, finv = com_init(MAX, mod)

def nCr(n, r):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def nHk(n, k):
    '''
    Duplicated Combination
    '''
    return nCr(n - 1 + k, n - 1)

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

Submission status: Accepted

Solution code:
class FastModComb:

    def __init__(self, n, mod=10 ** 9 + 7):
        f, self.mod = [1], mod
        for i in range(1, n + 1):
            f.append(f[-1] * i % mod)
        rf = [self.modpow(f[-1], mod - 2)]
        for i in range(1, n + 1):
            rf.append(rf[-1] * (n - i + 1) % mod)
        self.f, self.rf = f, list(reversed(rf))

    def modpow(self, a, b):
        ret = 1
        while b > 0:
            if b % 2 == 1:
                ret = ret * a % self.mod
            a = a * a % self.mod
            b //= 2
        return ret

    def modcomb(self, n, c):
        return self.f[n] * self.rf[c] * self.rf[n - c] % self.mod


n, k = map(int, input().split())
mod, mc = 10 ** 9 + 7, FastModComb(n)
print(sum([mc.modcomb(n, m) * mc.modcomb(n - 1, n - m - 1) % mod
           for m in range(min(n - 1, k) + 1)]) % mod)

Submission status: Accepted

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):
        p = pow(i,M-2,M)
        c1 = c1*(n+1-i)*p%M
        c2 = c2*(n-i)*p%M
        y += c1*c2%M
        # y = (y+c1*c2)%M
print(y%M)

Submission status: Accepted

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

for i in range(min(n, k+1)):
  ans += c1 * c2
  c1 *= (n-i) * pow(i+1, mod-2, mod)
  c1 %= mod
  c2 *= (n-i-1) * pow(i+1, mod-2, mod)
  c2 %= mod

print(ans%mod)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

def main():
    n, k = map(int,input().split())
    MOD = 10 ** 9 + 7
    comb = Combination(10 ** 6)
    ans = 0
    if n - 1 <= k:
        ans = comb(n + n - 1, n)
    else:
        ans = 1
        for i in range(1,k+1):
            ans += comb(n,i) * comb(n - 1, i)
            ans %= MOD
    
    print(ans)


    




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

class Factorial:
    def __init__(self,MOD):
        self.MOD = MOD
        self.factorials = [1,1] # 階乗を求めるためのキャッシュ
        self.invModulos = [0,1] # n^-1のキャッシュ
        self.invFactorial_ = [1,1] # (n^-1)!のキャッシュ

    def calc(self,n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0]*(n+1-len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI,n+1):
            prev = nextArr[i-initialI] = prev * i%m
        self.factorials += nextArr
        return self.factorials[n]
    
    def inv(self,n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit() 
        p = self.MOD
        pi = n%p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0]*(n+1-len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI,min(p,n+1)):
            next = -self.invModulos[p%i]*(p//i)%p
            self.invModulos.append(next)
        return self.invModulos[pi]
    
    def invFactorial(self,n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit() 
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n) # To make sure already calculated n^-1
        nextArr = [0]*(n+1-len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI,n+1):
            prev = nextArr[i-initialI] = (prev * self.invModulos[i%p])%p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]


class Combination:
    def __init__(self,MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)
    
    def choose_k_from_n(self,n,k):
        if k < 0 or n < k:
            return 0
        k = min(k,n-k)
        f = self.factorial
        return f.calc(n)*f.invFactorial(max(n-k,k))*f.invFactorial(min(k,n-k))%self.MOD


def solve(n: int, k: int):
    c = Combination(MOD)
    sum = 0
    for i in range(min(n,k+1)-1,-1,-1):
        c1 = c.choose_k_from_n(n,i)
        c2 = c.choose_k_from_n(n-1,i)
        sum = (sum + c1*c2)%MOD
    print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
def inv(a,m=10**9+7):
    b=m
    (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 % m

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

ans=0
for i in range(k+1):
    tmp=inv(frac[i]**2%mod*frac[n-i]*frac[n-1-i]%mod)
    ans+=tmp
    ans%=mod
ans=ans*frac[n]*frac[n-1]%mod
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
mod = 10**9+7
g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1]
for i in range(2, n+1):
    g1.append((g1[-1] * i) % mod)
    inv.append((-inv[mod%i] * (mod//i)) % mod)
    g2.append((g2[-1] * inv[-1]) % mod)

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

li = []
for i in range(min(k, n-1)+1):
    li.append(comb(n-1, i))
ans = 0
pre = 0
for cur in li:
    ans += (pre+cur)*cur
    pre = cur
print(ans%mod)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

mod = 10**9+7
MOD = 10 ** 9 + 7
MAX = 2*n+1


fact = [1] * (MAX + 1)  # i!
finv = [1] * (MAX + 1)  # (i!)^{-1}
iinv = [1] * (MAX + 1)  # i^{-1}

for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


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


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

if k == 1:
    print(ans % mod)

else:
    print((ans+1) % mod)

Submission status: Accepted

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

    def pre(n,MOD):
        a=1
        for i in range(1,n+1):
            a=(a*i)%MOD
        an=a
        b=pow(a,MOD-2,MOD)
        bs=[1]*(n+1)
        bs[n]=b
        for i in range(n,1,-1):
            b=b*i%MOD
            bs[i-1]=b
        return an,bs

    a,b=pre(n-1,MOD)
    ans=1
    for i in range(1,min(n-1,k)+1):
        s=(a*n*b[i])%MOD
        s=(s*b[n-i])%MOD
        s=(s*a*b[n-i-1])%MOD
        s=(s*b[i])%MOD
        ans+=s
        ans%=MOD
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

##逆元計算
N = n  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

fact = [ 0 for i in range(N+1)]
factinv = fact.copy()
inv = fact.copy()


fact[0], fact[1] = 1, 1
factinv[0], factinv[1] = 1, 1
inv[0], inv[1] = 0, 1
cmb_list = fact.copy()
cmb_list_sub1 = fact.copy()

for i in range(2, N + 1):
    fact[i] = (fact[i-1] * i) % p##階乗のリスト
    inv[i] = (-inv[p % i] * (p // i)) % p
    factinv[i] =(factinv[i-1] * inv[i]) % p##階乗の逆数のリスト
    
#nCrの0=< r <=n までの値のリストがほしい場合
for r in range(1,N+1):
    cmb_list[r] = fact[N] * factinv[r] * factinv[N-r] % p

for r in range(1, n):
    cmb_list_sub1[r] =fact[n-1]*factinv[r]*factinv[n-1-r]%p

ans = 0
if k <= n-1:
    for i in range(0,k+1):
        ans = (ans + cmb_list[i] * cmb_list_sub1[n-1-i])%p
else:
    for i in range(0,n):
        ans = (ans + cmb_list[i] * cmb_list_sub1[n-1-i])%p
print(ans)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

def factorial(n):
    global fct
    global invfct
    fct = [0] * (n + 1)
    fct[0] = 1
    for i in range(1, n+1):
        fct[i] = fct[i-1] * i % MOD
    invfct = [0] * (n + 1)
    invfct[n] = pow(fct[n], MOD - 2, MOD)
    for i in range(n-1, -1, -1):
        invfct[i] = invfct[i+1] * (i + 1) % MOD

def binomial(n, k):
    return fct[n] * invfct[n-k] % MOD * invfct[k] % MOD

factorial(2 * n)

if k >= n:
    print(binomial(2 * n - 1, n) % MOD)
else:
    answer = 0
    for i in range(k+1):
        answer += binomial(n, i) * binomial(n-1, i)
        answer %= MOD
    print(answer)

Submission status: Accepted

Solution code:
N,K=map(int, raw_input().split())
 
mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1,N+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod

can_zero_num=min(N-1,K)
ans=0
for zero_num in range(can_zero_num+1):
    ans+=ncr(N,zero_num)*ncr(N-1,N-zero_num-1)

print ans%mod

Submission status: Accepted

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

k=min(k,n-1)
t,c,h=1,1,1
for i in range(1,k+1):
  p=pow(i,m-2,m)
  c=(c*(n-i+1)* p)%m
  h=(h*(n-i)  * p)%m
  t=(t+c*h)%m

print(t%m)

Submission status: Accepted

Solution code:
# 組み合わせ①
# nCk % MOD
# n固定でないとき
# 前処理O(MAX)、計算O(1)

MOD = 10 ** 9 + 7
MAX = 200010
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX
def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, 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 COM(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
COMinit()

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

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

Submission status: Accepted

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

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

def nCk(n,k):
    return fac[n]*inv[k]%mod*inv[n-k]%mod
ans = 0
for i in range(min(k+1,n)):
    ans += nCk(n,i)*nCk(n-1,i)%mod
    ans %=mod
print(ans)

Submission status: Accepted

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

fact = [1]*(U+1)
fact_inv = [1]*(U+1)

for i in range(1,U+1):
  fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U],MOD-2,MOD)

for i in range(U,0,-1):
	fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n,k):
  if k < 0 or k > n:
    return 0
  x = fact[n]
  x *= fact_inv[k]
  x %= MOD
  x *= fact_inv[n-k]
  x %= MOD
  return x

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

Submission status: Accepted

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


# Start template
# This template is from https://atcoder.jp/contests/abc156/submissions/10279810.
# Thank you Mr./Ms.convexineq.

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)

# End template



ans = 0
MAX = min(k,n- 1)
for i in range(0,MAX + 1):
    # print(choose(n,i) * chofuku(n-i,n))
    ans += choose(n,i) * chofuku(n - i ,i)
    ans %= MOD
    # print(ans)
print(ans % MOD)

Submission status: Accepted

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

def init_mod_c(lim=10**6, mod=10**9+7):
    fact = [1, 1] + [0] * (lim-1)
    fact_inv = [1, 1] + [0] * (lim-1)
    inv = [0, 1] + [0] * (lim-1)
    
    for i in range(2, lim+1):
        fact[i] = fact[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod

    def mod_c(n, m):
        if n < m or n < 0 or m < 0: return 0
        return fact[n] * (fact_inv[m] * fact_inv[n-m] % mod) % mod

    return mod_c

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

Submission status: Accepted

Solution code:
mod = 10**9+7
n,k = map(int,input().split())
ans = 0
mod = 10**9 + 7
inv_t = [0,1]
for i in range(2,n+2):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]
a = n
b = n-1
for i in range(1,min(n,k)+1):
    ans += a*b % mod
    a = a*(n-i)*inv_t[i+1] % mod
    b = b*(n-i-1)*inv_t[i+1] % mod
    ans %= mod
if k > 1:
    ans += 1
print(ans % mod)

Submission status: Accepted

Solution code:
MOD = 1000000007  # type: int
 
def solve(n: int, k: int):
    fact = [1] * (n+1)
    inv_fact = [1] * (n+1)
    for i in range(1, n+1):
        fact[i] = i*fact[i-1] % MOD
 
    inv_fact[-1] = pow(fact[-1], MOD-2, MOD)
    for i in range(n-1, 0, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
 
    def comb(n, r, MOD=MOD):
        return fact[n] * inv_fact[n-r] * inv_fact[r] % MOD
    
    ans = 0
    for i in range(min(k, n-1)+1):
        ans += comb(n, i) * comb(n-1, i) % MOD
        ans %= MOD
 
    return ans

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

print(solve(n, k))

Submission status: Accepted

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

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

'''
ここは任意
'''

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

#  これは計算量rでncr mod p を求められる。
def combination2(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

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

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

Submission status: Accepted

Solution code:
from sys import stdin



def prepare(n, p):
    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)
    return fact, factinv


def cmb(n, r, p, 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 get_result(data):
    n, k = data
    mod = 10**9+7
    fact, factinv = prepare(n, mod)
    ans = 0
    for m in range(n):
        # xHy = x+y−1Cx−1
        if m <= k:
            ans += (cmb(n, m, mod, fact, factinv) * cmb(n-1, n-m-1, mod, fact, factinv)) % mod
    ans %= mod
    return ans

if __name__ == '__main__':
    data = list(map(int, stdin.readline().split(' ')))
    result = get_result(data)
    print(result)

Submission status: Accepted

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

k = min([k, n-1])


ans = 0
key = 1

for i in range(k+1):
    ans += key
    ans %= mod
    key = (((key*(n-i)%mod)*(n-i-1)%mod)*pow(pow(i+1, mod-2, mod), 2, mod))%mod
print(ans)

Submission status: Accepted

Solution code:
MAX = 4*10**5
bikkuri=[1]
mod = 10**9+7
for i in range(1,MAX+1):
    bikkuri.append((bikkuri[-1]*i)%mod)

def Comb(n,k):
    ans = bikkuri[n]*pow(bikkuri[k],mod-2,mod)*pow(bikkuri[n-k],mod-2,mod)
    ans %=mod
    return ans
    
n,k = map(int,input().split())
if n-1 <= k:
    ans = Comb(2*n-1,n)
    print(ans)
else:
    tmp = 0
    for i in range(k+1):
        tmp += Comb(n,i)*Comb(n-1,i)
        tmp %= mod
    print(tmp)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
n,k = map(int,readline().split())
mod = 10**9+7
def pow(n,p,mod=10**9+7): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod
def factrial_memo(n=10**6+1,mod=10**9+7):
    fact = [1, 1]
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % mod)
    return fact
def fermat_cmb(n, r, mod=10**9+7): #needs pow,factrial_memo(only fact). return nCk
    return fact[n] * pow(fact[r],mod-2) * pow(fact[n-r],mod-2) %mod
fact = factrial_memo()

if k > n-1: #全通りの再現が可能ならば
    ans = fermat_cmb(2*n-1,n)
else: #移動回数の制限によって全通りの再現ができないならば
    ans = 1
    for i in range(1,k+1): #全ての動作を再現する(kはたかだか2*10**5である)
        ans += fermat_cmb(n,i)*fermat_cmb(n-1,i)
        #n人の中から動かせる人物をi人取り、n-1箇所(それぞれの人物に付き同じ場所には戻れない)
        #にi人を入れる組み合わせ。それぞれの事象に付き、0人になる部屋と他の部屋の人数は
        #必ず違う組み合わせになるので、これをk回だけ繰り返せば良い
        ans %= mod

print(ans)

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
mod=10**9+7
def bp(a,n):
        r=1
        while(n):
           if n%2:
              r=r*a%mod
           a=a*a%mod
           n>>=1
        return r
[n,k]=i2()
if n<=k:
   x=1
   for i in range(n-1):
      x*=2*n-1-i
      x%=mod
   y=1
   for i in range(n-1):
      y*=i+1
      y%=mod
   print((x*bp(y,10**9+5))%mod)   
   
else:
   x=1
   y=1
   t=1
   for i in range(k):
      t*=i+1
      t%=mod
      y*=n-1-i
      y%=mod
      y*=n-i
      y%=mod
      c=bp(t,10**9+5)
      x+=y*c*c
      x%=mod
   print(x)

Submission status: Accepted

Solution code:

import numpy as np

class Combination : 
    def __init__ (self, N=10**6, mod=10**9+7) :
        self.mod = mod
        self.fact = [1, 1]
        self.factinv = [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.factinv.append( (self.factinv[-1] * self.inv[-1]) % mod )

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

    def nPr(self, n, r) :
        if ( r < 0 ) or ( n < r ) : return 0
        return self.fact[n]*self.factinv[n-r] % self.mod


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

mod = 10**9+7
comb = Combination(2*10**5+100)
ans = 0
for m in range(min(n+1,k+1)) :
    ans = ans%mod + (comb.nCr(n,m) * comb.nCr(n-1, n-m-1))%mod
print(ans%mod)

Submission status: Accepted

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

class Combination:
    def __init__(self, N=10**6, mod=10**9 + 7):
        self.mod = mod
        self.N = N
        self.fact = [1, 1]  # fact[n] = (n! mod p)
        self.factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
        self.inv = [0, 1]  # factinv 計算用
        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.factinv.append((self.factinv[-1] * self.inv[-1]) % mod)

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

comb = Combination(2 * 10**5+100)
ans = 0
mod = 10**9 + 7
for ki in range(min(n+1, k+1)):
    ans = ans % mod + (comb.nCr(n, ki) * comb.nCr(n-1, n-ki-1)) % mod
print(ans%mod)

Submission status: Accepted

Solution code:
n,k = [int(x) for x in input().split()]
mod = 10**9+7
MAX_N = 10**6
 
fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1] = pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
    fact_inv[i] = fact_inv[i+1]*(i+1)%mod
 
 
def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod
if k>=n:
  print(mod_comb_k(2*n-1,n,mod))
else:
  res=1
  for i in range(1,k+1):
    res = (res+mod_comb_k(n,i,mod)*mod_comb_k(n-1,n-i-1,mod))%mod
  print(res)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
MOD_t_MAX = 2*(10**5)+1

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_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 MOD_COM(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
def MOD_pow(a, n):
    res = 1
    while n > 0:
        if (n & 1):
            res = res * a % MOD
        a = a * a % MOD
        n = n // 2
    return res

def main():
    n, k = map(int, input().split())
    MOD_COM_init()
    ans = 0
    for i in range(n):
        if k-i < 0:
            continue
        x = MOD_COM(n, i) * MOD_COM(n-1, n-i-1) % MOD
        ans += x
        ans %= MOD
    print(ans)
if __name__ == "__main__":
    main()