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:
MOD = 10**9 + 7

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

k = min(n-1,k)

dp = [0] * (k+1) # the number of empty room is i
dp[0] = 1
dp[1] = (n * (n-1)) % MOD

comn = 200000
fact = [1]*(comn+1)
inv = [1]*(comn+1)
ifact = [1]*(comn+1)
for i in range(1,comn+1):
    fact[i] = fact[i-1]*i % MOD
    inv[i] = pow(i,MOD-2,MOD)
    ifact[i] = ifact[i-1]*inv[i] % MOD

def nCr(n,r):
    return fact[n] * ifact[r] * ifact[n-r] % MOD

for i in range(2,k+1):
    dp[i] = (nCr(n,i) * nCr(n-1,i)) % MOD

print(sum(dp) % MOD)

Submission status: Accepted

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

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p


p = 10 ** 9 + 7
N = 2 * (10**5)  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
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)
ans=0
if(k<n-1):
    for i in range(1,k+1):
        k=cmb(n,i,p)*cmb(n-1,i,p)% p
        ans=ans+k
        ans=ans % p
    ans+=1 % p
else:
    for i in range(1,n):
        k=cmb(n,i,p)*cmb(n-1,i,p)% p
        ans=ans+k
        ans=ans % p
    ans+=1 % p
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 0!~n!をmodしつつ求める
def fact_all(n,M=mod):
    f = [1]*(n+1)
    ans = 1
    for i in range(1,n+1):
        ans = (ans*i)%M
        f[i] = ans
    return f

# inv(0!)~inv(n!)をmodしつつ求める
def fact_inv_all(fact_all,M=mod):
    N = len(fact_all)
    finv = [0]*N
    finv[-1] = pow(fact_all[-1],M-2,M)
    for i in range(N-1)[::-1]:
        finv[i] = finv[i+1]*(i+1)%M
    return finv

# nCkをmodしつつ返す
def nCk(n,k,fact_list=[],inv_list=[],M=mod):
    # a!をmodしつつ求める
    def fact(a,M=mod):
        ans = 1
        for i in range(2,a+1):
            ans = (ans*i)%M
        return ans

    # 互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
    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]]

    # aの逆元(mod M)を求める（aとMは互いに素）
    def mod_inv(a,M=mod):
        x = extgcd(a,M)[0]
        return (M+x%M)%M
    
    if fact_list and inv_list:
        return (((fact_list[n]*inv_list[k])%M)*inv_list[n-k])%M
    else:
        x = fact(n,M)
        y1 = mod_inv(fact(k,M),M)
        y2 = mod_inv(fact(n-k,M),M)
        return ((x*y1)%M*y2)%M

n,k = LI()

fact_list = fact_all(n)
inv_list = fact_inv_all(fact_list)

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

Submission status: Accepted

Solution code:
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

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

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

def main():
    n, k = map(int, input().split())
    comb = Combination(10 ** 6)
    MOD = 10 ** 9 + 7
    ans = 0
    if n - 1 <= k:
        ans = comb(n+n-1,n)
    else:
        ans = 0
        for i in range(1,k+1):
            ans += comb(n-1,i) * comb(n,i)
            ans %= MOD
        if k >= 2:
            ans += 1
        ans %= MOD




    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

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


mod = 10**9+7

MAX = N + 10
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

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

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

Submission status: Accepted

Solution code:
def modinv(a,m):
    return pow(a,m-2,m)


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



if n-1 <= k:
    N = n + min(n-1,k)
    ans = 1
    for i in range(1,n):
        ans = ans*(N+1-i)*modinv(i,P)%P

else:
    ans = 1
    nCl = 1
    n1Cl = 1
    for l in range(1,k+1):
        nCl = nCl*(n+1-l)*modinv(l,P)%P
        n1Cl = n1Cl*(n-l)*modinv(l,P)%P
        ans = (ans+nCl*n1Cl)%P

print(ans)

Submission status: Accepted

Solution code:
import math
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 =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)



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

Submission status: Accepted

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

n, k = map(int, readline().split())
P = 10**9 + 7

def mod_prod(a,b):
    return a * b % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n // 2
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret


if k >= n - 1:
    ans = mod_comb(n + n - 1, n - 1)
    print(ans)
