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:
class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    # "n 要素" は区別できる n 要素
    # "k グループ" はちょうど k グループ

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

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

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

    def H(self, n, r):
        if (n == 0 and r > 0) or r < 0: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

    def rising_factorial(self, n, r):  # 上昇階乗冪 n * (n+1) * ... * (n+r-1)
        return self.fac[n+r-1] * self.facinv[n-1] % self.mod

    def stirling_first(self, n, k):  # 第 1 種スターリング数  lru_cache を使うと O(nk)  # n 要素を k 個の巡回列に分割する場合の数
        if n == k: return 1
        if k == 0: return 0
        return (self.stirling_first(n-1, k-1) + (n-1)*self.stirling_first(n-1, k)) % self.mod

    def stirling_second(self, n, k):  # 第 2 種スターリング数 O(k + log(n))  # n 要素を区別のない k グループに分割する場合の数
        if n == k: return 1  # n==k==0 のときのため
        return self.facinv[k] * sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def balls_and_boxes_3(self, n, k):  # n 要素を区別のある k グループに分割する場合の数  O(k + log(n))
        return sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def bernoulli(self, n):  # ベルヌーイ数  lru_cache を使うと O(n**2 * log(mod))
        if n == 0: return 1
        if n % 2 and n >= 3: return 0  # 高速化
        return (- pow(n+1, self.mod-2, self.mod) * sum(self.C(n+1, k) * self.bernoulli(k) % self.mod for k in range(n))) % self.mod

    def faulhaber(self, k, n):  # べき乗和 0^k + 1^k + ... + (n-1)^k
        # bernoulli に lru_cache を使うと O(k**2 * log(mod))  bernoulli が計算済みなら O(k * log(mod))
        return pow(k+1, self.mod-2, self.mod) * sum(self.C(k+1, j) * self.bernoulli(j) % self.mod * pow(n, k-j+1, self.mod) % self.mod for j in range(k+1)) % self.mod

    def lah(self, n, k):  # n 要素を k 個の空でない順序付き集合に分割する場合の数  O(1)
        return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.mod

    def bell(self, n, k):  # n 要素を k グループ以下に分割する場合の数  O(k**2 + k*log(mod))
        return sum(self.stirling_second(n, j) for j in range(1, k+1)) % self.mod


def main():
    N, K = map(int, input().split())
    mod = 10**9+7
    sign = 1
    L = []
    comb = Combination(202020)
    ans = 0
    for n_zeroes in range(min(K+1, N)):
        a = comb.C(N, n_zeroes) * comb.H(N-n_zeroes, n_zeroes) % mod
        ans += a
    print(ans % mod)

main()

Submission status: Accepted

Solution code:
import sys

N_MAX = 200000 + 5
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7

# ## COMBINATION (MOD) ## #

