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())
P=10**9+7
class FactInv:
    def __init__(self,N,P):
        fact=[];ifact=[];fact=[1]*(N+1);ifact=[0]*(N+1)
        for i in range(1,N):
            fact[i+1]=(fact[i]*(i+1))%P
        ifact[-1]=pow(fact[-1],P-2,P)
        for i in range(N,0,-1):
            ifact[i-1]=(ifact[i]*i)%P
        self.fact=fact;self.ifact=ifact;self.P=P
    def comb(self,n,k):
        return (self.fact[n]*self.ifact[k]*self.ifact[n-k])%self.P
C=FactInv(2*n+10,P)
ans=0
for i in range(0,min(k+1,n)):
    ans+=(C.comb(n,i)*C.comb(n-1,n-i-1))%P
    ans%=P
print(ans)

Submission status: Accepted

Solution code:
MOD=10**9+7
def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)#階乗テーブル、逆元テーブル、逆元
    fac[0]=1;fac[1]=1;finv[0]=1;finv[1]=1;inv[1]=1
    for i in range(2,N+1):
        fac[i]=fac[i-1]*i%MOD
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i]=finv[i-1]*inv[i]%MOD
    return fac,finv,inv


def COM(n,r):
    if n<r or r<0:
        return 0
    else:
        return ((fac[n]*finv[r])%MOD*finv[n-r])%MOD
        
n,k=map(int,input().split())
fac,finv,inv=facinv(2*n)

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

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def initialize_cmb(m, mod=10 ** 9 + 7):
    fac = [1]
    finv = [1]
    inv = [0] * (m + 1)
    if m > 1:
        fac.append(1)
        finv.append(1)
        inv[1] = 1
        pre_fac = 1
        pre_finv = 1
        for i in range(2, m + 1):
            pre_fac = pre_fac * i % mod
            fac.append(pre_fac)
            inv[i] = mod - inv[mod % i] * (mod // i) % mod
            pre_finv = pre_finv * inv[i] % mod
            finv.append(pre_finv)
    return fac, finv


def cmb(n, k, fac, finv, mod=10 ** 9 + 7):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


def main():
    input = stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, k = map(int, input().split())

    fac, finv = initialize_cmb(n, mod)

    c_n = []
    for i in range(n + 1):
        c_n.append(cmb(n, i, fac, finv))
    c_n_1 = []
    for i in range(n):
        c_n_1.append(cmb(n - 1, i, fac, finv))

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


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

MOD = 10**9+7

class Comb:
    def __init__(self, N):
        self.fac = [1] * (N+1)
        for i in range(2, N+1): self.fac[i] = self.fac[i-1] * i % MOD

    def pow(self, a, b):
        res = 1
        while b:
            if b & 1: res = res * a % MOD
            a = a**2 % MOD
            b >>= 1
        return res

    def pow2(self, a, b):
        return pow(a, b, MOD)

    def comb(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] * self.pow2(self.fac[r], MOD-2)) % MOD * self.pow2(self.fac[n-r], MOD-2) % MOD

    def permutation(self, n, r):
        if r == 0: return 1
        return self.fac[n] * self.pow2(self.fac[n-r], MOD-2) % MOD

def main():
  N, K = list(map(int, input().split()))

  comb = Comb(N)
  ans = 0

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

  print(ans) 

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


