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: Time Limit Exceeded

Solution code:
def factorial(n, mod=10**9+7):
    a = 1
    for i in range(1,n+1):
        a = a * i % mod
    return a


def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


def comb(n, k, mod=10**9+7):
    if n < k or k < 0:
        result = 0
    else:
        a = factorial(n, mod=mod)
        b = factorial(k, mod=mod)
        c = factorial(n-k, mod=mod)
        result = (a * power(b, mod-2, mod=mod) * power(c, mod-2, mod=mod)) % mod
    return result

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

if k >= n:
  print(comb(2*n-1, n))
  quit()

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

def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def f(i):
  res = fact[n] * fact[n-1] % MOD
  res *= power(fact[n-i], MOD-2)
  res %= MOD
  res *= power(fact[n-i-1], MOD-2)
  res %= MOD
  t = power(fact[i], MOD-2)
  res *= t
  res %= MOD
  res *= t
  res %= MOD
  return res
  

ans = 0
for i in range(k+1):
  ans += f(i)
  ans %= MOD

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
m=10**9+7
p=1
for i in range(1,n+1):p=(p*(2*n-i)*pow(i,m-2,m))%m
if k>=n:
    print(p)
else:
    c,d=1,1
    for i in range(1,k+1):c=(c*(n-i)*pow(i,m-2,m))%m
    for i in range(1,k+1):d=(d*(n-i+1)*pow(i,m-2,m))%m
    for i in range(k+1,n):
        c=(c*(n-i)*pow(i,m-2,m))%m
        d=(d*(n-i+1)*pow(i,m-2,m))%m
        p=(p-c*d)%m
    print(p)

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 *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

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

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

# 逆元事前処理ver
# nが小さい場合に
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()

# 部屋がn個
# 重複組み合わせ？

# つまり数え上げ
# 人数が0人の部屋がいくつあるか
# 0 ~ N - 1人
# 0人の部屋が0個の場合
# kが偶数ならいける kが1の場合はダメ
# kの回数は何か関係あるか

# k >= 2の時0人の部屋0人ができる
# 0人の部屋1人ができるのは？　k >= 1の時

if K >= 2:
    ans = 1 # 0人の部屋0人
else:
    ans = 0

for k in range(1, min(K + 1, N)):
    # 0の場所を決める *
    # 球があるN - kの部屋の仕切りN - k - 1の仕切り方について考える
    # ただし各部屋１個以上なければならないので自由に動かせる球はk個
    # kHN-k-1
    ans += cmb(N, k) * cmb(N - 1, N - k - 1)
    ans %= mod
print(ans % mod)

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	n,k=MI()
	mod=10**9+7

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

	ans=0
	for i in range(k+1):
		if n-i-1>=0:
			ans+=f[n]*finv[i]*finv[n-i]*f[n-1]*finv[i]*finv[n-i-1]
			ans%=mod
		else:
			break
	print(ans%mod)








if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
K = min(N-1, K)
fact = [1 for _ in range(200001)]
inv = [1 for _ in range(200001)]
fact_inv = [1 for _ in range(200001)]
mod = 10**9+7
for i in range(2, 200001):
    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

dp = [0] * N
for i in range(N):
    f1 = (fact[N] * fact_inv[N-i] * fact_inv[i]) % mod  
    f2 = (fact[N-1] * fact_inv[N-i-1] * fact_inv[i]) % mod 
    f = (f1*f2)%mod
    if i == 0:
        dp[i] = f
    else:
        dp[i] = (dp[i-1] + f) % mod
print(dp[K])

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N, K = map(int, input().split())
MAX = 10 ** 6 + 5
MOD = 10 ** 9 + 7

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def p(n, r, mod):
    return fac[n] * finv[n - r] % mod
    
comInit(MOD)

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

Submission status: Accepted

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

m = 4*10**5 + 500

fac = [1] * (m + 1)
facinv = [1] * (m + 1)
for i in range(1, m+1):
    fac[i] = (fac[i-1] * i) % mod
    facinv[i] = (facinv[i-1] * pow(i, -1, mod)) % mod

def nCk(n, k):
    return (fac[n] * facinv[k] * facinv[n-k]) % mod

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

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
mod = 1000000007
fac = [1]
inv = [1]
for i in range(n * 2):
    fac.append(fac[-1] * (i + 1) % mod)
    inv.append(pow(fac[-1], mod - 2, mod))


def cmb(n, k):
    if k < 0 or k > n:
        return 0
    return ((fac[n] * inv[k]) % mod * inv[n - k]) % mod


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

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


