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 io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


def prepare(n, mod=pow(10, 9) + 7):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= mod
        factorials.append(f)
    inv = pow(f, mod - 2, mod)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= mod
        invs[m - 1] = inv

    return factorials, invs


# 実装を行う関数
def resolve(test_def_name=""):
    n, k = map(int, input().split())

    # 逆数を求める
    fns, invs = prepare(pow(10, 6))

    # 計算
    ans = 0
    for i in range(1, min(n - 1, k) + 1):
        # (fns[n] * invs[i] * invs[n - i]) 0の部屋パターン数
        # (fns[n - 1] * invs[i] * invs[n - 1 - i])  移動先数(重複組み合わせで求める。)
        ans += (fns[n] * invs[i] * invs[n - i]) * (fns[n - 1] * invs[i] * invs[n - 1 - i]) % (pow(10, 9) + 7)
        ans = ans % (pow(10, 9) + 7)

    # ALL1のパターンを考慮して+1した結果を出力。
    print(ans + 1)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 2"""
        output = """10"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """200000 1000000000"""
        output = """607923868"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """15 6"""
        output = """22583772"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
class Factorial:
    def __init__(self, max_fact, mod):
        #mod should be prime number
        #using homogeneous_product(n,r), max_fact ≧ max(n+r-1)
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        if mod > max_fact:
            fi = [pow(f[-1], mod - 2, mod)]
            for idx in range(max_fact, 0, -1):
                fi += [fi[-1] * idx % mod]
            fi = fi[::-1]
        else:
            fi = [pow(n, mod - 2, mod) for n in f]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = 4 * 10**5 + 100
mod = 10**9 + 7
fact_instance = Factorial(max_fact, mod)
comb_repl = fact_instance.homogeneous_product
comb = fact_instance.combination

N, K = [int(_) for _ in input().split()]
ans = 0
for r in range(min(N - 1, K) + 1):
    ans += comb(N, r) * comb_repl(N - r, r)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n,k=map(int,input().split())

Mod=10**9+7
M=2*10**5 +1#書き換え

fac=[0]*M
finv=[0]*M
inv=[0]*M

#finvに逆元、facに階乗のmod
def COMinit():
  fac[0]=fac[1]=1
  finv[0]=finv[1]=1
  inv[1]=1
  for i in range(2,M):
    fac[i]=(fac[i-1]*i%Mod)%Mod
    inv[i]=Mod-inv[Mod%i]*(Mod//i) %Mod
    finv[i]=(finv[i-1]*inv[i]%Mod)%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)%Mod

COMinit()
if n>k:
    ans=1
    for i in range(1,k+1):
        ans+=(COM(n,i)*COM(n-1,i))%Mod
        ans%=Mod
else:
    ans=1
    for i in range(1,n):
        ans+=(COM(n,i)*COM(n-1,i))%Mod
        ans%=Mod
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


