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())
MOD = 10**9+7
ans = 0
N = 5 * 10 ** 5
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
p = MOD
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):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
if k >= n-1:
    print(cmb(2*n-1, n, p))
else:
    for i in range(k+1):
        ans += cmb(n, i, p)*cmb(n-1, i, p) %MOD
    print(ans%MOD)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
k=min(k,n-1)
mod=10000*100000+7
def mpow(a,b,m=100000*10000+7):#returns a**b%m
  ret=1
  while b>0:
    if b&1:
      ret=(ret*a)%m
    a=(a*a)%m
    b>>=1
  return ret
fact=[1]*(n+1)
ifact=[1]*(n+1)
for i in range(2,n+1):
  fact[i]=(fact[i-1] *i)%mod
ifact[n]=mpow(fact[n],mod-2)
for i in range(n-1,1,-1):
  ifact[i]=((i+1)*ifact[i+1])%mod
def nCr(n,r):
  if r==0 or r==n:
    return 1
  val=(fact[n]*ifact[r])%mod
  return (val*ifact[n-r])%mod
ans=0
for h in range(k+1):
  ans=(ans+(nCr(n,h)*nCr(n-1,n-h-1))%mod)%mod
print(ans)

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

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

L = max(1, N - K)

ans = 0
for l in range(L, N + 1):
    zero = N - l
    ans += comb.ncr(N, zero) * comb.nhr(N - zero, zero)
    ans %= MOD

print(ans)

Submission status: Accepted

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

    import numpy as np
    def prepare(n):
        nrt = int(n ** 0.5) + 1
        nsq = nrt * nrt
        facts = np.arange(nsq, dtype=np.int64).reshape(nrt, nrt)
        facts[0, 0] = 1
        for i in range(1, nrt):
            facts[:, i] = facts[:, i] * facts[:, i - 1] % mod
        for i in range(1, nrt):
            facts[i] = facts[i] * facts[i - 1, -1] % mod
        facts = facts.ravel().tolist()
 
        invs = np.arange(1, nsq + 1, dtype=np.int64).reshape(nrt, nrt)
        invs[-1, -1] = pow(facts[-1], mod - 2, mod)
        for i in range(nrt - 2, -1, -1):
            invs[:, i] = invs[:, i] * invs[:, i + 1] % mod
        for i in range(nrt - 2, -1, -1):
            invs[i] = invs[i] * invs[i + 1, 0] % mod
        invs = invs.ravel().tolist()
 
        return facts, invs

    facts,invs=prepare(3*n)
    
    def nck(n,k):
        if k<0 or k>n:
            return 0
        else:
            return facts[n]*invs[n-k]*invs[k]%mod

    if k>=n-1:
        print(nck(2*n-1,n-1))
        exit()
    
    else:
        ans=0
        for i in range(k+1):
            ans+=nck(n,i)*nck(n-1,i)
            ans%=mod
        print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
MOD=10**9+7
def comb(n,m,p=10**9+7):
    buf=perm[n]*inv[m]
    buf%=MOD
    buf*=inv[n-m]
    buf%=MOD
    return buf
def inv_mod(a):
  return pow(a,MOD-2,MOD)

perm=[1]*(2*n+1)
for i in range(1,2*n+1):
    perm[i]=perm[i-1]*(i)
    perm[i]%=MOD
inv=[1]*(2*n+1)
inv[-1]=inv_mod(perm[-1])
for i in range(2*n-1,-1,-1):
    inv[i]=inv[i+1]*(i+1)
    inv[i]%=MOD
#print(comb(5,2))
buf=comb(2*n-1,n)
for j in range(k+1,n):
    x=comb(n,j)*comb(n-1,j)
    x%=MOD
    buf-=x
    buf%=MOD
print(buf)

Submission status: Accepted

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