def main():
    mod=10**9+7
    N,K=MI()
    
    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

    fact=[1,1]
    factinv=[1,1]
    inv=[0,1]

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

    ans=0
    
    #空き部屋がk個
    for i in range(min(K+1,N)):
        a=i#動く人
        b=N-i#割り当てる部屋
        temp=cmb(a+b-1,a,mod)
        
        #空き部屋の選び方
        temp2=cmb(N,i,mod)
        temp*=temp2
        
        ans=(ans+temp)%mod
        
    print(ans)
        
    

main()

Submission status: Accepted

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

mod = 1000000007

def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

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

def cmb(n, k):
    if k < 0 or k > n:
        return 0
    return (fac[n] * inv[k] * inv[n - k]) % mod

x = max(0, n - k - 1)
ret = cmb(n * 2 - 1, n - 1)
for i in range(x):
    ret = (ret - cmb(n, i + 1) * cmb(n - 1, i)) % mod
print(ret)

Submission status: Accepted

Solution code:
mod_val = 10**9+7
n, k = map(int, input().split())
factorials = [1]*(n+1)  # values 0 to n
for i in range(2, n+1):
  factorials[i] = (factorials[i-1]*i)%mod_val
def mod_binomial(a, b):
  numerator = factorials[a]
  denominator = (factorials[b]*factorials[a-b])%mod_val
  invert = pow(denominator, mod_val-2, mod_val)
  return (numerator*invert)%mod_val
partial = 0
# m is number of rooms with no people
for m in range(min(k+1, n)):
  # m places within n to place the 'no people' rooms
  # put n-(n-m) people in n-m rooms (n-m) must be placed to be non-empty
  partial = (partial + (mod_binomial(n, m) * mod_binomial(n-1, m))%mod_val)%mod_val