else:
    ans = 0

    a = mod_comb(n, 0)
    b = mod_comb(n - 1, 0)
    ans = a * b % P
    for i in range(1, k + 1):
        a = mod_prod(a, (n - i + 1)) 
        a = mod_div(a, i)
        b = mod_prod(b, (n - 1 - i + 1))
        b = mod_div(b, i)
        ans += a * b % P
        ans %= P
    print(ans)

Submission status: Accepted

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

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


fl = [-1]*(k+1)
fl[0] = 1
def f(i):
  global fl
  if fl[i] > 0: return fl[i]
  else:
    if i <= n//2:
      res = f(i-1)*(n-i+1)*(n-i)
      t = power(i, MOD-2)
      res *= t
      res %= MOD
      res *= t
      res %= MOD
      fl[i] = res
      return res
    else:
      res = f(n-i) * (n-i)
      res *= power(i, MOD-2)
      res %= MOD
      fl[i] = res
      return res


if k <= n//2:
  fl = [-1]*(k+1)
  fl[0] = 1
  def f(i):
    global fl
    if fl[i] > 0: return fl[i]
    else:
      res = f(i-1)*(n-i+1)*(n-i)
      t = power(i, MOD-2)
      res *= t
      res %= MOD
      res *= t
      res %= MOD
      fl[i] = res
      return res

  ans = 0
  for i in range(k+1):
    ans += f(i)
    ans %= MOD
else:
  fl = [-1]*(n+1)
  fl[0] = comb(n, k) * comb(n-1, k) % MOD
  def f(i):
    global fl
    if fl[i-k] > 0: return fl[i-k]
    else:
      res = f(i-1)*(n-i+1)*(n-i)
      t = power(i, MOD-2)
      res *= t
      res %= MOD
      res *= t
      res %= MOD
      fl[i-k] = res
      return res
  
  ans = 0
  for i in range(k+1, n+1):
    ans += f(i)
    ans %= MOD
  ans = comb(2*n-1, n) - ans
  ans %= MOD


print(ans % MOD)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def comb(n,a):
    dend = n
    for i in range(1,a):
        dend = (dend*(n-i))%R
    sor = 1
    for i in range(2,a+1):
        sor = (sor*i)%R
    return (dend*modinv2(sor,R))%R

n,k = inm()
if n-1<=k:
    print(comb(2*n-1,n-1))
    exit()
c = [1]*(k+1)
d = [1]*(k+1)
for i in range(1,k+1):
    m = modinv2(i,R)
    c[i] = (c[i-1]*(n-i+1)*m)%R
    d[i] = (d[i-1]*(n-i)*m)%R
ddprint("c,d")
ddprint(c)
ddprint(d)
sm = 0
#for j in range(n-k,n+1):
#    sm = (sm+comb(n,j)*comb(n-1,j-1))%R
for j in range(k+1):
    sm = (sm+c[j]*d[j])%R
#if k==1:
#    sm = (sm-1)%R
print(sm)

Submission status: Accepted

Solution code:
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

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


def main():
    n, k = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    prep(10**6, mod)
    a = nCr(n + n - 1, n - 1, mod)
    if k < n:
        t = 0
        for x in range(k + 1):
            t = (t + nCr(n, x, mod) * nCr(n - 1, x, mod)) % mod
        print(t)
    else:
        print(a)
    


main()

Submission status: Accepted

