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())
def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n):
    #0!からn!までの逆元を素数10**9+7で割ったあまりリストを作る関数
    powlist=find_power(n,10**9+7)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist
mod=10**9+7
a=find_power(4*10**5+100,mod)
b=find_inv_power(4*10**5+100)
def combi(n,r,mod):
    if n<r:
        return 0
    elif n>=r:
        return (a[n]*b[r]*b[n-r])%(mod)
if n<=k:
    K=combi(2*n-1,n-1,mod)
    print(K)
    
else:
    K=combi(2*n-1,n-1,mod)
    for i in range(k+1,n):
        K-=combi(n-1,n-i-1,mod)*combi(n,i,mod)
    print(K%mod)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

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

inv_list = [1]  # 0で割るというのは定義されないので無視。
for i in range(n):
    inv_list.append(int(MOD - inv_list[(MOD % (i + 2)) - 1] * (MOD // (i + 2)) % MOD))
if k >= n:
    ans = 1
    for i in range(2 * n - 1):
        ans *= (i + 1)
        ans %= MOD
    for i in range(n):
        ans *= inv_list[i]
        ans *= inv_list[i]
        ans %= MOD
    ans *= n
    ans %= MOD
    print(ans)
else:
    ans = 1
    nCm = 1
    nmHm = 1
    for i in range(k):
        nCm *= n - i
        nCm *= inv_list[i]
        nCm %= MOD
        nmHm *= (n - 1) - i
        nmHm *= inv_list[i]
        nmHm %= MOD
        ans += nCm * nmHm
        ans %= MOD
    print(ans)

Submission status: Accepted

Solution code:
import math

def modcomb(n, k, mod, fac, ifac):
    x = fac[n]
    y = ifac[n-k] * ifac[k] % mod
    #print(x * y % mod)
    return x * y % mod

def makeTables(n, mod):
    fac = [1, 1]
    ifac = [1, 1]
    inv = [0, 1]

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

def answer(n, k, mod, fac, ifac):
    if k >= n:
        k = n - 1
    ans = 0
    for i in range(k+1):
        c = modcomb(n, i, mod, fac, ifac) * modcomb(n-1, i, mod, fac, ifac) % mod
        ans = (ans + c) % mod

    return ans

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

fac, ifac = makeTables(n, mod)
print(answer(n, k, mod, fac, ifac))

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

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

# 階乗、Combinationコンビネーション(numpyを使う)


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(N * 2 + 10, MOD)
fact, fact_inv = fact.tolist(), fact_inv.tolist()


def mod_comb_k(n, k, mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n - k] % mod


ans = 0
for i in range(N):
    if K < i:
        continue

    if N - 1 <= K:
        ans = mod_comb_k(N + N - 1, N - 1, MOD)
        break

    if i == 0:
        ans += 1
        continue

    a = int(mod_comb_k(N - 1, i, MOD)) * int(mod_comb_k(N, i, MOD))
    a %= MOD
    ans += a
    ans %= MOD

    '''
    a = int(fact[N]) * int(fact_inv[i]) % MOD * int(fact_inv[N - 1])
    a = a * int(fact[N-1]) % MOD * int(fact_inv[i]) % MOD * \
        int(fact_inv[N-i-1]) % MOD
    ans = (a + ans) % MOD
    '''

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

fac = [1, 1]
f_inv = [1, 1]
inv = [0, 1]

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


def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


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

    prepare(N, MOD)

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
mod=10**9+7
n_max=4*(10**5+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
FI[n_max-1]=pow(F[n_max-1],mod-2,mod)
for i in reversed(range(n_max-1)):
  FI[i]=(FI[i+1]*(i+1))%mod
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

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

  print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

# Wrong Answer
# WA


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

# 階乗、Combinationコンビネーション(numpyを使う)


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(N*2+10, MOD)


def mod_comb_k(n, k, mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n - k] % mod


ans = 0
for i in range(N):
    if K < i:
        continue

    if N - 1 <= K:
        ans = mod_comb_k(N + N - 1, N - 1, MOD)
        break

    if i == 0:
        ans += 1
        continue

    a = int(mod_comb_k(N - 1, i, MOD)) * int(mod_comb_k(N, i, MOD))
    a %= MOD
    ans += a
    ans %= MOD

    '''
    a = int(fact[N]) * int(fact_inv[i]) % MOD * int(fact_inv[N - 1])
    a = a * int(fact[N-1]) % MOD * int(fact_inv[i]) % MOD * \
        int(fact_inv[N-i-1]) % MOD
    ans = (a + ans) % MOD
    '''

print(ans)