print(partial)

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 = 5*10**5 #Nの最大値
g1 = [0]*(N+1) #元テーブル(p(n,r))
g1[0] = g1[1] = 1
g2 = [0]*(N+1) #逆元テーブル
g2[0] = g2[1] = 1
inverse = [0]*(N+1) #逆元テーブル計算用テーブル
inverse[0],inverse[1] = 0,1
for i in range(2,N+1):
    g1[i] = (g1[i-1] * i) % mod
    inverse[i] = (-inverse[mod % i] * (mod//i)) % mod
    g2[i] = (g2[i-1] * inverse[i]) % mod

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

# 0の数がi個の場合の数
dp = [0]*(n+1)
# 残りn-i種類にi個を割り振る　×　0がi個の場合の数 -> n-1Ci * nCi
for i in range(n+1):
    dp[i] = cmb(n-1,i) * cmb(n,i) % mod

if k == 1:
    ans = dp[1]
else:
    k = min(n,k)
    ans = 0
    for i in range(k+1):
        ans += dp[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
NN = 10**6

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

# M = 空き部屋数の最大値
M = min(N - 1, K)

"""
m = 0,1,2,...,M

N部屋から、空き部屋をm個選ぶ
-> N_C_m

残りの(N-m)部屋に、N人を配置する（空き部屋が出来てはいけない）
まず、(N-m)部屋に1人ずつ配置し、残ったm人を(N-m)部屋に配置する
これは、m個のボールと(N-m-1)本の仕切りの並び替えに相当する
-> (m+N-m-1)_C_m = N-1_C_m
"""

ans = 0
for m in range(0, M + 1):
    ans += cmb(N, m, mod) * cmb(N - 1, m, mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
# 解説を参考に作成
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
def inverse(a, p):
    """逆元"""
    a_, p_ = a, p
    x, y = 1, 0
    while p_:
        t = a_ // p_
        a_ -= t * p_
        a_, p_ = p_, a_
        x -= t * y
        x, y = y, x
    x %= p
    return x


# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(n, k):
    mod = 10 ** 9 + 7
    ans = 0
    p_mod = [1, 1]
    for i in range(2, n + 1):
        p_mod.append((p_mod[-1] * i) % mod)

    for i in range(min(n, k + 1)):
        if i == 0:
            ans += 1
        elif i == 1:
            ans += n * (n - 1)
        else:
            nCi = p_mod[n] * inverse(p_mod[n - i], mod) % mod * inverse(p_mod[i], mod) % mod
            nmHi = (p_mod[n - 1] * inverse(p_mod[n - i - 1], mod) % mod) * inverse(p_mod[i], mod) % mod
            # ans += cmb2(n, i, mod) * cmb2(n - 1, i, mod)
            ans += nCi * nmHi % mod
        ans %= mod
    print(ans)


if __name__ == '__main__':
    # S = input()
    # N = int(input())
    n, k = map(int, input().split())
    # Ai = [int(i) for i in input().split()]
    # Bi = [int(i) for i in input().split()]
    # ABi = [[int(i) for i in input().split()] for _ in range(N)]
    solve(n, k)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
import bisect
from functools import reduce
def main():
    def comb(n, r):
        numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
        denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
        return numerator * pow(denominator, mod - 2, mod) % mod
    mod = 10 ** 9 + 7
    N, K = MI()
    if K >= N - 1:
        ans = comb(2 * N - 1, N - 1)
        print(ans)
    else:
        N_r = pow(N, mod - 2, mod)
        ans = N * (N - 1) % mod
        add = N * (N - 1) % mod
        for i in range(2, K + 1):
            a = (N - i + 1) % mod
            b = (a - 1) % mod
            c = pow(i, mod - 2, mod)
            d = pow(c, 2, mod)
            add = ((((add * a) % mod * b) % mod) * d) % mod
            ans += add
            ans %= mod
        if K >= 2:
            ans += 1
            ans %= mod
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, mod):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % mod)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], mod - 2, mod)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % mod
        self.mod = mod

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.mod

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.mod

    def combination_large(self, k, r):
        """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.mod
        return (res * self.inv_fact[r]) % self.mod

n,k = map(int,input().split())
mod = 10**9+7
comb = Combination(n,mod)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Combination:
    def __init__(self, n, mod):

        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)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.MOD


@mt
def slv(N, K):
    ans = 0
    M = 10**9 + 7

    C = Combination(N*2+1, M)
    def H(n, r):
        return C(n+r-1, r)

    K = min(N-1, K)
    for k in range(K+1):
        m = N - k
        t = C(N, k) * H(m, k)
        ans += t
        ans %= M

    return ans


def main():
    N, K = read_int_n()
    print(slv(N, K))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

#nCrは以下のやつ全てを使ってください
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]
 
gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]
 
def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

def nPr(n,r):
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

N,K = map(int,input().split())
if K >= N:
    M = N
else:
    M = K

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

Submission status: Accepted

Solution code:
max_n=10**6
mod=10**9+7

frac=[1]
for i in range(1,max_n+1):
  frac.append((frac[-1]*i)%mod)

inv=[1,1]
inv_frac=[1,1]
for i in range(2,max_n):
  inv.append((mod-inv[mod%i]*(mod//i))%mod)
  inv_frac.append((inv_frac[-1]*inv[-1])%mod)
  
def perm(m,n):
  if m<n:
    return 0
  if m==1:
    return 1
  return (frac[m]*inv_frac[m-n])%mod

def comb(m,n):
  if m<n:
    return 0
  if m==1:
    return 1
  return (frac[m]*inv_frac[n]*inv_frac[m-n])%mod  

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

		
#階乗#
lim = 4*10**5   #必要そうな階乗の限界を入力
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod

#階乗の逆元#
fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod

n, k = MAP()

if n-1 <= k:
	print(C(2*n-1, n))
	exit()

ans = 0
for i in range(k+1):
	ans += C(n, i) * C(n-1, i) % mod
	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**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
a,b=map(int,input().split())
mod=(10**9)+7
if b>=a-1:
  print(cmb((2*a)-1, a,mod))
else:
  ans=0
  for i in range(1,b+1):
    ans+=cmb(a, i,mod)*cmb(a-1, a-i-1,mod)
  if b!=1:
    ans+=1
  print(ans%mod)

Submission status: Accepted

Solution code:
import sys

n, k = map(int, input().split())
P = int(1e9+7)


def cmb(n, r, P):
    r = min(r, n - r)
    inv_y = 1
    for i in range(1, r + 1):
        inv_y = (inv_y * i) % P
    inv_y = pow(inv_y, P - 2, P)
    x = 1
    for i in range(n - r + 1, n + 1):
        x = x * i % P
    return (x * inv_y) % P


if k >= n:
    print(cmb(2*n-1, n, P))
    sys.exit()
if k == 1:
    print((n * n - 1) % P)
    sys.exit()
ans = 1
comb1 = 1
comb2 = 1
for i in range(1, k + 1):
    iinv = pow(i, P-2, P)
    comb1 = ((comb1 * (n - i)) * (iinv)) % P
    comb2 = ((comb2 * (n - i + 1)) * (iinv)) % P
    ans = (ans + comb1*comb2) % P
print(ans)

Submission status: Accepted

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

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

if n-1 <= k:
    print((fact[2*n-1] * finv[n] * finv[n-1]) % mod)
    exit()

ans = 0
for i in range(k+1):
    ans += fact[n] * finv[n-i] * finv[i] * fact[n-1] * finv[n-1-i] * finv[i]
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
"""
一回の移動で移動する人間は一人なのか？＝＞質問みたらYESだった。