fact = [1] * (2 * n + 1)
inv = [1] * (2 * n + 1)
invf = [1] * (2 * n + 1)
for i in range(2, 2 * n + 1):
  fact[i] = fact[i-1] * i % mod
  inv[i] = -inv[mod % i] * (mod // i) % mod
  invf[i] = invf[i-1] * inv[i] % mod

count = 0
for i in range(min(n, k+1)):
  c = fact[n] * invf[n-i] * invf[i] % mod
  count += c * fact[n-1] * invf[n-i-1] * invf[i] % mod
  count %= mod
print(count)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n, k = map(int, input().split())
    p = 10**9 + 7

    answer = 0
    nCi = 1
    n_1Ci = 1
    for i in range(min(k + 1, n)):
        answer += nCi * n_1Ci
        answer %= p
        deno = pow(i + 1, p - 2, p)
        nCi *= (n - i) * deno
        nCi %= p
        n_1Ci *= (n - i - 1) * deno
        n_1Ci %= p

    print(answer)

Submission status: Accepted

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

mod = 10**9 + 7
k = min(k, n-1)

def choose(n, r):
    x = 1
    y = 1
    for i in range(1, r+1):
        x = (x * (n-i+1)) % mod
        y = (y * i) % mod
    return (x * pow(y, mod-2, mod)) % mod

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

ans = 0
for i in range(k+1):
#    ans += (choose(n, min(i,n-i)) * choose(n-1, min(i,n-1-i))) % mod
    ans += (kaijo[n] * pow(kaijo[i]*kaijo[n-i], mod-2,mod) % mod) * (kaijo[n-1]*pow(kaijo[i]*kaijo[n-1-i],mod-2,mod) % mod)
    ans = ans % mod
print(ans % mod)

Submission status: Accepted

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

mod = 10**9 + 7
k = min(k, n-1)

def choose(n, r):
    x = 1
    y = 1
    for i in range(1, r+1):
        x = (x * (n-i+1)) % mod
        y = (y * i) % mod
    return (x * pow(y, mod-2, mod)) % mod

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

ans = 0
for i in range(k+1):
#    ans += (choose(n, min(i,n-i)) * choose(n-1, min(i,n-1-i))) % mod
    ans += kaijo[n] * pow(kaijo[i]*kaijo[n-i], mod-2,mod) * kaijo[n-1]*pow(kaijo[i]*kaijo[n-1-i],mod-2,mod)
    ans = ans % mod
print(ans % mod)

Submission status: Accepted

Solution code:
mod = 10**9+7

def factorials(n,m):
    # 0~n!のリスト
    f = [1,1]
    for i in range(2,n+1):
        f.append(f[-1]*i%m)

    # 0~n!の逆元のリスト
    g = [1]
    for i in range(n):
        g.append(pow(f[i+1],m-2,m))

    return f,g

f,g = factorials(4*10**5,mod)


n,k = map(int, input().split())
if k>=n-1:
    print((f[2*n-1]*g[n]*g[n-1])%mod)
else:
    ans = 0
    for x in range(k+1):
        ans += f[n-1]*g[x]*g[n-x-1]*f[n]*g[n-x]*g[x]
        ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
"""
E
"""
mod=10**9+7
MAX=4*10**5+100

g1=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    
def cmb(n,r):
    return g1[n]*pow(g1[r],mod-2,mod)*pow(g1[n-r],mod-2,mod)%mod


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

ans=cmb(2*N-1,N)


if K>=N:
    print(ans)
    
else:
    num=cmb(N,N-K-1)
    S=0
    for i in range(N-K-1,0,-1):
        S=(S+cmb(N-1,i-1)*cmb(N,i))%mod
        
    ans=(ans-S)%mod
    print(ans)

Submission status: Accepted

Solution code:
"""

部屋にいる人数が0の部屋は、操作一回につき一つできうる。が、どこかの部屋には移動しなければならないので、空っぽの部屋がNはあり得ない。
ので、空っぽの部屋の最大数=max(N-1,K)となる

移動方法について考えると、

・空の部屋が0個
行って戻ってを偶数回繰り返す（Kが1の場合はできない）
・空の部屋が１個
適当な部屋に移動をK回繰り返す
・空の部屋が２個
適当な部屋に移動→２人部屋以外に、二人部屋以外の人が移動
・空の部屋がm個
m-1人が別々の部屋に移動→最後の一人が、残り回数が１になるまで移動して、最後に一人部屋に移動

なので、やっぱり 0 or 1 ~ max(N-1,K)の部屋が空っぽになりうる
なので、その範囲について、どのような並び順になるか考える。
空っぽになる部屋の数をrとすると、
・n部屋からr個選ぶ方法 nCr
・残りn-r部屋について、
　人がn人、部屋の数がn-r個->n人と仕切りn-r-1個の並べ方。ただし残りの部屋について0人部屋はないので、
　最初にn-r人を残りの各部屋に割り当てて残りr人。

　** なので、n-rの部屋に重複を許して同質の人間r人を振り分ける方法（重複組み合わせ）と考えられる **

　ooo~oo <-r人の人間
　ここにn-r-1個の仕切りを入れることで、n-rの部屋に残りの人間を振り分ける
　n-rHr = (n-r-1 + r)! / ((n-r)! * r!) = (n-1)! / ((n-r)! * r!) =  n-1Cn-r-1
　

"""


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

MAXN = N+10
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -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
 
def nHr(n,r):
    return nCr(n+r-1, r)

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

print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
n,k=map(int,input().split())
ans=0
comb1=1 #初期値はNC0=1
comb2=1 #初期値は(N-1)C0=1
for i in range(min(k+1,n)): #0人の部屋は高々N-1個しか存在しないので操作回数は高々min(K,N-1)回となる
 ans+=comb1*comb2 #0人の部屋がi個のときの場合の数はNCi*(N-1)Ci
 ans%=mod
 comb1*=(n-i)*pow(i+1,mod-2,mod) #NC(i+1)はNCi*(N-i)/(i+1)で求められる
 comb1%=mod
 comb2*=(n-1-i)*pow(i+1,mod-2,mod) #(N-1)C(i+1)は(N-1)Ci*((N-1)-i)/(i+1)で求められる
 comb2%=mod
print(ans)

Submission status: Accepted

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

mod = pow(10,9)+7

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

s =0
for m in range((K+1)*(N>K)+(N)*(K>=N)):
  s += (kaijo[N]*pow((kaijo[m]*kaijo[N-m]),mod-2,mod ))%mod * (kaijo[N-1]*pow((kaijo[m]*kaijo[N-1-m]),mod-2,mod ) )%mod
  s = s%mod

print(s)

Submission status: Accepted

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


def cmb_r(n, r):
    n += r - 1
    return cmb(n, r)


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


def make_table2(n, mod=10 ** 9 + 7):
    # 元テーブル
    g1 = [0] * (n + 1)
    g1[0] = 1
    g1[1] = 1
    tmp = 1

    for i in range(2, n + 1):
        tmp = tmp * i % mod
        g1[i] = tmp

    # 逆元テーブル
    g2 = [0] * (n + 1)
    g2[-1] = pow(g1[-1], mod - 2, mod)
    tmp = g2[-1]

    for i in range(n - 1, -1, -1):
        tmp = tmp * (i + 1) % mod
        g2[i] = tmp

    return g1, g2


g1, g2 = make_table2(2 * 10 ** 5 + 2)
answer = 0
for i in range(min(n, k) + 1):
    answer += cmb(n, i) * cmb_r(n - i, i) % mod
    answer %= mod

print(answer)

Submission status: Accepted

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

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

    fac = [0 for _ in range(2*10**5+1)]
    fac[0],fac[1] = 1,1
    inv = copy.deepcopy(fac)
    invfac = copy.deepcopy(fac)
    
    for i in range(2,2*10**5+1):
        fac[i] = (fac[i-1]*i)%MOD
        inv[i] = MOD-(MOD//i)*inv[MOD%i]%MOD
        invfac[i] = (invfac[i-1]*inv[i])%MOD

    def coef(x,y):
        num = (((fac[x]*invfac[y])%MOD)*invfac[x-y]%MOD)
        return num
    
    ans = 0
    for i in range(min(N,K+1)):
        a = coef(N,i)
        b = coef(N-1,N-i-1)
        ans += ((a*b)%MOD)
        
    print(ans%MOD)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

    fac = [0 for _ in range(4*10**5+1)]
    fac[0],fac[1] = 1,1
    inv = copy.deepcopy(fac)
    invfac = copy.deepcopy(fac)
    
    for i in range(2,4*10**5+1):
        fac[i] = (fac[i-1]*i)%MOD
        inv[i] = MOD-(MOD//i)*inv[MOD%i]%MOD
        invfac[i] = (invfac[i-1]*inv[i])%MOD

    def coef(x,y):
        num = (((fac[x]*invfac[y])%MOD)*invfac[x-y]%MOD)
        return num
    
    ans = 0
    for i in range(min(N,K+1)):
        a = coef(N,i)
        b = coef(N-1,N-i-1)
        ans += ((a*b)%MOD)
        
    print(ans%MOD)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int, input().split())  
MOD=10**9+7
uplimit=2*10**5+1
fac = [0 for i in range(uplimit)] # 階乗
inv = [0 for i in range(uplimit)] # iの逆元 
finv = [0 for i in range(uplimit)] # i!の逆元

def fac_and_inv() :
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, uplimit) :
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * int(MOD / i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD
    return fac, finv, inv

temp = fac_and_inv()
ans = 0

#  x : 0人部屋の数
for x in range(0, k+1) : # k回動ける=最大kまで0人部屋になりうる
    if(x >= n) : # kがn以上の場合を想定。これ以降は計算する意味なし。
        break
    y = n - x # y : 人がいる部屋の数
    ans += (fac[n]*finv[x]*finv[n-x]) * (fac[n-1] * finv[x] * finv[y-1]) % MOD
    # 要はnCx * n-xHx 通り
    # nCxは0人部屋の選び方
    # n-xHxは n-xから重複を許してx選ぶ組み合わせ
    # n-xHx = n-1Cn-x-1 = n-1Cy-1
    # よって(n-1)! / x! / (y-1)!が欲しい

print(ans % MOD)

Submission status: Accepted

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

mod = 10**9+7 #出力の制限
N = 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 )

N, K = map(int, input().split())
MOD = 10**9+7
n = min(N,K)
ans = 0
for i in range(max(1,N-n),N+1):
  m = cmb(N,i,MOD)
  m *= cmb(N-1,i-1, MOD)
  ans += m
  ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
class combnk_mod(object):
    # pが素数かつaとpが互いに素であるとき
    # フェルマーの小定理より以下が成り立つ.
    # 1 / a = a ** (p - 2) (mod p)
    # これを使って (1 / k!) mod p を計算する.
    def __init__(self, maxn, p):
        self.maxn = maxn
        self.p = p
        self.x = [1] # 分母にあたる数 1 / n! mod p
        self.y = [1] # 分子にあたる数. n! mod p
        for i in range(1, self.maxn + 1):
            self.x.append(self.x[-1] * pow(i, self.p - 2, self.p) % self.p)
            self.y.append(self.y[-1] * i % self.p)

    def combnk(self, n, k):
        if n < k:
            return 0
        return (self.x[n - k] * self.x[k] * self.y[n]) % self.p

if __name__ == '__main__':
    MOD = 10 ** 9 + 7
    n, k = map(int, input().split())
    C = combnk_mod(n, MOD)

    ans = 0
    for m in range(min(n, k + 1)):
        ans += C.combnk(n, m) * C.combnk(n - 1, n - m - 1) % MOD
        ans %= MOD
    print(ans)

Submission status: Accepted

Solution code:
#標準入力を高速に
import sys
input = sys.stdin.readline

def factorial_mod(x, y, mod):
    factorial = 1
    for i in range(x,y+1):
        factorial *= i
        factorial %= mod
    return factorial
  
def n_C_k(n, k, mod, fact):
    inv = (pow(fact[n-k], mod-2, mod) * pow(fact[k], mod-2, mod)) % mod
    return (fact[n] * inv) % mod

"""
#main関数(若干早くなる)
def main():
    mod = 10**9+7
    n, k = map(int, input().split())         
    ans = 1+n*(n-1)

    a = n
    b = n-1

    for i in range(1, min(n, k)):
        temp1 = (n-i)*pow(i+1, mod-2, mod)%mod
        a *= temp1
        a %= mod
        temp2 = (n-1-i)*pow(i+1, mod-2, mod)%mod
        b *= temp2
        b %= mod
        temp3 = a*b%mod
        ans += temp3
        ans %= mod

    print(ans)
"""


#main関数(若干早くなる)
def main():
    mod = 10**9+7
    n, k = map(int, input().split())
    ans = (1+n*(n-1))%mod

    #階乗を使いまわすver.
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i
        fact[i] %= mod

    for i in range(2, min(n-1, k)+1):
        ans += n_C_k(n, i, mod, fact)*n_C_k(n-1, i, mod, fact)
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

MOD = 1000000007

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD

#互いに素なa,bについて、a*x+b*y=1の一つの解
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):
    x,_ = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res