fac = [1, 1]  # 元テーブル
facinv = [1, 1]  # 逆元テーブル
inv = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N_MAX + 1):
    fac.append((fac[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    facinv.append((facinv[-1] * inv[-1]) % MOD)


def cmb(n, r):
    if (r < 0 or r > n):
        return 0
    # r = min(r, n-r)
    return fac[n] * facinv[r] * facinv[n - r] % MOD


def main():
    n, k = map(int, sys.stdin.readline().rstrip().split())

    k = min(n, k)

    ans = 0
    for m in range(k+1):
        empty = cmb(n, m)
        member = cmb(n - 1, n - m - 1)
        ans += (empty * member) % MOD
        ans %= MOD

    print(ans)


main()

Submission status: Accepted

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

# ①nCrの各項のmod(10^9+7)を事前計算
p = 10 ** 9 + 7
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, 2*n):
  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

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

Submission status: Accepted

Solution code:
def factorial(n, mod):
    fac = [0] * (n + 1)
    inv = [0] * (n + 1)
    fac[0], inv[0] = 1, 1
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % mod
        inv[i] = inverse(fac[i], mod)
    return fac, inv

def inverse(a, mod):
    a %= mod
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod

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

if k == 1:
    print(n * (n - 1) // 2 % mod)
    quit()

if k >= n:
    k = n - 1
ans = 0
for i in range(0, k + 1):
    nci = fac[n] * inv[n-i] % mod * inv[i] % mod
    mci = fac[n-1] * inv[n-1-i] % mod * inv[i] % mod
    ans = (ans + nci * mci % mod) % mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def prepare(n, MOD):
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def comb(n, r, factorials, invs):
    return factorials[n] * invs[r] * invs[n - r] % MOD


def main():
    n, k = map(int, input().split())
    factorials, invs = prepare(n, MOD)
    ans = 0
    for m in range(min(k, n - 1) + 1):
        ans += comb(n - 1, m, factorials, invs) * comb(n, m, factorials, invs)
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

MAX = 4 * 10 ** 5 + 1
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1

# Inverse
inv = [0] * (MAX + 1)
inv[1] = 1

# Inverse factorial
finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

for i in range(2, MAX + 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 comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD


if N - 1 <= K:
    print(comb(2 * N - 1, N - 1))
else:
    # zero: 0 ~ K
    ans = 0
    for n in range(K + 1):
        ans += comb(N, n) * comb(N - 1, n)
        ans %= MOD
    print(ans)

Submission status: Accepted

Solution code:

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

MAX = 4 * 10 ** 5 + 1
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1

# Inverse
inv = [0] * (MAX + 1)
inv[1] = 1

# Inverse factorial
finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

for i in range(2, MAX + 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 comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD


if N - 1 <= K:
    print(comb(2 * N - 1, N - 1))
else:
    # zero: 0 ~ K
    ans = 0
    for n in range(K + 1):
        ans += comb(N, n) * comb(N - 1, N - n - 1)
        ans %= MOD
    print(ans)

Submission status: Accepted

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


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


mod = 10**9+7  # 出力の制限
N = 2*10**5+1
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

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


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

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

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

# C,Pを求める前処理
m = 4*10**5
mod = 10**9 + 7


fact = [0]*(m+5)
fact_inv = [0]*(m+5)
inv = [0]*(m+5)

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

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

# nCkをmod（素数）で割った余りを求める．ただしn<10**7
# 前処理はm=n+5まで
def cmb(n,k,mod):
    return fact[n] * (fact_inv[k] * fact_inv[n-k] % mod) % mod

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


class CmbMod:
    def __init__(self, n, p):
        """
        二項係数nCr(n個の区別できるものからr個のものを選ぶ組み合わせの数)をpで割った余りを求める
        """
        self.n = n
        self.p = p
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]

    def cmb_mod(self, n, r):
        """
        二項係数nCr(mod p)をO(r)にて計算。nが大きいがrは小さい時に使用。
        """
        numer, denom = 1, 1
        for i in range(r):
            numer = (numer * (n - i)) % self.p
            denom = (denom * (i + 1)) % self.p
        return (numer * pow(denom, self.p - 2, self.p)) % self.p

    def prep(self):
        """
        二項係数nCr(mod p)をO(1)で求める為の前処理をO(N)にて実行。
        """
        for i in range(2, self.n + 1):
            self.fact.append((self.fact[-1] * i) % self.p)
            self.inv.append((-self.inv[self.p % i] * (self.p // i)) % self.p)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % self.p)

    def cmb_mod_with_prep(self, n, r):
        """
        二項係数nCr(mod p)をO(1)で求める。事前にprepを実行する事。
        """
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] * self.factinv[n - r] % self.p


def resolve():
    n, k = map(int, input().split())
    k = min(n - 1, k)
    cmb = CmbMod(n, mod)
    cmb.prep()
    res = 0
    for i in range(k + 1):
        res += (cmb.cmb_mod_with_prep(n, i) * cmb.cmb_mod_with_prep(n - 1, i)) % mod
        res %= mod
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
mod = pow(10, 9) + 7
c1, c2 = 1, 1
n1, n2 = n, n - 1
ans = 1
for r in range(1, min(k + 1, n)):
    c1 = (c1 * n1 * pow(r, mod - 2, mod)) % mod
    c2 = (c2 * n2 * pow(r, mod - 2, mod)) % mod
    n1 -= 1
    n2 -= 1
    ans += (c1 * c2) % mod
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

def getFacts(n, MOD):
    facts = [1] * (n+1)
    for x in range(2, n+1):
        facts[x] = (facts[x-1] * x) % MOD
    return facts
facts = getFacts(2*N, MOD)
def getInvFacts(n, MOD):
    invFacts = [0] * (n+1)
    invFacts[n] = pow(facts[n], MOD-2, MOD)
    for x in reversed(range(n)):
        invFacts[x] = (invFacts[x+1] * (x+1)) % MOD
    return invFacts
invFacts = getInvFacts(2*N, MOD)
def getComb(n, k, MOD):
    if n < k:
        return 0
    return facts[n] * invFacts[k] * invFacts[n-k] % MOD

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

print(ans)

Submission status: Accepted

Solution code:
mod = int(1e9) + 7 # <-- input modulo
maxf = 500000           # <-- input factional limitation

def make_fact(n, k):
    tmp = n
    perm = [i for i in range(k)]
    L = [0 for _ in range(k)]
    for i in range(k):
        L[i] = tmp % (i + 1)
        tmp //= i + 1
    LL = [0 for _ in range(k)]
    for i in range(k):
        LL[i] = perm[L[-i-1]]
        for j in range(L[-i-1]+1, k):
            perm[j-1] = perm[j]
    return LL

def doubling(n, m, modulo=mod):
    y = 1
    base = n
    tmp = m
    while tmp != 0:
        if tmp % 2 == 1:
            y *= base
            if modulo > 0:
                y %= modulo
        base *= base
        if modulo > 0:
            base %= modulo
        tmp //= 2
    return y

def inved(a, modulo=mod):
    x, y, u, v, k, l = 1, 0, 0, 1, a, modulo
    while l != 0:
        x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
        k, l = l, k % l
    return x % modulo

fact = [1 for _ in range(maxf+1)]
invf = [1 for _ in range(maxf+1)]

for i in range(maxf):
    fact[i+1] = (fact[i] * (i+1)) % mod
invf[-1] = inved(fact[-1])
for i in range(maxf, 0, -1):
    invf[i-1] = (invf[i] * i) % mod
n, k = map(int, input().split())
S = 0
if n <= k + 1:
    print(fact[2*n-1]*invf[n]*invf[n-1]%mod)
else:
    S = 0
    for i in range(min(n, k+1)):
        S += invf[i]*invf[i]*invf[n-i-1]*invf[n-i]%mod
        S %= mod
    print(S*fact[n-1]*fact[n]%mod)

Submission status: Accepted

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

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

if k >=n:
  L = 2*n-1
  ansbunsi =1
  for j in range(n-1):
    ansbunsi = ansbunsi*L%mod
    L -= 1
  ansbunbo = 1
  L = n - 1
  for j in range(n-1):
    ansbunbo = ansbunbo*L%mod
    L -= 1
  ansbunbo = modinv(ansbunbo)
  print(ansbunsi*ansbunbo%mod)

else:
  kaijou = [1, 1]
  for j in range(2, n):
    kaijou.append(kaijou[-1]*j%mod)
  
  ans = 0

  for m in range(k+1):
    ansbunsi = (kaijou[n-1]**2)*n%mod
    ansbunbo = kaijou[n-m-1]*kaijou[m]%mod
    ansbunbo = ansbunbo*ansbunbo%mod*(n-m)%mod
    ansbunbo = modinv(ansbunbo)
    ans += ansbunbo*ansbunsi%mod
    ans %= mod
  
  print(ans)

Submission status: Accepted

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

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

if k >=n:
  L = 2*n-1
  ansbunsi =1
  for j in range(n-1):
    ansbunsi = ansbunsi*L%mod
    L -= 1
  ansbunbo = 1
  L = n - 1
  for j in range(n-1):
    ansbunbo = ansbunbo*L%mod
    L -= 1
  ansbunbo = modinv(ansbunbo)
  print(ansbunsi*ansbunbo%mod)

else:
  kaijou = [1, 1]
  for j in range(2, n+1):
    kaijou.append(kaijou[-1]*j%mod)
  
  ans = 0

  for m in range(k+1):
    ansbunsi = kaijou[n]*kaijou[n-1]%mod
    ansbunbo = kaijou[m]*kaijou[n-m]%mod
    ansbunbo = ansbunbo*kaijou[n-m-1]%mod
    ansbunbo = ansbunbo*kaijou[m]%mod
    ansbunbo = modinv(ansbunbo)
    ans += ansbunbo*ansbunsi
    ans %= mod
  
  print(ans)

Submission status: Accepted

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

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

if k >=n:
  L = 2*n-1
  ansbunsi =1
  for j in range(n-1):
    ansbunsi = ansbunsi*L%mod
    L -= 1
  ansbunbo = 1
  L = n - 1
  for j in range(n-1):
    ansbunbo = ansbunbo*L%mod
    L -= 1
  ansbunbo = modinv(ansbunbo)
  print(ansbunsi*ansbunbo%mod)

else:
  kaijou = [1, 1]
  for j in range(2, k+n+1):
    kaijou.append(kaijou[-1]*j%mod)
  
  ans = 0

  for m in range(k+1):
    ansbunsi = kaijou[n]*kaijou[n-1]%mod
    ansbunbo = kaijou[m]*kaijou[n-m]%mod
    ansbunbo = ansbunbo*kaijou[n-m-1]%mod
    ansbunbo = ansbunbo*kaijou[m]%mod
    ansbunbo = modinv(ansbunbo)
    ans += ansbunbo*ansbunsi
    ans %= mod
  
  print(ans)

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
factmod=[1 for i in range(n+1)]
for i in range(n):
    factmod[i+1]=(factmod[i]*(i+1))%mod
#print(factmod)
ans=0
for m in range(min(k+1,n)):
    a=factmod[-1]*pow((factmod[m]*factmod[n-m])%mod,mod-2,mod)
    b=factmod[n-1]*pow((factmod[m]*factmod[n-m-1])%mod,mod-2,mod)
    ans=(ans+(a*b))%mod
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 = 2*(10**5)+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
a,b=map(int,input().split())
c=min(a,b)
s=0
for i in range(0,c+1):
    s+=cmb(a,i,10**9+7)*cmb(a-1,i,10**9+7)
print(s%(10**9+7))

Submission status: Accepted

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

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

g1=[1,1]
g2=[1,1]
inv=[0,1]
for i in range(2,1000003):
  g1.append((g1[-1]*i)%mod)
  inv.append((-inv[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inv[-1])%mod)
P=0
for i in range(min(N,K+1)):
  P=(P+cmb(N,i)*cmb(N-1,i))%mod
print(P)

Submission status: Accepted

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

mod = 10 ** 9 + 7
fact = [1] * (n + 1)
ifact = [1] * (n + 1)

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


def comb(x, y):
    if y < 0 or y > x:
        return 0
    return (fact[x] * ifact[x - y] * ifact[y]) % mod


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

Submission status: Accepted

Solution code:
def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euc(a, mod)
    return x % mod


def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split()))
    c = [1, 1]  # comb(N, n), comb(N - 1, n)
    ans = 0
    for n in range(min(N - 1, K) + 1):
        ans += c[0] * c[1]
        ans %= MOD
        n_inv = mod_inv(n + 1, MOD)
        c[0] *= N - n
        c[0] *= n_inv
        c[0] %= MOD
        c[1] *= N - 1 - n
        c[1] *= n_inv
        c[1] %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

class Combination:                                      # 計算量は O(n_max + log(mod))
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):                     # 階乗(= n_max !)の逆元を生成
            f = f * i % mod                             # 動的計画法による階乗の高速計算
            fac.append(f)                               # fac は階乗のリスト
        f = pow(f, mod-2, mod)                          # 階乗から階乗の逆元を計算。フェルマーの小定理より、　a^-1 = a^(p-2) (mod p) if p = prime number and p and a are coprime
                                                        # python の pow 関数は自動的に mod の下での高速累乗を行ってくれる
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):                   # 上記の階乗の逆元から階乗の逆元のリストを生成（＝ facinv ）
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def H(self, n, r):                                  # (箱区別:〇　ボール区別:×　空箱:〇)　重複組み合わせ nHm
        if (n == 0 and r > 0) or r < 0: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod


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

k = min(k,n-1)
res = 0
for l in range(k+1):
    res += C(n,l)*C.H(n-l,l)
print(res%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N = 10**6  # 10**6が限界
factorial_mod = [1, 1]  # factrial_mod[i] := i! mod p
modular_multiplicative_inverse = [0, 1]  # モジュラ逆数 := i^(-1) ≡ x (mod p) となるx
factorial_inverse_mod = [1, 1]  # factrial_inverse_mod[i] := (i!)^(-1) mod p
 
for i in range(2, N + 1):  # O(N)
    factorial_mod.append((factorial_mod[i - 1] * i) % MOD)
    modular_multiplicative_inverse.append((-modular_multiplicative_inverse[MOD % i] * (MOD // i)) % MOD)
    factorial_inverse_mod.append((factorial_inverse_mod[i-1] * modular_multiplicative_inverse[i]) % MOD)
 
def nCr_mod(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return factorial_mod[n] * factorial_inverse_mod[r] * factorial_inverse_mod[n - r] % MOD

# ---------------------- #
 
n, k = (int(x) for x in input().split())
ans = 0
for i in range(min(n - 1, k) + 1):
    # nCi * n-iHi = nCi * n-1Ci
    ans += nCr_mod(n, i) * nCr_mod(n - 1, i)
    ans %= MOD
print(ans)

Submission status: Accepted

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

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 = mod
N = 4 * 10 ** 6 + 10 # 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)
    
def shikiri(a,b):
    return fact[a+b]*factinv[a]*factinv[b]%mod

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

if m==1:
    ans-=1
print(ans)

Submission status: Accepted

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


def read():
    N, K = list(map(int, input().strip().split()))
    return N, K


def binom_preprocess(n, MOD=10**9+7):
    f = [0 for i in range(n+1)]  # n!
    invf = [0 for i in range(n+1)]  # (n!)^-1
    f[0] = 1
    f[1] = 1
    invf[0] = 1
    invf[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] * i % MOD
    invf[n] = pow(f[n], MOD-2, MOD)
    for i in range(n, 2, -1):
        invf[i-1] = invf[i] * i % MOD
    return f, invf


def binom(n, k, f, invf, MOD=10**9+7):
    if n < k or n < 0 or k < 0:
        return 0
    else:
        return (f[n] * invf[k] % MOD) * invf[n-k] % MOD


def solve(N, K, MOD=10**9+7):
    # k: 人数0の部屋の数
    # N人を(N-k)部屋に押し込む方法を考える
    f, invf = binom_preprocess(N, MOD)
    ans = 0
    for k in range(0, min(N, K+1)):
        ans += binom(N, k, f, invf, MOD) * binom(N-1, k, f, invf, MOD)
        ans %= MOD
    return ans


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Accepted

Solution code:
class Combination:
  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 = map(int,input().split())
ans = 1
MOD = 10**9+7
comb = Combination(2*10**5+1)
for i in range(1, min(n, k+1)):
  ans += (comb(n,i)*comb(n-1, i))%MOD
  ans %= MOD

print(ans)

Submission status: Accepted

Solution code:

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

MAX = 6 * 10 ** 5 + 1
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1

# Inverse
inv = [0] * (MAX + 1)
inv[1] = 1

# Inverse factorial
finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

for i in range(2, MAX + 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 comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD


def comb_rep(n, k):
    return comb(n + k - 1, n - 1)


if K >= N - 1:
    print(comb_rep(N + 1, N - 1))
else:
    ans = 0
    for i in range(K + 1):
        ans += comb(N, i) * comb_rep(N - i, i) % MOD
        ans %= MOD
    print(ans)

Submission status: Accepted

Solution code:
# nCk ( O(N) )
N_MAX = 10**6
MOD = 10**9 + 7
fac, finv, inv = [0]*N_MAX ,[0]*N_MAX, [0]*N_MAX
def com_init():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, N_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 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

com_init()
n,k = map(int, input().split())
ans = 0
max_k = min(n-1,k)
for i in range(max_k+1):
    ans += (com(n,i)*com(n-1,i))
    ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
class Combination:
    def __init__(self,N,P=10**9+7):
        if N > 10**7:
            self.fact = lambda x: x * self.fact(x-1) % P if x > 2 else 2
            self.perm = lambda x, r: x * self.perm(x-1,r-1) % P if r > 0 else 1
            self.cmb = lambda n,r: (self.perm(n,min(n-r,r)) * pow(self.fact(min(n-r,r)) ,P-2 ,P) % P) if r > 0 else 1
        else:
            self.__fact = [1] * (N+1)
            self.__inv = [1] * (N+1)
            self.__inv_fact = [1] * (N+1)
            for i in range(2,N+1):
                self.__fact[i] = self.__fact[i-1] * i % P
                self.__inv[i] = - self.__inv[P%i] * (P//i) % P
                self.__inv_fact[i] = self.__inv_fact[i-1] * self.__inv[i] % P
            self.fact = lambda n: self.__fact[n]
            self.perm = lambda n,r: self.__fact[n] * self.__inv_fact[n-r] % P
            self.cmb = lambda n,r: (self.__fact[n] * self.__inv_fact[n-r] * self.__inv_fact[r] % P) if r > 0 else 1






import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    from collections import deque
    
    n,k = LMIIS()
    cmb = Combination(2*n)
    ans = 1
    for i in range(1,min(n,k+1)):
        ans = (ans + cmb.cmb(n,i) * cmb.cmb(n-1,i)) % MOD
    print(ans)

    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N = 10**6  # 10**6が限界
factorial_mod = [1, 1]  # factrial_mod[i] := i! mod p
modular_multiplicative_inverse = [0, 1]  # モジュラ逆数 := i^(-1) ≡ x (mod p) となるx
factorial_inverse_mod = [1, 1]  # factrial_inverse_mod[i] := (i!)^(-1) mod p

for i in range(2, N + 1):  # O(N)
    factorial_mod.append((factorial_mod[i - 1] * i) % MOD)
    modular_multiplicative_inverse.append((-modular_multiplicative_inverse[MOD % i] * (MOD // i)) % MOD)
    factorial_inverse_mod.append((factorial_inverse_mod[i-1] * modular_multiplicative_inverse[i]) % MOD)

def nCr_mod(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return factorial_mod[n] * factorial_inverse_mod[r] * factorial_inverse_mod[n - r] % MOD

def nPr_mod(n, r):
    return factorial_mod[n] * factorial_inverse_mod[n - r] % MOD

# ---------------------- #

n, k = (int(x) for x in input().split())
ans = 0
for i in range(min(n - 1, k) + 1):
    # nCi * n-iHi = nCi * n-1Ci
    ans += nCr_mod(n, i) * nCr_mod(n - 1, i)
    ans %= MOD
print(ans)