n=2の場合を除いて、
人がいる部屋の数はmax(n-k,1)以上となる。
人がいる部屋の数が1つの場合、2つの場合、、、と順番に場合の数を数えていく。
人がいる部屋の数がxの場合の場合の数の求め方：まず、n部屋の中から、x部屋を選ぶ場合の数でnCx。各部屋に一人は人がいるので、nからxを控除する。残りのn-xをx部屋でどう分けるかを考えればよい。
これは、重複組み合わせの公式で(n-x+x-1)C(x-1)。上記の二つをかけ合わせればよい。
あと、制約から考えて、combination関数は高速化が必要。
"""
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 = 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) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)




mod = 10**9 +7
n,k = map(int,input().split())
ans = 0
for i in range(n,max(n-k,1)-1,-1):
    ans += cmb(n,i,p)*cmb(n-i+i-1,i-1,p)
ans %= mod
print(ans)

Submission status: Accepted

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

fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
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):
  tmp = COM(n, i) % Mod
  tmp *= COM(i+n-i-1, i)
  tmp %= Mod
  ans += tmp
  ans %= Mod
print(ans)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
p = 10**9+7
size = 2*2*10**5

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

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, size + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

res = 0

for i in range(min(K, N)+1):
        res += (binom(N, i, p) * binom(N-1, N-i-1, p)) % p

print(res % p)

Submission status: Accepted

Solution code:
class mod_comb_k():
  def __init__(self, MAX_N = 10**6, mod = 10**9+7):
    self.fact = [1]
    self.fact_inv = [0] * (MAX_N + 4)
    self.mod = mod
    for i in range(MAX_N + 3):
      self.fact.append(self.fact[-1] * (i + 1) % self.mod)
    self.fact_inv[-1] = pow(self.fact[-1], self.mod - 2, self.mod)
    for i in range(MAX_N + 2, -1, -1):
      self.fact_inv[i] = self.fact_inv[i + 1] * (i + 1) % self.mod
  def comb(self, n, k):
    if n < k:return 0
    else:return self.fact[n] * self.fact_inv[k] % self.mod * self.fact_inv[n - k] % self.mod
c=mod_comb_k()
n,k=map(int,input().split())
if k>=n:print(c.comb(2*n-1,n))
else:
  ans=0
  m=10**9+7
  for i in range(k+1):
    ans+=c.comb(n-1,i)*c.comb(n,i)%m
    ans%=m
  print(ans)

Submission status: Accepted

Solution code:
n,k = list(map(int, input().split()))
mod = int(1e9+7)



def init_cmb(Nmax):
    #mod = 10**9+7 #出力の制限
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] # 逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル

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

g1,g2 = init_cmb(n+10)

def cmb(n, r, modn=mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % modn
  
# ci = 0 である個数が m となるような数列の数は、 nCm ×n−m Hm = nCm * n-1Cn-m-1
# 0 <= m < n で足算する

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

Submission status: Accepted

Solution code:
def build_combinations_counter(N=10**5, p=10**9+7):
    fact = [1, 1]  # fact[n] = (n! mod p)
    factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
    inv = [0, 1]  # mod p におけるnの逆元 n^(-1)
    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)
    
    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
    
    import functools
    return functools.partial(cmb, p=p, fact=fact, factinv=factinv)

def resolve():
    n, k = list(map(int, input().split()))
    MOD = 10**9+7
    counter = build_combinations_counter(2*10**5, 10**9+7)
    ans = 0
    for i in range(min(n, k+1)):
        ans += counter(n, i) * counter(n-1, n-i-1)
        ans %= MOD
    print(ans)
    
    
if __name__ == "__main__":
    resolve()

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

MOD = 10**9+7
fact, fact_inv = prepare(3*10**5, MOD)

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

k = min(n-1, k)

ans = 1
for i in range(1,k+1):
    z = fact[n] * fact_inv[i] % MOD * fact_inv[n-i] % MOD
    p = fact[n-1] * fact_inv[n-i-1] % MOD * fact_inv[i] % MOD
    ans += z * p % MOD
    ans %= MOD
print(ans)