Solution code:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def invmod(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

n, k = map(int, input().split())
c = 10**9 + 7
if k >= n-1:
    a = 2*n - 1
    ans = a
    temp = a
    for i in range(1, n-1):
        temp = temp*(a-i) % c
        temp = temp*invmod(i+1, c) % c
    print(temp)
else:
    temp1 = n
    temp2 = n-1
    ans = 1 + (temp1 * temp2) % c
    for i in range(1, k):
        temp1 = temp1*(n-i) % c
        temp2 = temp2*(n-i-1) % c
        inv = invmod(i+1, c)
        temp1 = temp1*inv % c
        temp2 = temp2*inv % c
        
        ans += (temp1 * temp2) % c
    print(ans%c)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int


def get_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD

def make_comb(n, k):
    k = min(k, n - k)
    a = 1
    b = 1
    for i in range(k):
        a = a * (n - i) % MOD
        b = b * (i + 1) % MOD
    ret = get_fraction_mod(a, b)
    return ret

def make_facts(n):
    '''
        make factorials
        0!(=1), 1!, 2!, 3! .... n!
    '''
    fact = [1]
    for i in range(n):
        fact.append((fact[i] * (i + 1)) % MOD)
    return fact


def make_combs(n, k):
    '''
        make [C(n, 0), C(n, 1), C(n, 2) ..... C(n, k)]
        n! / (n - k)! k!
    '''
    facts = make_facts(n)
    invs = [] # inverted for fraction
    for fact in facts:
        invs.append(pow(fact, MOD - 2, MOD))

    ret = []
    for i in range(0, n + 1):
        a = facts[n]
        ret.append(a * invs[i] * invs[n - i] % MOD)
    return ret

def _solve(n):
    dp = [0] * (n + 1)

def solve(n: int, k: int):
    ret = make_comb(n * 2 - 1, n)
    if k < n - 1:
        combs = make_combs(n - 1, n - 1)
        n_combs = make_combs(n, n)
        for i in range(k + 1, n):
            #tmp = make_comb(n, i)
            tmp = n_combs[i]
            t = combs[n - i - 1]
            ret -= tmp * t
            ret %= MOD
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    k = int(next(tokens))  # type: int
    solve(n, k)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def comb(n, r):
    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
MAXN=400000+10
g1=[1, 1]
g2=[1, 1]
inverse=[0, 1]

for i in range(2, MAXN+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:
    print(comb(N*2-1, N))
else:
    ans=1
    for i in range(1, K+1):
        ans=(ans+(comb(N-1, i)*comb(N, i))%MOD)%MOD
    print(ans)

Submission status: Accepted

Solution code:
U = 10**6
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

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

n, k = map(int, input().split())
if k+1 < n:
  ans = 0
  for i in range(k+1, n):
    ans += comb(n, i) * comb(n-1, i)
    ans %= MOD
  ans = comb(2*n-1, n) - ans
  ans %= MOD
else:
  ans = comb(2*n-1, n)
print(ans)

Submission status: Accepted

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

MOD = 1000000007  # type: int

# 逆元comb
def comb(n, k):
    k = min(n-k,k)
    ans = 1
    for i in range(1, k + 1):
        ans *= (n + 1 - i) * pow(i,MOD-2,MOD)
        ans %= MOD
        
    return ans

def solve(n: int, k: int):
    # nC0---n-1
    comb1 = [0]*n
    comb1[0] = 1
    for i in range(1, n):
        comb1[i] = (comb1[i-1]*(n + 1 - i) * pow(i,MOD-2,MOD))%MOD

    # nC0---n-1
    comb2 = [0]*(n-1)
    comb2[0] = 1
    for i in range(1, n-1):
        comb2[i] = (comb2[i-1]*(n - i) * pow(i,MOD-2,MOD))%MOD

    
    if k >= n-1: ## なんでもいける
        answer = 0
        for i in range(n): # i はゼロの数
            if i == 0:
                answer += 1
            else:
                answer += comb1[i]*comb2[n-1-i]%MOD
        print(answer%MOD)
        return
    else:
        answer = 0
        for i in range(k+1): # i はゼロの数
            if i == 0:
                answer += 1
            else:
                answer += comb1[i]*comb2[n-1-i]%MOD
        print(answer%MOD)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    k = int(next(tokens))  # type: int
    solve(n, k)

if __name__ == '__main__':
    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
 
n,k=map(int,input().split())
mod=10**9+7

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

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

Submission status: Accepted

Solution code:
import socket
import sys

hostnames = ['N551J', 'F551C', 'X553M']
input_file = 'e1.in'
if socket.gethostname() in hostnames:
    sys.stdin = open(input_file)


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


def read_int():
    return int(input())


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


def read_str():
    return input()


mod = 10 ** 9 + 7

N = 4 * 10 ** 5
f = [1] * (N + 1)
for i in range(N):
    f[i + 1] = ((i + 1) * f[i]) % mod

MAX = N + 2
inv = [0] * MAX
inv[1] = 1
for i in range(2, MAX):
    inv[i] = - inv[mod % i] * (mod // i)
    inv[i] %= mod


def solve():
    n, K = read_int_list()
    if K >= n:
        K = n - 1
    r = 0
    c = 1
    d = 1
    for k in range(K + 1):
        r += c * d
        r %= mod
        c = (c * (n - 1 - k) * inv[k + 1]) % mod
        d = (d * (n - k) * inv[k + 1]) % mod

    return r


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
mod=10**9+7
ans=0
fac=[1]
for i in range(n+1):
	r=fac[i]*(i+1)%mod
	fac.append(r)
def c(x,y):
	if x<y:
		return 0
	r=pow(fac[y]*fac[x-y]%mod,mod-2,mod)
	return r*fac[x]%mod
for i in range(min(k,n)+1):
	kari=c(n,i)
	kari*=c(n-1,i)
	ans+=kari
	ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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


# MOD = 998244353

# MOD = 998244353

def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = [1]
    r = 1
    for inv in mod_invs(max, mod)[1:]:
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


N, K = list(map(int, sys.stdin.buffer.readline().split()))


@lru_cache(maxsize=None)
def solve(li, k):
    li = eval(li)
    if k == 0:
        return {','.join(map(str, li))}
    ret_s = set()
    for i in range(len(li)):
        if li[i] > 0:
            for j in range(len(li)):
                if i == j:
                    continue
                cp = li[:]
                cp[i] -= 1
                cp[j] += 1
                ret_s |= solve(str(cp), k - 1)
    return ret_s


# print(solve(str([0] * N), K))

comb = Combination(N * 2 + 100, MOD)
if K >= N - 1:
    ans = comb.ncr(N * 2 - 1, N - 1)
    print(ans)
    exit()


@lru_cache(maxsize=None)
def solve2(n, k, size):
    if size == 0:
        return 0
    if k >= n - 1:
        return comb.ncr(n * 2 - 1, n - 1)
    ret = 0
    for i in range(k + 1):
        ret += solve2(n - i, k, size - 1)
    return ret


# ゼロが何個あるか
# 最大 K こ
ans = 0
for zero_cnt in range(K + 1):
    # ゼロを置く場所を選ぶ
    a = comb.ncr(N, zero_cnt)
    # ゼロ以外の場所に全部1を置く
    r = N - zero_cnt
    # r から (N - r == zero_cnt) 個選ぶ重複組合せ
    b = comb.ncr(r + zero_cnt - 1, zero_cnt)
    ans += a * b % MOD
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
mod = 10 ** 9 + 7
n = N * 2
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
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % mod

if N <= K+1:
  print(comb(n-1,N))
else:
  ans = (1 + (N * (N-1))) % mod
  for i in range(2,K+1):
    mini_ans = (comb(N,i) * comb(N-1,N-i-1)) % mod
    ans = (ans + mini_ans) % mod
  print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

class InverseTable:
    __slots__ = ['In', 'fac', 'Ifac']

    def __init__(self, mod, maxnum):
        self.In = [0, 1]; self.fac = [1, 1]; self.Ifac = [1, 1]
        for i in range( 2, maxnum + 1 ):
            self.In.append( ( -self.In[mod % i] * (mod//i) ) % mod )
            self.fac.append( ( self.fac[-1] * i ) % mod )
            self.Ifac.append( (self.Ifac[-1] * self.In[-1]) % mod )
        
    def cmb(self, n, r):
        if ( r<0 or r>n ): return 0
        r = min(r, n-r)
        return self.fac[n] * self.Ifac[r] * self.Ifac[n-r] % mod
    
    def per(self, n, r):
        if ( r<0 or r>n ): return 0
        return self.fac[n] * self.Ifac[n-r] % mod

invt = InverseTable(mod, 10**6)
# maxnum=10**6だとテーブル生成に200ms程かかるので（Pythonだと1000msほど）
# 最大生成領域は問題ごとに要検討

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

Submission status: Accepted

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))
MOD=10 ** 9 + 7

def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


class BinomialCoefficient(object):

    def __init__(self, N=510000, MOD=10**9+7):
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]
        self.MOD = MOD
        for i in range(2, N + 1):
            self.fac.append((self.fac[-1] * i) % MOD)
            self.inv.append((-self.inv[MOD % i] * (MOD // i)) % MOD)
            self.finv.append((self.finv[-1] * self.inv[-1]) % MOD)

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



n, k = MI()

if k >= n:
    print(combination(2 * n - 1, n, MOD))
    exit(0)

coef = BinomialCoefficient(n + 1, MOD)
ans = 1
for l in range(1, k + 1):
    ans += coef.comb(n, l) * coef.comb(n - 1, l)
    ans %= MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
Mod=10**9+7
f=[1]*(2*n+1)
for i in range(2,2*n+1):
    f[i]=f[i-1]*i%Mod
def f_inverse(i):
    return pow(f[i],Mod-2,Mod)
f_inv=[f_inverse(i) for i in range(2*n+1)]
def comb(n,i):
    return f[n]*f_inv[i]*f_inv[n-i]%Mod

Ans=0
for x in range(0,min(k+1,n)):
    Ans=(Ans+comb(n,x)*comb(n-1,x))%Mod
print(Ans)

Submission status: Accepted

Solution code:
M = 10 ** 9 + 7

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

# invert
def calc_inverse(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

def fact(a):
	n = 1
	
	for i in range(1, a + 1):
		n = (n * i) % M
	
	return n

facts = [None]
facts_i = [None]
f = 1
for i in range(1, n * 2):
	f = (f * i) % M
	facts.append(f)
	facts_i.append(calc_inverse(f, M))

def calc_count(men, room):
	if room == 1:
		return 1
	else:
		return facts[men + room - 1] * calc_inverse(facts[men], M) * calc_inverse(facts[room - 1], M) % M

def c(a, b):
	return facts[a] * facts_i[a - b] * facts_i[b] % M;

if k >= n:
	print(calc_count(n, n))
else:
	
	count = 0
	for i in range(1, k + 1):
#		print(i, ">", c(n, i), calc_count(i, n - i) % M, "=", c(n, i) * calc_count(i, n - i) % M)
		count = (count + c(n, i) * calc_count(i, n - i)) % M
	
	if k > 1:
		count += 1
	
	print(count)

Submission status: Accepted

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

MOD = 10**9 + 7

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_table(n, mod=10**9 + 7):
    # 元テーブル
    g1 = [0] * (n + 1)
    g1[0] = 1
    g1[1] = 1

    # 逆元テーブル
    g2 = [0] * (n + 1)
    g2[0] = 1
    g2[1] = 1

    # 逆元計算用テーブル
    inverse = [0] * (n + 1)
    inverse[0] = 0
    inverse[1] = 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

    return tuple(g1), tuple(g2), tuple(inverse)

g1, g2, inverse = make_table(2*n)

# n! (MOD p)
def factorial_mod(n, p = MOD):
    tmp = 1
    for i in range(1, n+1):
        tmp *= i
        tmp %= p
    return tmp

if n-1 <= k:
    print(cmb(2*n-1, n-1))
else:
    ans = 1
    for n_empty in range(1, k+1):
        ans += cmb(n, n_empty) * cmb(n-1, n-1-n_empty)
        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
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

def main():
    n, k = map(int, input().split())
    if k >= n-1:
        return cmb(2*n-1, n, mod) % mod
    else:
        t = 0
        for i in range(k+1):
            t += cmb(n, i, mod) * cmb(n-1, i, mod) 
            t %= mod
        return t
print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
from random import randint
from collections import defaultdict
from itertools import accumulate
from fractions import gcd
from collections import defaultdict
import sys
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
MOD = 10**9 + 7
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
 
size = 3 * 10**5
g1, g2, inverse = [0]*size, [0]*size, [0]*size
 
g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル
 
for i in range(2, size):
    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 = inpl()

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

Submission status: Accepted

Solution code:
mo = 10 ** 9 + 7
n, k = map(int, input().split())
def rev(u):
    return pow(u, mo - 2, mo)
def C(p, q):
    ans = 1
    for i in range(q):
        ans = ans * (p - i) % mo
    for i in range(q):
        ans = ans * rev(i + 1) % mo
    return (ans + mo) % mo
if k >= n - 1:
    print(C(2 * n - 1, n))
    exit()
u, v = 1, 1
ans = 1
for i in range(k):
    u = u * (n - 1 - i) * rev(i + 1) % mo
    v = v * (n - i) * rev(i + 1) % mo
    ans = (ans + u * v) % mo
print(ans)

Submission status: Accepted

Solution code:
def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res

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

MOD = 1000000007

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