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

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10**9+7
def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] * ifac[com_n - com_r]

def nHr(hn,hr):return nCr(hn+hr-1,hr)

n_max = 200005
fac = [mint(1)]
for i in range(1, n_max + 1): fac.append(fac[-1] * i)
ifac = [mint(1)] * (n_max + 1)
ifac[n_max] /= fac[n_max]
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1)

def main():
    n,k=MI()
    ans=mint(0)
    for v in range(min(k+1,n)):
        ans+=nCr(n,v)*nHr(n-v,v)
    print(ans)

main()

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

def modPow(a, n, mod):
    if n == 1:
        return a
    if n % 2 == 1:
        return (a * (modPow(a, n//2, mod) ** 2)) % mod
    else:
        return (modPow(a, n//2, mod) ** 2) % mod


def modInverse(a, p):
    # calculates the modular multiplicative of a mod m.
    # (assuming p is prime).
    return modPow(a, p-2, p)


def modBinomial(n, k, p):
    # calculates C(n,k) mod p (assuming p is prime).

    numerator = 1  # n * (n-1) * ... * (n-k+1)
    for i in range(k):
        numerator = (numerator * (n-i)) % p

    denominator = 1  # k!
    for i in range(1, k+1):
        denominator = (denominator * i) % p

    # numerator / denominator mod p.
    return (numerator * modInverse(denominator, p)) % p

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

if n <= k:
    print(modBinomial(2*n-1,n,mod))
    exit()
ans = 0
if k != 1:
    ans += 1
for i in range(1,k+1):
    ans = (ans + cmb(n,i,mod) * cmb(n-1,i,mod)) % mod

print(ans)

Submission status: Accepted

Solution code:
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod + x % mod)% mod
def comb(n,k,mod):
    c = 1
    for i in range(k):
        c = c*(n-i)%mod
        c = c*mod_inv(i+1,mod)%mod
    return c
n,k = map(int,input().split())
mod = 10**9+7
if k >= n-1:
    print(comb(n+n-1,n,mod))
else:
    ans = 0
    c = 1
    c2 = 1
    for i in range(k):
        c = c*(n-1-i)%mod
        c2 = c2*(n-i)%mod
        c = c*mod_inv(i+1,mod)%mod
        c2 = c2*(mod_inv(i+1,mod))%mod
        ans += c*c2
        ans %= mod
    if k > 1:
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
##部屋の移動は隣とは限らない
##部屋ごとに出入りを割り当てる
##出る<=入る+1
##出入りは相殺させて、たかだかk回の移動で、各人はたかだか1回移動とみなす
##別の部屋なので1回を0回とみなすのは不可能だが、2回以上は交代も可
##交代による相殺を別として、出た部屋に入る人はいない
##k>=nならば任意
#出に割り当てるx人をn-x部屋に割り当てる

n,k  = map(int,input().split( ))
mod = 10**9+7
if k==1:
    print(n*(n-1))
    exit()
rev = [0]+[pow(i,mod-2,mod) for i in range(1,n+3)]
chs_nx = [0]
def chs(t,s):
    res = 1
    for i in range(t,t-s,-1):
        res *= i
        res %=mod
    for i in range(1,s+1):
        res *= rev[i]
        res %=mod
    return res
res = 1
mn = min(n,k)
for i in range(1,mn+1):
    res *= n-i+1
    res *= rev[i]
    res %=mod
    chs_nx.append(res)
ans = 1

for i in range(1,mn+1):
    ans += chs_nx[i]**2*(n-i)*rev[n]
print(ans%mod)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def inv(x):
    return pow(x, MOD-2, MOD)

def nPk(n,k):
    
    # x=1
    # for a in range(n-k+1, n+1):
    #     x = x * a % MOD
    # return x
    return kaijo[n] * inv(kaijo[n-k]) % MOD

def nCk(n,k):
    return nPk(n,k) * inv(kaijo[k])

MOD = 10**9+7

kaijo = [0] * 400020
kaijo[0] = 1
for i in range(1, len(kaijo)):
    kaijo[i] = kaijo[i-1] * i % MOD

n,k = get_nums_l()

if k >= n-1:
    print(nCk(n+n-1, n) % MOD)
    exit()

# 0人の部屋=zがk以下であるような人数の並べ方の個数

# z=0 1
# z=1 nC1 * (n-1)**1
# z=2 nC2 * (n-2)**2
# z=3 nC3 * (n-3)**3

ans = 1
for z in range(1,k+1):
    ans += nCk(n,z) * nCk(n-1, z)

print(ans%MOD)

Submission status: Accepted

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

MOD = 10 ** 9 + 7
SIZE = 10 ** 6 + 1

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

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

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())

answer = 0
for k in range(min(N, K) + 1):
    answer = (answer + comb(N, k, MOD) * comb(N - 1, k, MOD)) % MOD
print(answer)

Submission status: Accepted

Solution code:

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret

def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max,mod=DIV):
    fac,finv,inv = [0]*max, [0]*max, [0]*max
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod -inv[mod%i] * (mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
    class CONV:
        def __init__(self):
            pass
        def ncr(self,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
    return CONV()


def main():
    n,k = isRaw()
    if k >= n-1:
        return ncr(2*n-1,n-1)
    conv = CONV_TBL(n+1)
    ans = 0
    for j in range(0,k+1):
        tmp = (conv.ncr(n, j)*conv.ncr(n-1, j)+DIV) % DIV
        ans = (ans+tmp+DIV )% DIV

    return ans


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
mod = 10**9+7
rng = 400100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
n,k=map(int,input().split())
dp=[0 for i in range(n+1)]
dp[0]=1
for i in range(1,n+1):
  x=cmb(n,i)*cmb(n-1,i)%mod
  dp[i]=(dp[i-1]+x)%mod
print(dp[min(k,n-1)])

Submission status: Accepted

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

MOD = 1000000007

def pow_mod(x, y):
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD

mod_inv = lambda x: pow_mod(x, MOD - 2)

if k >= n-1:
  n2_1 = (n * 2 - 1) % MOD 
  nHr = {0:1}
  for i in range(1, n):
    nHr[i] = nHr[i-1] * (n2_1 - i + 1)
    nHr[i] %= MOD
    nHr[i] *= mod_inv(i)
    nHr[i] %= MOD
  print(nHr[n-1])
else:
  mod_inv_d = {i: mod_inv(i) for i in range(1, max(k+1, n-k+1))}
  nCr = {0:1}
  n_1Cr = {0:1}
  ans = nCr[0] * n_1Cr[0]
  for i in range(1, k+1):
    hoge = (n - i + 1)
    nCr[i] = nCr[i-1] * hoge
    nCr[i] %= MOD
    nCr[i] *= mod_inv_d[i]
    nCr[i] %= MOD
    n_1Cr[i] = n_1Cr[i-1] * (hoge - 1)
    n_1Cr[i] %= MOD
    n_1Cr[i] *= mod_inv_d[i]
    n_1Cr[i] %= MOD
    ans += (nCr[i] * n_1Cr[i]) % MOD
    ans %= MOD
  print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

n,k=map(int,input().split())
zero_end = min(n,k+1)

inv_mod = [pow(i,MOD-2,MOD) for i in range(zero_end)]

comb_mod1 = [1] * zero_end
comb_mod2 = [1] * zero_end
for i in range(1,zero_end):
    comb_mod1[i] = comb_mod1[i-1] * (n-i+1) * inv_mod[i] %MOD
    comb_mod2[i] = comb_mod2[i-1] * (n-i  ) * inv_mod[i] %MOD

ans = 0

for i in range(zero_end): 
    
    ans = ans + comb_mod1[i] *comb_mod2[i] %MOD
    
print(ans%MOD)

Submission status: Accepted

Solution code:
def examA():
    N, R = LI()
    ans = R+100*max(0,(10-N))
    print(ans)
    return

def examB():
    N, K = LI()
    ans = 1
    while(N>=K):
        N //=K
        ans += 1
    print(ans)
    return

def examC():
    N = I()
    X = LI()
    ans = inf
    for i in range(101):
        cur = 0
        for x in X:
            cur += (i-x)**2
        ans = min(ans,cur)
    print(ans)
    return

def examD():
    def cmb(n, r, mod):
        cur = 1
        for i in range(r):
            cur *= (n-i)
            cur %= mod
        for i in range(r):
            cur *= pow(i+1,mod-2,mod)
            cur %= mod
        return cur
    n, a, b = LI()
    ans = pow(2,n,mod) - cmb(n,a,mod) - cmb(n,b,mod) -1
    ans = (ans+mod*2)%mod
    print(ans)
    return

def examE():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

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

        def comb(self, n, r, mod):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % mod
    n, k = LI()
    C = combination(2*10**5+1,mod)
    if k>n:
        k = n
    ans = 0
    for i in range(k+1):
        cur = C.comb(n,i,mod) * C.comb(n-1,i,mod)
        ans += cur
        ans %= mod
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

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

# a = cmb(n,r,mod)

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

if n <= k:
    k = n-1
# print(k)

while k >=0:
    if k == 0:
        ans += 1
        ans %= mod
    else:
        base = cmb(n,k,mod)
        # print(base)
        base *= cmb(n-1,n-k-1,mod)
        base %= mod
        ans += base
        ans %= mod
    # print(ans,k)
    k-=1

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n, k = LI()
    L = [[1]*n]
    ans = 1
    f = [1]
    N = 10**6
    for i in range(N):
        f.append(f[-1]*(i+1)%mod)
    inv = [None]*(N+1)
    inv[N] = pow(f[N],mod-2,mod)
    for i in range(N)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    def comb(a,b):
        return f[a]*inv[b]*inv[a-b]%mod
    ans = comb(2*n-1,n)
    if k + 1 >= n:
        print(ans)
    else:
        for t in range(k+1,n):
            ans -= comb(n,t)*comb(n-1,t)%mod
            ans %= mod
        print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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 = 200000
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
if k >= n:
    for i in range(n):
        ans += cmb(n-1, i, mod) * cmb(n, i, mod)
        ans %= mod


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

print(ans)

Submission status: Accepted

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

"""
T = [0]*n
def f(a, b, c):
  if a==n-1:
    T[c+max(b-1, 0)] += 1
  else:
    for i in range(0, b+1):
      f(a+1, b-i, c+max(i-1, 0))
f(0, n, 0)
ans = sum(T[:k+1])
print ans
print T
"""

"""
[1]
[1, 2]
[1, 6, 3]
[1, 12, 18, 4]
[1, 20, 60, 40, 5]
[1, 30, 150, 200, 75, 6]
[1, 42, 315, 700, 525, 126, 7]
https://oeis.org/A132813
T(n,k) = (k+1)*binomial(n+1,k+1)*binomial(n+1,k)/(n+1), n>=k>=0.
"""

M = 10**9+7

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

def C(x, y):
  return F[x]*pow(F[y], M-2, M)*pow(F[x-y], M-2, M)%M

ans = 0
for i in range(min(k+1, n)):
  ans += (i+1)*C(n, i+1)*C(n, i)*pow(n, M-2, M)%M
print ans%M

Submission status: Accepted

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

mod = 10 ** 9 + 7

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

def comb(n, r) :
  if n < 1 or n < r : return 0
  return fac[n] * inv[r] * inv[n-r] % mod
  
ret = comb(n + n - 1, n)
for i in range(1, n - k) :
  ret -= comb(n - 1, k + i) * comb(n, k + i)
  ret %= mod
print(ret % mod)

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 mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
fac = [1] * (5 * 10 ** 5 + 1)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD


n, k = map(int, input().split())
if k >= n:
    print(fac[2 * n] * pow(2, MOD - 2, MOD) *
          pow(fac[n], MOD - 2, MOD) ** 2 % MOD)
else:
    ans = 0
    for i in range(k + 1):
        ans += fac[n - 1] * pow(fac[i], MOD - 2, MOD) * \
            pow(fac[n - i - 1], MOD - 2, MOD) * fac[n] * pow(fac[n - i],
                                                             MOD - 2, MOD) * pow(fac[i], MOD - 2, MOD) % MOD
    print(ans % MOD)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
MOD=10**9+7
max_n=2*10**5
fac=[1]*(max_n+1)
inv=[1]*(max_n+1)
ifac=[1]*(max_n+1)
for n in range(2,max_n+1):
    fac[n]=(fac[n-1]*n)%MOD
    inv[n]=MOD-inv[MOD%n]*(MOD//n)%MOD
    ifac[n]=(ifac[n-1]*inv[n])%MOD
def comb(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    return (fac[n]*ifac[k]*ifac[n-k])%MOD
print(sum([(comb(N,k)*comb(N-1,k))%MOD for k in range(min(N,K)+1)])%MOD)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
mod = 10 ** 9 + 7

class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
f = Factorial(2 * N, mod)
dp = [0] * N
dp[0] = 1
for i in range(N - 1):
  x = i + 1
  dp[i + 1] = f.combi(N, x) * f.combi(x + (N - x - 1), N - x - 1) % mod
  dp[i + 1] += dp[i]
  dp[i + 1] %= mod
if K >= N: print(dp[-1])
else: print(dp[K])

Submission status: Accepted

Solution code:
mod=10**9+7
n,k=map(int,input().split())
def inv(x):
    return pow(x,mod-2,mod)
MAX_N=2*10**5
Fact=[0 for i in range(MAX_N+1)]
Finv=[0 for i in range(MAX_N+1)]
Fact[0]=1
for i in range(MAX_N):
    Fact[i+1]=(i+1)*Fact[i]
    Fact[i+1]%=mod
Finv[-1]=inv(Fact[-1])
for i in range(MAX_N-1,-1,-1):
    Finv[i]=Finv[i+1]*(i+1)
    Finv[i]%=mod
def C(n,k):
    return (Fact[n]*(Finv[k]*Finv[n-k])%mod)%mod

'''
for N in range(n,n+1):
    for K in range(N):
        print(C(N,K)*C(N-1,K),end=" ")
    print("")
'''
ans=0
for i in range(min(n,k+1)):
    ans+=(C(n,i)*C(n-1,i))%mod
    ans%=mod
    #print(ans)
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7         # 問題に合わせて適宜書き換え
list_size = 1000000   # 問題に合わせて適宜書き換え

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+2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(-2, -list_size-1, -1):
	f_r_list[i] = ((f_r_list[i+1] * (list_size + 2 + i)) % MOD)

def comb(n,r):
    if n < r:
        return 0
    if n == 0 or r == 0 or n == r:
        return 1
    return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD

N, K = map(int,input().split())
ans = 0
for i in range(min(K,N-1)+1):
    #print(i,comb(N-1,N-1-i),comb(N,1+i))
    ans += comb(N-1,i)*comb(N,N-i)
    ans %= MOD
    #print(ans)
print(ans)

Submission status: Accepted

Solution code:
MOD = 1000000007

class Factorial():
    def __init__(self,n,mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n+1)]
        self.inv = [0 for _ in range(n+1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i+1] = self.factorial[i]*(i+1)%mod
        self.inv[n] = pow(self.factorial[n],mod-2,mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i+1]*(i+1)%mod
    def fact(self,m): #階乗
        return self.factorial[m]
    def invfact(self,m): #階乗の逆数
        return self.inv[m]
    def perm(self,m,k): #順列
        if m < k: return 0
        return self.factorial[m]*self.inv[m-k]%self.mod
    def comb(self,m,k): #組み合わせ 0<=k<=m<=n 重複組み合わせはcomb(m+k-1,k)
        return self.factorial[m]*self.inv[k]*self.inv[m-k]%self.mod



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


F = Factorial(200010,MOD)
ans = 0

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

print(ans%MOD)

Submission status: Accepted

Solution code:
mod = 10**9+7
fact = [1]*(4*10**5+1)
for i in range(4*10**5):
    fact[i+1] = (i+1)*fact[i]%mod

factinv = [1]*(4*10**5+1)
for i in range(4*10**5+1):
    factinv[i] = pow(fact[i],mod-2,mod)

def comb(n,k):
    return fact[n]*factinv[k]*factinv[n-k]%mod
n,k = map(int,input().split())
ans = comb(2*n-1,n)
for i in range(k+1,n):
    ans -= comb(n-1,i)*comb(n,i)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
Q = 10**9+7
def getInv(N):#Qはmod
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

def getFactorialInv(N):
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    ret = [1]*(N+1)
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
        ret[i] = ret[i-1]*inv[i] % Q
    return ret

def getFactorial(N):
    ret = [1]*(N+1)
    for i in range(2,N+1):
        ret[i] = ret[i-1]*i%Q
    return ret

def main():
    n, k = map( int, input().split())
    fact = getFactorial(n)
    invfact = getFactorialInv(n)
    if k >= n-1:
        ans = 1
        for i in range(1,n*2):
            ans *= i
            ans %= Q
        print( ans*invfact[n-1]%Q*invfact[n]%Q)
        return
    ans = 0
    for i in range(k+1):
        ans += fact[n]*invfact[i]%Q*invfact[n-i]%Q*fact[n-1]%Q*invfact[i]%Q*invfact[n-1-i]%Q
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

K = min(K, N - 1)

fact = [1]
facinv = [1]
for i in range(1, N + 1):
    fact.append(fact[-1]*i % mod)


def nCr(n, r):
    num = fact[n]
    div = fact[r] * fact[n - r] % mod
    return num * pow(div, mod - 2, mod) % mod


move = [0] * (N + 1)
move[0] = 1
for i in range(1, N + 1):
    x = nCr(N, i) * nCr(N - 1, N - i - 1) % mod
    move[i] = x

for i in range(1, N):
    move[i] = (move[i - 1] + move[i]) % mod

ans = move[K]
print(ans)

Submission status: Accepted

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


FACT=[1]
for i in range(1,5*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(5*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

ANS=0
for i in range(min(k+1,n)):
    ANS+=Combi(n-1,n-i-1)*Combi(n,i)
    #print(i,ANS)

print(ANS%mod)

Submission status: Accepted

Solution code:
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


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

com = comb(n * 2, MOD)

ans = com.com(n * 2 - 1, n)
for i in range(k + 1, n + 1):
  t = com.com(n, i) * com.com(n - 1, i) % MOD
  ans -= t
  while ans < 0:
    ans += MOD


print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# %%
import numpy as np
# %%
stdin = open(0)

# %%
N, K = map(int, stdin.read().split())

# %%
MOD = 10 ** 9 + 7

# %%


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


def make_fact(U, MOD=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]
    fact.flags.writeable = False
    fact_inv.flags.writeable = False
    return fact, fact_inv


# %%
fact, fact_inv = make_fact(N + 10)

# %%
if K >= N:
    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 = np.sum(x * y % MOD) % MOD

# %%
print(answer)

# %%

Submission status: Accepted

Solution code:
def main():
    mod=1000000007
    n,k=map(int,input().split())
    m=2*n
    Fact=[1] #階乗
    for i in range(1,m+1):
        Fact.append(Fact[i-1]*i%mod)
    Finv=[0]*(m+1) #階乗の逆元
    Finv[-1]=pow(Fact[-1],mod-2,mod)
    for i in range(m-1,-1,-1):
        Finv[i]=Finv[i+1]*(i+1)%mod
    def comb(n,r):
        if n<r:
            return 0
        return Fact[n]*Finv[r]*Finv[n-r]%mod
    
    if k>=n-1:
        return comb(2*n-1,n-1)
    ans=1
    for i in range(1,k+1):
        ans+=comb(n,i)*comb(n-1,n-i-1)
        ans%=mod
    return ans
    
if __name__=='__main__':
    print(main())

Submission status: Accepted

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


FACT=[1]
for i in range(1,5*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(5*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

ANS=0
for i in range(min(k+1,n)):
    ANS+=Combi(n-1,n-i-1)*Combi(n,i)
    #print(i,ANS)

print(ANS%mod)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,K = inpl()

def comb(N,x):
    ret = 1
    for i in range(N-x+1,N+1):
        ret *= i
        ret %= mod

    for i in range(1, x+1):
        ret *= pow(i,mod-2,mod)
        ret %= mod

    return ret%mod

class Combination:
    def __init__(self,N):
        self.fac = [1]*(N+1)
        for i in range(1,N+1):
            self.fac[i] = (self.fac[i-1]*i)%mod
        self.invmod = [1]*(N+1)
        self.invmod[N] = pow(self.fac[N],mod-2,mod)
        for i in range(N,0,-1):
            self.invmod[i-1] = (self.invmod[i]*i)%mod

    def calc(self,n,k):#nCk
        return self.fac[n]*self.invmod[k]%mod *self.invmod[n-k] %mod




if N <= K:
    ans = comb(N*2-1, N)
    print(ans)
else:
    C = Combination(200000+3)
    ans = 0
    for z in range(K+1):
        r = N - z
        m = N - r
        ans += C.calc(N, z) * C.calc(r+m-1, m)
        ans %= mod

    print(ans)

Submission status: Accepted

Solution code:
# コンビネーション
mod = 10**9+7
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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())
if K >= N-1:
    ans = cmb(2*N-1, N)
else:
    ans = 0
    a = K
    while a >= 0:
        ans += cmb(N, a) * cmb(N-1, a) % mod
        ans %= mod
        a -= 1

print(ans)

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)