MAX = 400001

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

def COMinit():
    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;

def mod_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;

COMinit()


n, k = l_in()

if k >= n-1:
    print(mod_COM(2*n-1, n-1))
else:
    res = 0
    for r in range(0, k+1):
        res = mod_add(res, mod_mul(mod_COM(n-1, r), mod_COM(n, r)))

    print(res)

Submission status: Accepted

Solution code:
#標準入力を高速に
import sys
input = sys.stdin.readline

def factorial_mod(x, y, mod):
    factorial = 1
    for i in range(x,y+1):
        factorial *= i
        factorial %= mod
    return factorial



def n_C_k(n, k, mod, fact):
    return (fact[n] * pow(fact[n-k], mod-2, mod) * pow(fact[k], mod-2, mod)) % mod

"""
#main関数(若干早くなる)
def main():
    mod = 10**9+7
    n, k = map(int, input().split())         
    ans = 1+n*(n-1)

    a = n
    b = n-1

    for i in range(1, min(n, k)):
        temp1 = (n-i)*pow(i+1, mod-2, mod)%mod
        a *= temp1
        a %= mod
        temp2 = (n-1-i)*pow(i+1, mod-2, mod)%mod
        b *= temp2
        b %= mod
        temp3 = a*b%mod
        ans += temp3
        ans %= mod

    print(ans)
"""