def solve():
    N, K = Scanner.map_int()

    MOD = int(1e09) + 7
    MAX = 200010
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = finv[0] = finv[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 cmb(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

    ans = 0
    for m in range(0, min(K, N - 1) + 1):
        a = cmb(N, m)
        b = cmb(N - 1, m)
        ans += a * b
        ans %= MOD
    print(ans)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0


class ModFactorial:
    """
    階乗, 組み合わせ, 順列の計算
    """

    def __init__(self, n, MOD=10 ** 9 + 7):
        """

        :param n: 最大の要素数.
        :param MOD:
        """
        kaijo = [0] * (n + 10)
        gyaku = [0] * (n + 10)

        kaijo[0] = 1
        kaijo[1] = 1
        for i in range(2, len(kaijo)):
            kaijo[i] = (i * kaijo[i - 1]) % MOD
        gyaku[0] = 1
        gyaku[1] = 1
        for i in range(2, len(gyaku)):
            gyaku[i] = pow(kaijo[i], MOD - 2, MOD)
        self.kaijo = kaijo
        self.gyaku = gyaku
        self.MOD = MOD

    def nCm(self, n, m):
        return (self.kaijo[n] * self.gyaku[n - m] * self.gyaku[m]) % self.MOD

    def nPm(self, n, m):
        return (self.kaijo[n] * self.gyaku[n - m]) % self.MOD

    def factorial(self, n):
        return self.kaijo[n]


mf = ModFactorial(N, MOD)
for i in range(1, N + 1):
    if N - i > K: continue

    p = N - i
    # print(i, p, mf.nCm(p + i - 1, i - 1))
    ans += mf.nCm(p + i - 1, i - 1) * mf.nCm(N, i)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
MOD = 10**9 + 7
MAX_N = 10**6 + 5
fact = [0]*(MAX_N)
fact_inv = [0]*(MAX_N)
fact[0] = 1
for i in range(MAX_N-1):
    fact[i+1] = fact[i]*(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 comb(n, k):
    return fact[n]*fact_inv[k] % MOD * fact_inv[n-k] % MOD


if K >= N:
    print(comb(2*N-1, N-1))
    exit()

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

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    COM_MAX = n

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1

    for i in range(2, COM_MAX + 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

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

    ans = 0
    for r in range(min(n, k + 1)):
        ans = (ans + com(n, r) * com(n - 1, r)) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,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 f(n,k,mod):
  return fact[n]*fact_inv[k]%mod*fact_inv[n-k] %mod

ans=0
#0人の部屋はmaxいくつできるか
a=min(k,n-1)
ans=0
for i in range(a+1):
  d=f(n,i,mod)*f(n-1,i,mod)
  #print(i,d)
  ans+=d%mod
  ans%=mod

print(ans)

Submission status: Accepted

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

mod=10**9+7

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

ans=1
comb1=1
comb2=1

for i in range(1,min(n-1,k)+1):
    comb1*=(n-i+1)*modinv(i)
    comb2*=(n-i)*modinv(i)
    comb1%=mod
    comb2%=mod

    ans+=comb1*comb2
    ans%=mod

print(ans)

Submission status: Accepted

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

list_size = 4*10**5 + 1
 
f_list = [1] * list_size
f_r_list = [1] * list_size
 
for i in range(list_size-1):
	f_list[i+1] = (f_list[i] * (i+1)) % mod
 
f_r_list[-1] = pow(f_list[-1], mod - 2, mod)
 
for i in range(list_size-2, -1, -1):
	f_r_list[i] = (f_r_list[i+1] * (i+1)) % mod
 
def comb(n, r, mod):
	if n < r or r < 0:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (f_list[n] * f_r_list[n-r] * f_r_list[r]) % mod


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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

lim = 10 ** 6 + 1
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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

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

N, K = getNM()

ans = 0
for i in range(min(K + 1, N)):
    # 0の場所を選ぶ通り * 重複組み合わせ
    cnt = cmb(N, i) * cmb(N - i + i - 1, i)
    ans += cnt
    ans %= mod
print(ans % mod)

Submission status: Accepted

Solution code:
def cmb(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


mod = 10**9+7
N = 10**6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


MOD = int(1e09) + 7
# INF = int(1e15)


def solve():
    MAX = 2 * 10 ** 5 + 10
    fac = [0] * MAX
    inv = [0] * MAX
    finv = [0] * MAX
    fac[0] = fac[1] = finv[0] = finv[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 cmb(n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
    N, K = Scanner.map_int()
    ans = 0
    for i in range(min(N - 1, K) + 1):
        ans += cmb(N, i) * cmb(N - 1, i)
        ans %= MOD
    print(ans)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

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

fact = [0] * (n+1)
inv_fact = [0] * (n+1)

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

inv_fact[n] = pow(fact[n], MOD-2, MOD)
for i in range(n, 0, -1):
    inv_fact[i-1] = inv_fact[i] * i % MOD


def nCk(n, k):
    return fact[n] * inv_fact[k] * inv_fact[n-k] % MOD
  
ans = 1
for i in range(1, n):
    if i > k:
      break
    ans += nCk(n, i) * nCk(n-1, n-i-1) % MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class CmbMod:
    def __init__(self, n, p):
        """
        二項係数nCr(n個の区別できるものからr個のものを選ぶ組み合わせの数)をpで割った余りを求める
        """
        self.n = n
        self.p = p
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]

    def cmb_mod(self, n, r):
        """
        二項係数nCr(mod p)をO(r)にて計算。nが大きいがrは小さい時に使用。
        """
        numer, denom = 1, 1
        for i in range(r):
            numer = (numer * (n - i)) % self.p
            denom = (denom * (i + 1)) % self.p
        return (numer * pow(denom, self.p - 2, self.p)) % self.p

    def prep(self):
        """
        二項係数nCr(mod p)をO(1)で求める為の前処理をO(N)にて実行。
        """
        for i in range(2, self.n + 1):
            self.fact.append((self.fact[-1] * i) % self.p)
            self.inv.append((-self.inv[self.p % i] * (self.p // i)) % self.p)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % self.p)

    def cmb_mod_with_prep(self, n, r):
        """
        二項係数nCr(mod p)をO(1)で求める。事前にprepを実行する事。
        """
        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.p


def resolve():
    n, k = map(int, input().split())
    k = min(k, n - 1)
    cb = CmbMod(n + 1, mod)
    cb.prep()
    res = 0
    for i in range(k + 1):
        res += (cb.cmb_mod_with_prep(n, i) * cb.cmb_mod_with_prep(n - 1, i)) % mod
        res %= mod
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
mod = 10 ** 9 + 7
def comb(n, r):
    if n < r:return 0
    if n < 0 or k < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
fa = [1] * (n + 1)
fi = [1] * (n + 1)
for i in range(1, n + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
ans = 0
for i in range(min(k, n - 1) + 1):
    ans += comb(n, i) * comb(n - 1, i) % mod
print(ans % mod)

Submission status: Accepted

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

fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
Mod = 10**9+7
def COMinit():
  #N_C_kのN
  for i in range(2, n+10):
    fac.append(fac[-1]*i%Mod)
    inv.append((-inv[Mod%i] * (Mod//i)) % Mod)
    finv.append(finv[-1] * inv[-1] % Mod)


def COM(n, k):
  if n < 0 or k < 0 or n < k:
    return 0
  return fac[n] * (finv[k] * finv[n-k] % Mod) % Mod


COMinit()

ans = 0

for i in range(min(n, k)+1):
  ans += (COM(n, i) * COM(n-1, n-i-1))
  ans %= Mod

print(ans)

Submission status: Accepted

Solution code:

class Combination:
    def __init__(self, n_max, mod=10 ** 9 + 7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max + 1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod - 2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    # "n 要素" は区別できる n 要素
    # "k グループ" はちょうど k グループ

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

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

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

    def nHr(self, n, r):
        if (n == 0 and r > 0) or r < 0:
            return 0
        return self.fac[n + r - 1] * self.facinv[r] % self.mod * self.facinv[n - 1] % self.mod


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

    r = min(N-1, K)
    cmb = Combination(N)

    ans = 0
    for i in range(r+1):
        ans += cmb.nCr(N, i) * cmb.nHr(N-i, i)
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def com(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def pom(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


N, K = map(int, input().split())
mod = 10**9+7
c = Combi(4*10**5+100, mod)
if N <= K:
    print(c.com(2*N-1, N-1))
else:
    ans = c.com(2*N-1, N-1)
    for i in range(K+1, N):
        ans -= c.com(N-1, N-i-1)*c.com(N, i)
    print(ans % mod)

Submission status: Accepted

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


mod = 10**9+7  # 出力の制限
N, K = map(int, input().split())
n = N*2
r = min(N, K+1)
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
for i in range(r):
    ans += cmb(N, i, mod) * cmb(N-1, i, mod)
if K == 1:
    ans -= 1
print(ans % mod)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
mod = 1000000007
def comb(n,k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fac[n]*finv[k]%mod*finv[n-k]%mod
fac = [1]*(n+1)
finv = [1]*(n+1)
for i in range(1,n+1):
    fac[i] = fac[i-1]*i%mod
    finv[i] = pow(fac[i],mod-2,mod)

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



M = 10**9+7
N = 4*10**5+3 # 必要なテーブルサイズ

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

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

n,k = map(int, input().split())
M = 10**9+7
if k<n:
    ans = 0
    for p in range(k+1):
        ans += cmb(n,p,M) * cmb(n-1, p, M)
        ans %= M
else:
    ans = cmb(2*n-1,n,M)
print(ans)

Submission status: Accepted

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


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)


def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

def com(n, r, mod):
    r = min(r, n - r)
    if r == 0:
        return 1
    res = ilist[n] * iinvlist[n-r] * iinvlist[r] % mod
    return res


mod = 10**9+7

ilist = [0]
iinvlist = [1]
tmp = 1
for i in range(1, n+1):
    tmp *= i
    tmp %= mod
    ilist.append(tmp)
    iinvlist.append(modinv(tmp, mod))

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


print(ans)

Submission status: Accepted

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

mod = 10**9 + 7
l = 10**7
fac = [1]*l
facr = [1]*l

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

def combi(N,K):
    return fac[N]*facr[N-K]%mod*facr[K]%mod

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

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def main():
    # nCrの左項にはn以外も来るバージョン、1!～(n-1)!を保持
    def prepare(n, MOD):
        # 1! - n! の計算
        f = 1
        factorials = [1]  # 0!の分
        for m in range(1, n + 1):
            f *= m
            f %= MOD
            factorials.append(f)
        # n!^-1 の計算
        inv = pow(f, MOD - 2, MOD)
        # n!^-1 - 1!^-1 の計算
        invs = [1] * (n + 1)
        invs[n] = inv
        for m in range(n, 1, -1):
            inv *= m
            inv %= MOD
            invs[m - 1] = inv

        return factorials, invs

    n, k = ns()
    facts, invs = prepare(n, MOD)

    ans = 0
    for ki in range(min(n, k + 1)):
        zero_comb = facts[n] * invs[ki] * invs[n - ki] % MOD
        nonzero_comb = facts[n - 1] * invs[ki] * invs[n - 1 - ki] % MOD
        ans += zero_comb * nonzero_comb % MOD
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def prepare():
    fact = []
    f = 1
    for m in range(1, n):
        f *= m
        f %= mod
    fact.append(f)
    f *= n
    f %= mod
    fact.append(f)
    
    factinv = [1, 1]
    inv = [0, 1]

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

    return fact, factinv

def cmb(a, r, p):
    if (r < 0) or (n < r):
        return 0
    if a == 1:
        return f[a] * v[r] * v[n - r] % mod
    else:
        return f[a] * v[r] * v[n - r - 1] % mod

f,v = prepare()

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

print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(2147483647)

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = 10**9+7 #割る数
N = 2*n+1  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans=1

if k>n:
    ans=cmb(n+n-1,n,p)

else:

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

print(ans%p)

Submission status: Accepted

Solution code:
def main():
    N, k = map(int, input().split())

    MAX_N = 3 * 10 ** 5
    MOD = 10 ** 9 + 7
    fac = [0]*MAX_N
    inv = [0]*MAX_N
    finv = [0]*MAX_N
    fac[0] = 1; fac[1] = 1
    inv[1] = 1
    finv[0] = 1; finv[1] = 1

    def com_init():
        for i in range(2, MAX_N):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = -(MOD//i)*inv[MOD%i]%MOD
            finv[i] = finv[i-1]*inv[i]%MOD

    def com(n, k):
        if n < 0:return 0
        elif k > n: return 0
        
        return (fac[n]*finv[n-k]%MOD)*finv[k]%MOD
    
    k = min(k, N-1)
    ans = 1
    com_init()
    for i in range(1, k+1):
        ans += com(N, i)*com(N-1, N-i-1)
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

mod = 10**9 + 7


class Mod:
    """
    comb = Mod(1000000)
    print(comb(5, 3))  # 5C3
    """

    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 comb(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

    def factorial(self, n):
        return self.fac[n]

    def factorial_inv(self, n):
        return self.facinv[n]

    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


def solve():

    n, k = map(int, input().split())
    k = min(n - 1, k)
    m = Mod(n)

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

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
#逆元nCr
mod = 10**9+7
def cmb(n,r,mod):
    r = min(r, n-r)
    return (fact[n] * factinv[r] * factinv[n-r]) % mod
def h(n,r,mod):
    return cmb(n+r-1,r,mod)
def makefact(n,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)
    return fact,factinv
fact,factinv = makefact(n,mod)


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