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:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

class Combination:
    """
    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):
        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 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
n,k = inpl()
m = min(n-1,k)
res = 1
if m == 1:
    print((n-1)*n%mod)
    quit()
comb = Combination(n+10)
for i in range(m):
    res += comb(n,i+1) * comb(n-1,n-i-2)
    res %= mod
print(res)

Submission status: Accepted

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

MOD = 10**9 + 7
MAX = 2 * n + 1
fact = [1] * (MAX + 1)  # i!
finv = [1] * (MAX + 1)  # (i!)^{-1}
iinv = [1] * (MAX + 1)  # i^{-1}

for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


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


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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import count, islice

MOD = 1000000007  # type: int

def mod_factorial_iter():
    acc = 1
    yield 1
    for i in count(1):
        acc = acc * i % MOD
        yield acc

def solve(n: int, k: int):
    mod_factorials = tuple(islice(mod_factorial_iter(), n+2))
    def comb(a, b):
        return (mod_factorials[a] * (pow(mod_factorials[a-b], MOD-2, MOD) * pow(mod_factorials[b], MOD-2, MOD)) % MOD) % MOD
    ans = 1
    for i in range(1, min(n-1, k)+1):
        t = (comb(n-1, i) * comb(n, i)) % MOD
        ans = (ans + t) % MOD
    return ans


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    print(solve(n, k))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def comb(p,q,A,fact = None,factinv = None): #pCq modA
  if (q < 0) or (p < q):
    return 0
  q = min(q, p - q)
  return fact[p] * factinv[q] * factinv[p-q] % A
def main():
  mod = 10 ** 9 + 7
  n, k = map(int, input().split())
  
  fact = [1] #n!をmodで割ったあまり、0! = 1
  factinv = [1,1] #(n!)^(-1)をmodで割ったあまり
  inv = [0,1] #n^-1をmodで割ったあまり
  
  for a in range(2, n + 1):
    inv.append((-inv[mod % a] * (mod // a)) % mod)
  for i in range(1, n + 1):
    fact.append((fact[-1] * i) % mod)
  for j in range(2, n + 1):
    factinv.append((factinv[-1] * inv[j]) % mod)
  ans = 0
  for i in range(min(n,k+1)): #i:空の部屋の数
    ans = (ans + comb(n,i,mod,fact,factinv)*comb(n-1,i,mod,fact,factinv)) % mod
  print(ans)
main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
MAX = int(2e5)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def main():
    n, k = map(int, input().split())
    ans = 0
    for i in range(min(n-1, k)+1):
        # iCn
        # (n-i-1)C(n-1)
        tmp = FACT[n] * INV[i] * INV[n-i] % MOD
        tmp = (tmp * FACT[n-1] * INV[n-i-1] * INV[i]) % MOD
        ans = (ans + tmp) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def pow_mod(a, b, p):
    res = 1
    mul = a
    for i in range(len(bin(b)) - 2):
        if (1 << i) & b:
            res = (res * mul) % p
        mul = (mul ** 2) % p
    return res


def comb_mod(n, r, p, factorial, invert_factorial):
    return (factorial[n] * invert_factorial[r] * invert_factorial[n - r]) % p


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

    factorial = [1] * (n + 1)
    for i in range(1, n + 1):
        factorial[i] = (factorial[i - 1] * i) % p

    invert_factorial = [0] * (n + 1)
    invert_factorial[n] = pow_mod(factorial[n], p - 2, p)
    for i in range(n - 1, -1, -1):
        invert_factorial[i] = (invert_factorial[i + 1] * (i + 1)) % p

    res = 0
    for i in range(min(k + 1, n)):
        res = (res + comb_mod(n, i, p, factorial, invert_factorial)
               * comb_mod(n - 1, i, p, factorial, invert_factorial)) % p
    print(res)


main()

Submission status: Accepted

Solution code:
def pow_mod(a, b, p):
    res = 1
    mul = a
    for i in range(len(bin(b)) - 2):
        if (1 << i) & b:
            res = (res * mul) % p
        mul = (mul ** 2) % p
    return res


def comb_mod(n, r, p, factorial=None, invert_factorial=None):
    return (factorial[n] * invert_factorial[r] * invert_factorial[n - r]) % p


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

    factorial = [1] * (n + 1)
    for i in range(1, n + 1):
        factorial[i] = (factorial[i - 1] * i) % p

    invert_factorial = [0] * (n + 1)
    invert_factorial[n] = pow_mod(factorial[n], p - 2, p)
    for i in range(n - 1, -1, -1):
        invert_factorial[i] = (invert_factorial[i + 1] * (i + 1)) % p

    res = 0
    for i in range(min(k + 1, n)):
        res = (res + comb_mod(n, i, p, factorial, invert_factorial)
               * comb_mod(n - 1, i, p, factorial, invert_factorial)) % p
    print(res)


main()

Submission status: Accepted

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

R = 200010
f = [1]*R
p = 1
for i in range(1, R):
    p = f[i] = p*i%mod

finv = [1]*R
p = finv[-1] = pow(f[-1], mod-2, mod)
for i in range(R-2, 0, -1):
    p = finv[i] = p*(i+1)%mod

def comb(n, k):
    return f[n]*finv[n-k]*finv[k]%mod

ans = 0
for m in range(min(k, n-1)+1):
    x = comb(n, m)
    y = comb(n-1, m)
    ans += x*y%mod

print(ans%mod)

Submission status: Accepted

Solution code:
U = 5*10**5
MOD = 10**9+7
 
def main():
  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)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:

def cmb1(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
ans = 0
k_ = min(n-1, k)
for i in range(k_+1):
    ans += cmb1(n, i, mod) * cmb1(n-i-1+i, i, mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
class Combinatorics:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}         # n!
        self.inverse = {i: None for i in range(1, N+1)}   # inverse of n in the field Z/(MOD)Z
        self.fact_inverse = {i: None for i in range(N+1)} # inverse of n! in the field Z/(MOD)Z
        
        # preprocess
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def perm(self, n, r):
        '''
        Calculate nPr = n! / (n-r)! % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return (self.fact[n] * self.fact_inverse[n-r]) % self.mod
    
    def binom(self, n, r):
        '''
        Calculate nCr = n! /(r! (n-r)!) % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
    def hom(self, n, r):
        '''
        Calculate nHr = {n+r-1}Cr % mod.
        Assign r objects to one of n classes.
        Arrangement of r circles and n-1 partitions:
            o o o | o o | | | o | | | o o | | o
        '''
        if n == 0 and r > 0:
            return 0
        if n >= 0 and r == 0:
            return 1
        return self.binom(n + r - 1, r)
    
MOD = 10**9 + 7
N, K = map(int, input().split())
com = Combinatorics(N, MOD)
ans = 0
for i in range(min(K, N-1) + 1):
    ans += (com.binom(N, i) * com.hom(N-i, i)) % MOD
    ans %= MOD
print(ans)

Submission status: Accepted

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


def combinations(n, r, MOD):
    if (r < 0) or (n < r):
        return 0

    r = min(r, n - r)
    return fact[n] * fact_inv[r] * fact_inv[n - r] % MOD


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

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


s = 0
for num_zero in range(min(k + 1, n)):
    # nCz
    x = combinations(n, num_zero, MOD)

    # n-zCx
    y = combinations(n - 1, n - num_zero - 1, MOD)

    s += (x * y) % MOD


print(s % MOD)

Submission status: Accepted

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

up = [1] * (n + 1)
down = [0] * (n + 1)
for i in range(1, n + 1):
  up[i] = (up[i - 1] * i) % D
down[n] = pow(up[n], D - 2, D)
for i in range(n, 0, -1):
  down[i - 1] = (down[i] * i) % D
  
def cmd(n, r, D):
  if r < 0 or r > n:
    return 0
  else:
    return (up[n] * down[r] * down[n - r]) % D

A = 0
k = min(k, n-1)
t = 0
while t <=k:
  A = (A + cmd(n-1, t, D) * cmd(n, t, D)) % D
  t = t+1
print (A)

Submission status: Accepted

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

MOD = 1000000007

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

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

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


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

    ifact = [0] * (n+1)
    ifact[n] = pow(fact[n], MOD-2, MOD)
    for i in range(n, 0, -1):
        ifact[i-1] = ifact[i] * i % MOD
    return (fact, ifact)


def cmb(n, r, table):
    if r > n:
        return 0
    return table[0][n] * table[1][n - r] * table[1][r] % MOD


def main():
    n, k = map(int, input().split())
    k = min(k, n-1)
    table = make_cmb_table(n)
    ans = 0
    for i in range(k+1):
        ans += cmb(n, i, table) * cmb((n-i-1)+i, i, table) % MOD
        ans %= MOD
    print(ans)


main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
mod = 10**9+7
m = min(n-1,k)
ans = 0

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

def comb_mod(n, r, mod):
    return f[n] * fi[r] * fi[n-r] % mod

for m in range(m+1):
    ans += comb_mod(n, m, mod) * comb_mod(n-1, m, mod) % mod

print(ans%mod)

Submission status: Accepted

Solution code:
MAX = 10 ** 5 * 2
mod = 10 ** 9 + 7
frac = [1]
inv_frac=[1]
def pow(a, n):
    if n == 0 : return  1
    elif n == 1 : return a
    tmp = pow(a, n//2)
    tmp = (tmp * tmp) % mod
    if n % 2 == 1 :
        tmp = (tmp * a) % mod
    return tmp
def inv(x):
    return pow(x, mod - 2 )
for i in range(1,MAX + 1 ):
    frac.append( (frac[-1] * i) % mod )
    inv_frac.append(inv(frac[-1])%mod)
def comb(n, k):
    if k >= n or k < 0 : return 1
    return (frac[n]*inv_frac[n-k] * inv_frac[k]) %mod
n,k = map(int,input().split())
count=0
b=inv(n)
for i in range(min(n,k+1)):
    a=comb(n,i)
    count=(count+a*a*(n-i)*b)%mod
print(count)

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
SIZE=4*10**5+1; MOD=10**9+7 #998244353 #ここを変更する
 
SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD
 
def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
def resolve():
    n, k = lr()
    ans = choose(2*n-1, n)
    if n-1 > k:
        for i in range(1, n-k):
            ans -= choose(n, i)*choose(n-1, n-i)
            ans %= MOD
    print(ans)
resolve()

Submission status: Accepted

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


fac = [0]*(n+1)
finv = [0]*(n+1)
inv = [0]*(n+1)
answer = 0
# テーブルを作る前処理
def COMinit(n, MOD):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, n+1):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
# 二項係数計算
def COM(n, 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, MOD)

fac = tuple(fac)
finv = tuple(finv)
inv = tuple(inv)

a = n if n < k else k + 1

for i in range(a):
    answer += COM(n,i) * COM(n-1, n-i-1)
    # print(answer)
print(answer%MOD)

Submission status: Accepted

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

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

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

ans = 0

if k >= n-1:
    print(cmb(2*n-1,n,p))
else:

    for i in range(k+1):
        ###i:0人の部屋の数
        x = cmb(n,i,p)###0人の部屋の選び方
        y = cmb(n-1,i,p)
            ###0人でないn-i個の部屋にn人が入る時の人数の組み合わせ
            ###各部屋に1人以上入るので, それを上回る分についてのみ考える
            ###すなわち, n-(n-i)=i人についての組み合わせを考える
            ###人間i人, 仕切りn-i-1個
        ans += (x*y)%p
        ans %= p

    print(ans)

Submission status: Accepted

Solution code:
class COM:
    def __init__(self, n: int, mod: int):
        self.n = n
        self.mod = mod
        self.fact = [0] * (n + 1)
        self.factinv = [0] * (n + 1)
        self.inv = [0] * (n + 1)
        
        self.fact[0] = self.fact[1] = 1
        self.factinv[0] = self.factinv[1] = 1
        self.inv[1] = 1
        for i in range(2, n + 1):
            self.fact[i] = (self.fact[i - 1] * i) % mod
            self.inv[i] = (-self.inv[mod % i] * (mod // i)) % mod
            self.factinv[i] = (self.factinv[i - 1] * self.inv[i]) % mod
    
    def get_cmb(self, n: int, k: int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] % self.mod * self.factinv[n - k] % self.mod


def solve():
    n, k = map(int, input().split())
    MOD = 10 ** 9 + 7
    
    com = COM(n, MOD)
    ans = 0
    for i in range(min(n, k + 1)):
        ans += com.get_cmb(n, i) * com.get_cmb(n - 1, i)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
x=input().split()
n=int(x[0])
k=int(x[1])
def fact_inverse(n,p):
    fact=[1]*(n+1)
    inv=[1]*(n+1)
    inv_fact=[1]*(n+1)
    inv[0]=0
    inv_fact[0]=0
    for i in range(2,n+1):
        fact[i]=(fact[i-1]*i)%p
        #compute the inverse of i mod p
        inv[i]=(-inv[p%i]*(p//i))%p
        inv_fact[i]=(inv_fact[i-1]*inv[i])%p
    return fact,inv_fact    
    

def combi2(n,p):
    f,inv=fact_inverse(n,p)
    combis=[1]*(n+1)
    for k in range(1,n+1):
        if k >=n//2+1:
            combis[k]=combis[n-k]
        else:
            combis[k]=(((f[n]*inv[n-k])%p)*inv[k])%p
    return combis    
      
    
p=10**9+7
combis1=combi2(n,p)
combis2=combi2(n-1,p)
s=0
L=min(n,k+1)
for i in range(L):
  s=(s+(combis1[i]*combis2[i])%p)%p
print(s)

Submission status: Accepted

Solution code:
class COM:
    def __init__(self, n: int, mod: int):
        self.n = n
        self.mod = mod
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]
        
        for i in range(2, n + 1):
            self.fact.append((self.fact[-1] * i) % mod)
            self.inv.append((-self.inv[mod % i] * (mod // i)) % mod)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % mod)
    
    def get_cmb(self, n: int, k: int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] % self.mod * self.factinv[n - k] % self.mod


def solve():
    n, k = map(int, input().split())
    MOD = 10 ** 9 + 7
    
    com = COM(n, MOD)
    ans = 0
    for i in range(min(n, k + 1)):
        ans += com.get_cmb(n, i) * com.get_cmb(n - 1, i)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from itertools import accumulate
import numpy as np
MOD = 10 ** 9 + 7


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


def make_fact_and_inv(U, mod=MOD):
    """
    0~Nまでのサイズ(N+1)の階乗およびその逆元の配列を返す
    """
    tmp = np.arange(U, dtype=np.int64)
    tmp[0] = 1
    fact = cumprod(tmp, mod)
    tmp = np.arange(U, 0, -1, dtype=np.int64)
    tmp[0] = pow(int(fact[-1]), mod - 2, mod)
    inv = cumprod(tmp, mod)[::-1]
    return fact, inv


fact, inv = make_fact_and_inv(2 * 10 ** 5 + 10)


def nCr(n, r, mod=MOD):
    if r < 0 or r > n or n < 0:
        return 0
    return fact[n] * inv[r] % mod * inv[n - r] % mod


if __name__ == "__main__":
    N, K = map(int, input().split())

    ans = []
    for i in range(min(N - 1, K) + 1):
        val = nCr(N, i) * nCr(N - 1, i) % MOD
        ans.append(val)

    answer = 0
    while ans:
        answer = (answer + ans.pop()) % MOD
    print(answer)

Submission status: Accepted

Solution code:
class Combination():
    def __init__(self, N:int, P:int):
        self.N = N
        self.P = P
        self.fact = [1, 1]   
        self.factinv = [1, 1]
        self.inv = [0, 1] 

        for i in range(2, N+1):
            self.fact.append((self.fact[-1] * i) % P)
            self.inv.append((-self.inv[P % i] * (P // i)) % P)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % P)
    def getComb(self, n:int, k:int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] % self.P * self.factinv[n-k] % self.P

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

    COMB = Combination(n,MOD)

    ans = 0
    for i in range(min(n, k+1)):
        ans += COMB.getComb(n,i) * COMB.getComb(n-1,i)
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

class Combination():
    # コンストラクタ
    def __init__(self, N:int, P:int):
        self.N = N
        self.P = P

        # fact[i] = (i! mod P)
        self.fact = [1, 1]   
        # factinv[i] = ((i!)^(-1) mod P)
        self.factinv = [1, 1]
        # factinv 計算用
        self.inv = [0, 1] 

        for i in range(2, N+1):
            self.fact.append((self.fact[-1] * i) % P)
            self.inv.append((-self.inv[P % i] * (P // i)) % P)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % P)
    
    # nCk (mod P)   (ただし、n<=N)
    def getComb(self, n:int, k:int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] % self.P * self.factinv[n-k] % self.P

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

COMB = Combination(n,MOD)

ans = 0
for i in range(min(n, k+1)):
    ans += COMB.getComb(n,i) * COMB.getComb(n-1,i)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

MOD=1000000007

n,k=map(int,input().split())
k=min(k,n-1)
fac=np.zeros((n+1)).astype(np.int64)
invfac=np.zeros((n+1)).astype(np.int64)
inv=np.zeros((n+1)).astype(np.int64)

invfac[0]=fac[0]=invfac[1]=fac[1]=inv[1]=1
for i in range(2,n+1):
    fac[i]=(fac[i-1]*i)%MOD
    inv[i]=(-inv[MOD%i]*(MOD//i))%MOD
    invfac[i]=(invfac[i-1]*inv[i])%MOD
def nCr(n,r):
    return ((fac[n]*invfac[r]%MOD)*invfac[n-r])%MOD
def nHr(n,r):
    return nCr(n+r-1,r)
    
print(np.sum(nCr(n,np.arange(k+1))*nHr(n-np.arange(k+1), np.arange(k+1))%MOD)%MOD)

Submission status: Accepted

Solution code:
import numpy as np

MOD=1000000007

n,k=map(int,input().split())
k=min(k,n-1)
fac=np.zeros((n+1)).astype(np.int64)
invfac=np.zeros((n+1)).astype(np.int64)
inv=np.zeros((n+1)).astype(np.int64)

invfac[0]=fac[0]=invfac[1]=fac[1]=inv[1]=1
for i in range(2,n+1):
    fac[i]=(fac[i-1]*i)%MOD
    inv[i]=(-inv[MOD%i]*(MOD//i))%MOD
    invfac[i]=(invfac[i-1]*inv[i])%MOD
def nCr(n,r):
    return ((fac[n]*invfac[r]%MOD)*invfac[n-r])%MOD
def nHr(n,r):
    return nCr(n+r-1,r)

ret = 0
x = nCr(n, np.arange(k+1))
y = nHr(n-np.arange(k+1), np.arange(k+1))
ret = np.sum(x*y%MOD)%MOD

print(ret)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = 1<<32
MOD = 1000000007  # type: int

# 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


def solve(n: int, k: int):
    fact = [1] * (n+1)
    ifact = [1] * (n+1)
    for i in range(1, n+1):
        fact[i] = i*fact[i-1] % MOD

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

    def comb(n, r, MOD=10**9+7):
        return fact[n] * ifact[n-r] * ifact[r] % MOD
    
    
    ans = 0
    for i in range(min(k, n-1)+1):
        ans += comb(n, i) * comb(n-1, i) % MOD
        ans %= MOD
    
    print(ans)

    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 main():
    import sys
    input = sys.stdin.readline

    # comb init
    mod = 1000000007
    nmax = 4 * 10 ** 5 + 10  # change here
    fac = [0] * nmax
    finv = [0] * nmax
    inv = [0] * nmax
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2, nmax):
        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 comb(n, r):
        if n < r:
            return 0
        else:
            return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

#output
mod = pow(10, 9) + 7

n_ = 4*10**5 + 5
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

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

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--

MOD = 10**9 + 7

def getModInv(a, b):
    return 1 if (a == 1) else (1-b*getModInv(b%a, a))//a%b


N, K = map(int, input().split())
t1, t2 = 1,1
s1, s2 = 1,1

for m in range(1, min(K, N-1)+1):
    t1 = t1*(N-m)*(N-m+1)%MOD
    t2 = t2*m**2%MOD

    s1 = (s1*t2 + s2*t1)%MOD
    s2 = s2*t2%MOD

print(s1*getModInv(s2, MOD)%MOD)

Submission status: Accepted

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

#n!とその逆元を求めておく
N=4*10**5+10
g1=[1,1] #n!
g2=[1,1] #n!の逆元
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 cmb(n,r): #nCrを求める
    if (r<0 or r>n):
        return 0
    r=min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod

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

Submission status: Accepted

Solution code:
LARGE = 10 ** 9 + 7


def solve(n, k):
    # singular cases
    if k == 0:
        return 1
    elif k == 1:
        return n * (n - 1)

    # pow
    pow_mod = [1] * (n + 1)
    for i in range(n):
        pow_mod[i + 1] = pow_mod[i] * (i + 1) % LARGE
    pow_mod_inv = [1] * (n + 1)
    pow_mod_inv[-1] = pow(pow_mod[-1], LARGE - 2, LARGE)
    for i in range(n - 1, 0, -1):
        pow_mod_inv[i] = pow_mod_inv[i + 1] * (i + 1) % LARGE

    res = 0
    for i in range(min(k, n - 1) + 1):
        # find where to set 0
        pick_zeros = pow_mod[n] * pow_mod_inv[i] * pow_mod_inv[n - i] % LARGE
        # how to assign ones
        assign_ones = pow_mod[n - 1] * pow_mod_inv[i] * pow_mod_inv[n - 1 - i] % LARGE
        res += pick_zeros * assign_ones
        res %= LARGE
    return res


def main():
    n, k = map(int, input().split())
    res = solve(n, k)
    print(res)


def test():
    assert solve(3, 2) == 10
    assert solve(200000, 1000000000) == 607923868
    assert solve(15, 6) == 22583772


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

Submission status: Accepted

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

MOD = 1000000007

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

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

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

mod = 10 ** 9 + 7
N = 10 ** 6

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

#階乗計算
kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

# コンビネーション計算
def cmb(n, r):
	return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

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