#main関数(若干早くなる)
def main():
    mod = 10**9+7
    n, k = map(int, input().split())
    ans = (1+n*(n-1))%mod

    #階乗を使いまわすver.
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i
        fact[i] %= mod

    for i in range(2, min(n-1, k)+1):
        ans += n_C_k(n, i, mod, fact)*n_C_k(n-1, i, mod, fact)
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
MAX = 200001
MOD = 1000000007


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


def cominit() :
  fac[0] = fac[1] = 1
  finv[0] = finv[1] = 1
  inv[1] = 1
  com[1] = n
  for i in range(2, MAX) :
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * int(MOD / i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD
    com[i] = com[i-1] * (n-(i-1)) * inv[i] % MOD
    
  return fac, finv, inv, com


temp = cominit()
k_1 = k%2
## x 部屋が0人になっているとして数える
ans = 0
for x in range(0, k+1) :
  ## 0人になる部屋数は n(全ての部屋数) よりも小さい
  if(x >= n) :
    break
  y = n - x
  ans += (com[x] * fac[n-1] * finv[x] * finv[y-1]) % MOD

print(ans % MOD)

Submission status: Accepted

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

n, k = [int(x) for x in input().split()]
mod = 10 ** 9 + 7

ans = 0

def make_tables(n, mod = 10 ** 9 + 7):
    fac = [1, 1] # 階乗テーブル
    finv = [1, 1] #逆元の階乗テーブル
    inv = [0, 1] #逆元テーブル

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

def nCk(n, k, mod = 10 ** 9 + 7):
    k = min(k, n-k)
    return fac[n] * finv[k] * finv[n-k] % mod

if k >= n - 1:
    x = n
else:
    x = k + 1

fac, finv = make_tables(n)

for i in range(x):
    ans += (nCk(n, i) * nCk(n - 1, i)) % mod
    ans %= mod
print(ans)

Submission status: Accepted

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

def calc(n,m):
    y = [1]*(n+1)
    for i in range(n):
        y[i+1] = (y[i]*(i+1))%m
        
    return y

def calc2(n,a,m,y):
    x = (y[a]*y[n-a])%m
    return (y[n]*pow(x, m-2, m))%m

m = 10**9+7
y = calc(2*n-1,m)
if k >= n-1:
    print(calc2(2*n-1, n-1, m, y))
else:
    s = 0
    for i in range(n-k-1):
        s += calc2(n-1,i,m,y)*calc2(n,i+1,m,y)
    print((calc2(2*n-1, n-1, m, y)-s)%m)

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

def make_table(size=10**6, p=MOD):
    fac = [None] * (size + 1)
    fac[0] = 1
    for i in range(size):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (size + 1)
    ifac[size] = pow(fac[size], p-2, p)
    for i in range(size, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    return fac, ifac

fac, ifac = make_table(5*10**5)

def comb(n, r, mod=MOD):
    if r > n or r < 0:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

def nHr(n, r):
    return comb(n-1+r, r)

n, k = map(int, sys.stdin.readline().split())
if k >= n:
        k = n - 1

def main():
    res = nHr(n, n)
    for i in range(1, n-k):
        res -= comb(n, i) * nHr(i, n-i) % MOD
        res %= MOD
    return res
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

def make_table(size=10**6, p=MOD):
    fac = [None] * (size + 1)
    fac[0] = 1
    for i in range(size):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (size + 1)
    ifac[size] = pow(fac[size], p-2, p)
    for i in range(size, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    return fac, ifac

fac, ifac = make_table(5*10**5)

def comb(n, r, mod=MOD):
    if r > n or r < 0:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

def nHr(n, r):
    return comb(n-1+r, r)

n, k = map(int, sys.stdin.readline().split())
if k >= n:
        k = n - 1

def main():
    res = nHr(n, n)
    for i in range(k+1, n):
        res -= comb(n, i) * nHr(n-i, i) % MOD
        res %= MOD
    return res
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
mod = 10**9 + 7
def factorial(N,MOD,r=True):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1,N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N],MOD-2,MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    if r:
        return fact,rfact
    else:
        return fact
fact,rfact = factorial(2*n,mod)

def perm(n,k): #上のfactorialと併用
    return fact[n]*rfact[n-k]%mod
def comb(n,k): #上のfactorialと併用
    return fact[n]*rfact[k]*rfact[n-k]%mod
ans = 0

if k+1>=n:
    ans = comb(2*n-1,n)
    print(ans)
else:
    ans = 0
    for i in range(k+1):
        ans += comb(n,i)*comb(n-1,i)
        ans %= mod
    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 comb(n,r,mod=10**9+7):
    if n<r:
        return 0
    elif n>=r:
        return (a[n]*b[r]*b[n-r])%(mod)

if n<=k:
    K=comb(2*n-1,n-1,mod)
    print(K)
    exit()

ans=0
for i in range(k+1):
    zs=i
    sm=comb(n,i) * comb(n-1,i)
    sm %= (10**9+7)
    ans+=sm

print(ans%(10**9+7))

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(U, 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 = mod_comb_k(N - 1, i, MOD)
    b = mod_comb_k(N, i, MOD)
    c = a * b
    c %= MOD
    '''
    a = mod_comb_k(N - 1, i, MOD)
    b = mod_comb_k(N, i, MOD)
    c = a * b % MOD
    ans += c
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a = 1
  b = 1
  c = 1
  for i in range(1,n+1):
    a = (a*i)%p
  for i in range(1,k+1):
    b = (b*i)%p
  for i in range(1,n-k+1):
    c = (c*i)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
mod = 10**9 + 7
zeronum = min(n-1,k)
comblist1 = []
comblist2 = []
ac = 1
for i in range(1,zeronum+1):
    ac = (ac*(n-i+1)*power_func(i,mod-2,mod))%mod
    comblist1.append(ac)
ac = 1
for i in range(1,zeronum+1):
    ac = (ac*(n-i)*power_func(i,mod-2,mod))%mod
    comblist2.append(ac)

ans = 1
for zero in range(1,zeronum+1):
    count = (comblist1[zero-1]*comblist2[zero-1])%mod
    ans = (ans+count)%mod
print(ans)

Submission status: Accepted

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


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

for i in range(2, 2 * N + 10):
    factorial.append((factorial[-1] * i) % MOD)
    inverse_from.append((-inverse_from[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * inverse_from[-1]) % MOD)


def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


ans = nCr(N * 2 - 1, N)
for x in range(K + 1, N):
    ans -= nCr(N, x) * nCr(N - 1, x) % MOD
    ans %= MOD

print(ans % MOD)

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(U, 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 i == 0:
        ans += 1
        continue

    '''
    a = mod_comb_k(N - 1, i, MOD)
    b = mod_comb_k(N, i, MOD)
    c = a * b
    c %= MOD
    '''
    a = mod_comb_k(N - 1, i, MOD)
    b = mod_comb_k(N, i, MOD)
    c = a * b % MOD
    ans += c
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
mod=10**9+7
k=min(k,n-1)
ans=1
g=1
h=1
for i in range(k):
    g*=(n-i)*pow(i+1,mod-2,mod)
    g%=mod
    h*=(n-1-i)*pow(i+1,mod-2,mod)
    h%=mod
    ans+=g*h%mod
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
def prepare(m, mod=10 ** 9 + 7):
	fac = [1] * (m + 1)
	inv = [1] * (m + 1)
	for i in range(1, m + 1):
		fac[i] = fac[i - 1] * i % mod
	inv[-1] = pow(fac[-1], mod - 2, mod)
	for i in range(m - 1, -1, -1):
		inv[i] = inv[i + 1] * (i + 1) % mod
	return fac, inv

n, k = map(int, input().split())
mod = 10 ** 9 + 7
fac, inv = prepare(n)

def cmb(n, r):
	assert n >= r >= 0
	return fac[n] * inv[n - r] * inv[r] % mod

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