class combination():
    def __init__(self, mod):
        '''
        modを指定して初期化
        '''
        self.mod = mod
        self.fac = [1, 1]  # 階乗テーブル
        self.ifac = [1, 1]  # 階乗の逆元テーブル
        self.inv = [0, 1]  # 逆元計算用

    def calc(self, n, k):
        '''
        nCk%modを計算する
        '''
        if k < 0 or n < k:
            return 0
        self.make_tables(n)  # テーブル作成
        k = min(k, n - k)
        return self.fac[n] * (self.ifac[k] * self.ifac[n - k] %
                              self.mod) % self.mod

    def make_tables(self, n):
        '''
        階乗テーブル・階乗の逆元テーブルを作成
        '''
        for i in range(len(self.fac), n + 1):
            self.fac.append((self.fac[-1] * i) % self.mod)
            self.inv.append(
                (-self.inv[self.mod % i] * (self.mod // i)) % self.mod)
            self.ifac.append((self.ifac[-1] * self.inv[-1]) % self.mod)


comb = combination(mod)

n, k = inpl()
ans = 0
# m個の0人の部屋を作る
for m in range(min(n, k + 1)):
    # n個の部屋からm個の0人の部屋を選ぶ
    a = comb.calc(n, m) % mod
    # n個の部屋にm人を自由に割り当てる
    b = comb.calc(n - 1, n - m - 1) % mod
    ans += a * b % mod
print(ans % mod)

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


MOD = 10 ** 9 + 7
sys.setrecursionlimit(20000000)


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())
    answer = 0
    if K >= N - 1:
        cmb = Combination(2 * N + 1)
        answer = cmb(N * 2 - 1, N - 1)

    else:
        cmb = Combination(N)
        for i in range(K + 1):
            answer += cmb(N, i) * cmb(N - 1, N - 1 - i)
    print(answer % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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())
    comb = Combination(n_max=10 ** 5 * 4 + 10)

    if N <= K:
        ans = comb(2 * N - 1, N)
    else:
        if K == 1:
            ans = comb(N, 1) * comb(N - 1, 1)
        else:
            ans = 0
            # mはゼロとなる数
            for m in range(K + 1):
                ans += comb(N, m) * comb(N - 1, m)
                ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve():
    mod = 10**9+7
    n, k = map(int, input().split())
    m = min(n-1,k)
    ans = 1
    dp0 = [1]*(m+1)
    dp1 = [1]*(m+1)
    for i in range(1,m+1):
        dp0[i] = dp0[i-1]*(n-i+1)*pow(i,mod-2,mod)%mod
        dp1[i] = dp1[i-1]*(n-i)*pow(i,mod-2,mod)%mod
        ans += dp0[i]*dp1[i]%mod
        ans %= mod
    return ans
print(solve())

Submission status: Accepted

Solution code:
class Facts:

  def __init__(self, mod=10**9+7, n_max=1):
    self.mod     = mod
    self.n_max   = n_max
    self.fact    = [1, 1]
    self.inv     = [0, 1]
    self.factinv = [1, 1]
    if 1 < n_max:
      self.setup_table(n_max)

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

  def factorial(self, n):
    if self.n_max < n:
      self.setup_table(n)
    return self.fact[n]
    
  def hom(self, n, k):
    return self.cmb(n+k-1, k)

  def prm(self, n, k):
    if self.n_max < n:
      self.setup_table(n)
    return self.fact[n] * self.factinv[n-k] % self.mod

  def setup_table(self, t):
    for i in range(self.n_max+1,t+1):
      self.fact.append( self.fact[-1] * i % self.mod )
      self.inv.append( -self.inv[mod % i] * (self.mod // i) % self.mod )
      self.factinv.append( self.factinv[-1] * self.inv[-1] % self.mod )
    self.n_max = t

# ABC156 Roaming
mod = 10 ** 9 + 7

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

ans = 0
f = Facts(mod)

for i in range(0, min(n-1, k)+1):
  ans += f.cmb(n,i) * f.hom(n-i,i) % mod
  if ans >= mod:
    ans -= mod 

print(ans)

# ABC167 E 2020/5/11
# mod = 998244353

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

# ans = 0
# f = Facts(mod)
# t = m * pow(m-1, n-1-k, mod)

# for i in range(k,-1,-1):
#   ans += f.cmb(n-1,i) * t % mod
#   t = t * (m-1) % mod

# print(ans % mod)

Submission status: Accepted

Solution code:


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


class Combination(): # nCr mod MOD など
    """
    O(n+log(mod))の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    C = Combination(10**6)
    print(C.combi_mod(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7): # O(n+log(mod))
        self.mod = mod
        self.fac, self.facinv = self.prepare(n_max)
        #self.modinv = self.make_modinv_list(n_max) ##なくても問題ないので、必要な時のみ使う
        
    def prepare(self,n): # O(n+log(mod))
        # 前処理(コンストラクタで自動的に実行)
        # 1! ~ n! の計算
        factorials = [1]  # 0!の分
        for m in range(1, n+1):
            factorials.append(factorials[m-1]*m%self.mod)
        # n!^-1 ~ 1!^-1 の計算
        invs = [1] * (n+1)
        invs[n] = pow(factorials[n], self.mod-2, self.mod)
        for m in range(n, 1, -1):
            invs[m-1] = invs[m]*m%self.mod
        return factorials, invs # list
    
    def make_modinv_list(self, n): # O(n)
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            # 整数aのMを法とした時の逆元a^-1は、(0<=a<=M-1)
            # a == qM+rであるとき(qは商,rは余り)、
            # a^-1 == -qr^-1 % M で与えられる。
            modinv[i] = (self.mod - self.mod//i)*modinv[self.mod%i]  % self.mod
        return modinv

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

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

    def repeated_permutation(self,n,deno): # 重複順列
        # n!/(deno[0]!*deno[1]!*...*deno[len(deno)-1]) % MOD
        ## n:int(分子),deno:分母のlist
        if n < max(deno):
            return 0
        if (n < 0 or min(deno) < 0):
            return 0
        D = 1
        for i in range(len(deno)):
            D = D*self.facinv[deno[i]] % self.mod
        return self.fac*D % self.mod # int ## == n!/(deno[0]!*deno[1]!*...*deno[len(deno)-1]) % MOD
    
    def H(self,n,r): # 重複組合せ nHr % self.mod
        now_n = len(self.fac)
        if now_n < n+r-1: # もしself.facの長さが足りなかったら追加
            for i in range(now_n+1, n+r-1+1):
                self.fac.append(self.fac[i-1]*i%self.mod)
        return self.combi_mod(n+r-1,r)


mod = 10**9+7
C = Combination(n,mod)
ans = 0
for i in range(min(k+1,n+1)):
    ans += C.combi_mod(n,i)*C.H(n-i,i)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
# 0人になる部屋の数
# ・最小0 (k = 1　ないしは　N = 2 and k = 3が制約外なので必ず0になる)
# ・最大 min(k,N-1) (k人が部屋を空に出来るが、1部屋は必ず空でない部屋が残る)
# min(k,N-1)部屋が空になるということは、N-min(k,N-1)部屋には必ず人がいる
# 空でない部屋の最大数はN - K
# N - K - 1部屋に割り振るパターンはあり得ない
# つまりN-min(k,N-1)-1部屋に人がいるケースはあり得ない
# N人をN部屋に割り振る場合の数から、
# N人をN-min(k,N-1)-1部屋に割り振る場合の数を引く
# いずれも0の場合を含む
# N個をK箱に割り振る場合の数は、N+K-1 C N

DIV = 10 ** 9 + 7
n = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

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

# N人をN部屋に割り振る場合の数から、
# N人をN-min(k,N-1)-1部屋に割り振る場合の数を引く
# いずれも0の場合を含む
# N個をK箱に割り振る場合の数は、N+K-1 C N

ans = 0
for i in range(min(K,N-1) + 1):
  a = nCr(N,i,DIV)
  
  # N-i個の部屋にN個のボールを詰める
  # N個のうちのN-i個をまず1個ずつ詰める
  # 残りはN - (N - i) = i個
  # i個のボールをN-i個に詰める。i個と(N-i-1)個の仕切りの並び替え
  # (i + N - i - 1) C i = (N-1) C i
  b = nCr(N-1,i,DIV)
  
  ans += (a * b) % DIV
  ans %= DIV
  
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の数がmin(n-1,k)
MAX=min(n-1,k)

dp=[0]*(MAX+1)
dp[0]=1
ans=1
for i in range(1,MAX+1):
    ans+=cmb(n,i,p)*cmb(n-i+i-1,i,p)
    ans%=p
    #print(ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self, n):
        fact, invfact = [1] * (n + 1), [1] * (n + 1)
        for i in range(1, n + 1): fact[i] = i * fact[i - 1] % MOD
        invfact[n] = pow(fact[n], MOD - 2, MOD)
        for i in range(n - 1, -1, -1): invfact[i] = invfact[i + 1] * (i + 1) % MOD
        self._fact, self._invfact = fact, invfact

    def inv(self, n):
        return self._fact[n - 1] * self._invfact[n] % MOD

    def fact(self, n):
        return self._fact[n]

    def invfact(self, n):
        return self._invfact[n]

    def comb(self, n, k):
        if k < 0 or n < k: return 0
        return self._fact[n] * self._invfact[k] % MOD * self._invfact[n - k] % MOD

    def perm(self, n, k):
        if k < 0 or n < k: return 0
        return self._fact[n] * self._invfact[n - k] % MOD

def resolve():
    n, k = map(int, input().split())
    mf = modfact(n)
    res = 0
    for i in range(min(k + 1, n)):
        res += mf.comb(n, i) * mf.comb(n - 1, i) % MOD
        res %= MOD
    print(res)
resolve()

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
size = 4*10**5
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

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

k = min(k, n-1)

ans = 0

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

ans %= mod

print(ans)

Submission status: Accepted

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

MOD = int(1e+9+7)

max_zero_num = min(n-1, k)
kai = [1]*(n+1)
gyaku_kai = [1]*(n+1)

for i in range(n):
    kai[i+1] = kai[i]*(i+1) % MOD
    gyaku_kai[i+1] = pow(kai[i+1], MOD-2, MOD)%MOD
        
answer = 0
for zero_num in range(max_zero_num+1):
    answer = (answer + kai[n]*gyaku_kai[n-zero_num]*gyaku_kai[zero_num]*\
    kai[n-1]*gyaku_kai[n-1-zero_num]*gyaku_kai[zero_num]) %MOD

print(answer)

Submission status: Accepted

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

def prepare(n, MOD):
    facts = [1]*(n+1)
    for i in range(1, n+1):
        facts[i] = facts[i-1]*i%MOD
    invs = [1]*(n+1)
    _invs = [1]*(n+1)
    invs[n] = pow(facts[n], MOD-2, MOD)
    for i in range(0, n)[::-1]:
        invs[i] = invs[i+1] * (i+1) % MOD
    return facts, invs

ans = 0
facts, invs = prepare(n, MOD)

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

print(ans)

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 = (10**5)*2+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 )

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

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

Submission status: Accepted

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

MOD = 10**9+7
fac = [1]*(N+1)
rev = [1]*(N+1)
 
for i in range(1, N+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)

comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD
ans = 0

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import combinations
def run():
    n,k = map(int, input().split())
    mod = 10 ** 9 + 7
    ret = 0
    inv = generate_inv(n, mod)

    if k >= n-1:
        k = n-1
    left = 1
    right = 1
    ret = 1
    for h in range(1, k+1):
        right *= (n - h) * inv[h]
        right %= mod
        left *= (n - h + 1) * inv[h]
        left %= mod
        ret += right * left
        ret %= mod
    print(ret)


def generate_inv(n,mod):
    """
    逆元行列
    n >= 2
    """
    ret = [0, 1]
    for i in range(2,n+1):
        next = -ret[mod%i] * (mod // i)
        next %= mod
        ret.append(next)
    return ret


def comb_mod(n, a, mod):
    """
    return: [n, a] % mod
    Note: mod must be a prime number
    """
    up = 1
    down = 1
    for i in range(a):
        up *= n - i
        up %= mod
        down *= i + 1
        down %= mod
    down = pow_mod(down, mod - 2, mod)
    return (up * down) % mod

def pow_mod(n, k, mod):
    res = 1
    while True:
        if k // 2 >= 1:
            if k % 2 == 1:
                res = (res * n) % mod
            n = (n ** 2) % mod
            k = k // 2
        else:
            break
    return (n * res) % mod


if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
M=10**9+7
n,k=map(int,input().split())
from functools import lru_cache
@lru_cache(None)
def f(x):
  if x: return x*f(x-1)%M
  return 1
l=[f(i) for i in range(n+1)]
a=0
for i in range(min(n,k+1)):
  c=l[n]*l[n-1]%M
  p=l[i]**2*l[n-i]*l[n-i-1]%M
  a+=c*pow(p,M-2,M)
print(a%M)

Submission status: Accepted

Solution code:
M=10**9+7;n,k=map(int,input().split());a=c=1
for i in range(1,min(n,k+1)):m=n-i;c=c*-~m*m*pow(i,M-2,M)**2%M;a+=c
print(a%M)

Submission status: Accepted

Solution code:
M=10**9+7;n,k=map(int,input().split());a=c=p=1
for i in range(1,min(n,k+1)):c=c*(n-i+1)*(n-i)%M;p=p*i*i%M;a+=c*pow(p,M-2,M)
print(a%M)

Submission status: Accepted

Solution code:
M=10**9+7
n,k=map(int,input().split())
a=c=p=1
for i in range(1,min(n,k+1)):
  c=c*(n-i+1)*(n-i)%M
  p=p*i*i%M
  a+=c*pow(p,M-2,M)
print(a%M)

Submission status: Accepted

Solution code:
M=10**9+7
n,k=map(int,input().split())
l=[1]
f=1
for i in range(n):
  f=f*(i+1)%M
  l+=[f]
a=0
for i in range(min(n,k+1)):
  c=l[n]*l[n-1]%M
  p=l[i]**2*l[n-i]*l[n-i-1]%M
  a+=c*pow(p,M-2,M)
print(a%M)

Submission status: Accepted

Solution code:
M=10**9+7
n,k=map(int,input().split())
l=[1]
f=1
for i in range(n):
  f=f*(i+1)%M
  l+=[f]
a=0
for i in range(min(n,k+1)):
  c=p=1
  c=c*l[n]*l[n-1]%M
  p=p*l[i]**2*l[n-i]*l[n-i-1]%M
  a+=c*pow(p,M-2,M)
print(a%M)

Submission status: Accepted

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

S = [0]*(2*10**5+1)
S[1] = 1
for i in range(2, 2*10**5+1):
    S[i] = S[MOD%i]*(MOD-int(MOD/i))%MOD

if N-1 <= K:
    ans = 1
    num = 2*N - 1
    for i in range(N-1):
        ans *= (num-i)*S[i+1]
        ans %= MOD
    print(ans%MOD)
else:
    S1 = [1]*N
    S2 = [1]*N
    for i in range(1, N):
        S1[i] = (S1[i-1]*(N+1-i)*S[i])%MOD
        S2[i] = (S2[i-1]*(N-i)*S[i])%MOD
    ans = 0
    for i in range(K+1):
        ans += S1[i]*S2[N-1-i]
        ans %= MOD
    print(ans)


# nCm * n-mHm
# nCm * n-1Cn-m-1

Submission status: Accepted

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

A = [0]*(m+1)
B = [0]*(m+1)

for i in range(m+1):
    if i == 0:
        A[0] = 1
        B[0] = 1
    else:
        A[i] = ((A[i-1]*(n-i+1))*pow(i,mod-2,mod)) % mod
        B[i] = ((B[i-1]*(n-i))*pow(i,mod-2,mod)) % mod

ans = 0
for i in range(m+1):
    ans = (ans+A[i]*B[i]) % mod

print(ans % mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

nmax = 3*10**5
mod = 10**9+7

fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    for i in range(2,nmax):
        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 ncr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n]* (finv[r] * finv[n-r] %mod) %mod


ncr_pre()
n,k = map(int,input().split())
ans = 0
for i in range(min(n,k+1)):
    ans+=ncr(n,i)*ncr(i+n-i-1,i)
    ans%=mod
print(ans)

Submission status: Accepted

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, k = mi()
    factorial = [1] * (n + 1)
    for i in range(1, n + 1):
        factorial[i] = (factorial[i - 1] * i) % mod
    # print(factorial)

    def combination(n, r, mod):
        # a^(p-1) = 1
        # a^(p-2) = 1/a
        numerator = factorial[n]
        denominator = (factorial[r] * factorial[n - r]) % mod
        return (numerator * pow(denominator, mod - 2, mod)) % mod
    
    ans = 0
    for empty_room_num in range(min(n - 1, k) + 1):
        ans = (ans + combination(n, empty_room_num, mod) * combination(n - 1, empty_room_num, mod)) % mod
        # print(f"{empty_room_num} {ans}")
    print(ans)
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
#入力
readline=stdin.readline
N,K=map(int,readline().split())

mod=10**9+7
fact=[1]*(2*N)
finv=[1]*(2*N)
inv=[1]*(2*N)
inv[0]=0
for i in range(2,2*N):
    fact[i]=(fact[i-1]*i%mod)
    inv[i]=(-inv[mod%i]*(mod//i))%mod
    finv[i]=(finv[i-1]*inv[i])%mod

def com(N,K,mod):
    if (K<0) or (N<K):
        return 0
    return fact[N]*finv[K]*finv[N-K]%mod

if N-1<=K:
    print(com(2*N-1,N,mod))

else:
    res=0
    for m in range(K+1):
        res+=com(N,m,mod)*com(N-1,m,mod)
        res%=mod
    print(res)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

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

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 10 ** 6  # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)

N, K = lr()
K = min(K, N-1)
x = fact[N] * fact_inv[0:K+1] % MOD * fact_inv[N-K:N+1][::-1] % MOD
y = fact[N-1] * fact_inv[0:K+1] % MOD * fact_inv[N-K-1:N][::-1] % MOD
answer = (x * y % MOD).sum()
print(answer % MOD)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
# K回の移動が終わった後、人がいる部屋の数はNからN-K

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

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 10 ** 6  # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)

N, K = lr()
answer = 0
for x in range(N, max(0, N-K-1), -1):
    # x個の家には1人以上いるのでこの人たちは除く
    can_move = N - x
    # x-1の壁をcan_move+1の場所に入れる
    answer += cmb(N, x) * cmb(x - 1 + can_move, can_move)
    answer %= MOD
    
print(answer % MOD)
# 31