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:
def main():
    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
    import math

    #inf = 10**17
    mod = 10**9 + 7

    max_n = 2*(10**5)
    fac, inv = [1]*(max_n+1), [0]*(max_n+1)
    for i in range(2, max_n+1):
        fac[i] = fac[i-1] * i % mod
    inv[-1] = pow(fac[-1], mod-2, mod)
    for i in range(max_n, 0, -1):
        inv[i-1] = inv[i] * i % mod

    # nCrを求める
    def ncr(n, r):
        return fac[n]*inv[r]*inv[n-r]%mod

    n, k = map(int, input().split())
    res = 0
    # i:空き部屋の数
    for i in range(n):
        if i > k:
            continue
        res += ncr(n, i) * ncr(n-1, i)
        res %= mod
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    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
    import math

    #inf = 10**17
    mod = 10**9 + 7

    max_n = 2*(10**5)
    fac, inv = [1]*(max_n+1), [0]*(max_n+1)
    for i in range(2, max_n+1):
        fac[i] = fac[i-1] * i % mod
    inv[-1] = pow(fac[-1], mod-2, mod)
    for i in range(max_n, 0, -1):
        inv[i-1] = inv[i] * i % mod

    # nCrを求める
    def ncr(n, r):
        return fac[n]*inv[r]*inv[n-r]%mod

    n, k = map(int, input().split())
    res = 0
    # i:空き部屋の数
    for i in range(n):
        if i > k:
            continue
        res += ncr(n, i) * ncr(n-1, i)
        res %= mod
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, kk = map(int, input().split())

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

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % mod

    ans = [1]

    for k in range(1, n):
        ans.append(nCr(n-1, k)*nCr(n, k) % mod)

    print(sum(ans[:min(kk+1, n)]) % mod)


main()

Submission status: Accepted

Solution code:
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

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


def main():
    MOD = 10 ** 9 + 7

    N, K = map(int, input().split())
    K = min(K, N - 1)  # K=最大空室数->N部屋空室は不可能

    calc = Calc(max_value=N * 2, mod=MOD)

    ans = 0
    for v in range(K + 1):  # 空室数
        ans = (ans + (calc.combination(N, v) * calc.combination(v + (N - v) - 1, v)) % MOD) % MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

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


def main():
    MOD = 10 ** 9 + 7

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

    calc = Calc(max_value=N * 2, mod=MOD)

    ans = 0
    for v in range(K + 1):  # 空室数
        ans = (ans + calc.combination(N, v) * calc.combination(v + (N - v) - 1, v)) % MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right


def combination_mod(n, r, mod):
    # if r > n:
    #     return 0  # このような通りの数は無いため便宜上こう定義する
    r = min(r, n - r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
    return nf * pow(rf, mod - 2, mod) % mod


def ret_list_combination_mod(n, r, mod):
    ret = [1]
    if r > n:
        return 0  # このような通りの数は無いため便宜上こう定義する
    # r = min(r, n - r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
        ret.append(nf * pow(rf, mod - 2, mod) % mod)
    return ret

# https://atcoder.jp/contests/abc156/tasks/abc156_e


MOD = 10**9 + 7
n, k = read_ints()
# n<=kのときは簡単
if n <= k:
    print(combination_mod(n + n - 1, n, MOD))
    exit()
# n>kのときはどうしよう

ans = 1
nCa = ret_list_combination_mod(n, k, MOD)
n_1Ca = ret_list_combination_mod(n - 1, k, MOD)
for a in range(1, k + 1):
    ans += nCa[a] * n_1Ca[a]  # ここ高速化しないと厳しいかな
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

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

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

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

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

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

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

print(ans)

Submission status: Accepted

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

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

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

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

    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

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

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

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

print(ans)

Submission status: Accepted

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

fact = [1]*(n+1)
ans = 0
for i in range(1,n+1):
    fact[i] = fact[i-1]*i
    fact[i] %= mod
invfact = [1] * (n+1)
invfact[-1] = pow(fact[-1],mod-2,mod)
for i in range(n-1,0,-1):
    invfact[i] = (invfact[i+1]*(i+1))%mod
def C(x,y):
    if x<=y:return 1
    return fact[x]*invfact[y]*invfact[x-y]%mod


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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
fact=[1]
for i in range(1,2*n):
  fact.append((fact[i-1]*(i+1))%(10**9+7))
factinv=[]
for i in range(n):
  factinv.append(pow(fact[i],10**9+5,10**9+7))
if k==1:
  print((n*(n-1))%(10**9+7))
elif k>=n-1:
  print((fact[2*n-2]*factinv[n-1]*factinv[n-2])%(10**9+7))
else:
  ans=1
  for i in range (k):
    ans=(ans+fact[n-1]*factinv[i]*factinv[n-i-2]*fact[n-2]*factinv[i]*factinv[n-i-3])%(10**9+7)
  print(ans)

Submission status: Accepted

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

MOD = 10**9 + 7
fac = [1 for k in range(200010)]
inv = [1 for k in range(200010)]
finv = [1 for k in range(200010)]
for k in range(2,200010):
    fac[k] = (fac[k-1]*k)%MOD
    inv[k] = (MOD - inv[MOD%k] * (MOD // k))%MOD
    finv[k] = (finv[k - 1] * inv[k]) % MOD;
def nCr(n,r):
    return (fac[n]*finv[r]*finv[n-r])%MOD

ans = 0
for i in range(min(n,K+1)):
    ans += nCr(n,i)*nCr(n-1,n-i-1)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
mod = int(10 ** 9) + 7

def modinv(x, m = mod):
    b = m
    u = 1
    v = 0
    while b:
        t = x // b
        x -= t * b
        x, b = b, x
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u

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

    if k > n-1:
        k = n-1

    factorial = [None for _ in range(200001)]
    factorial[0] = 1
    factorial[1] = 1
    for i in range(2, 200001):
        factorial[i] = (factorial[i-1] * i) % mod

    posCount = [None for _ in range(n+1)]
    for i in range(n+1):
        posCount[i] = (factorial[n] * modinv((factorial[i] * factorial[n-i]) % mod)) % mod

    placeCount = [None for _ in range(n+1)]
    placeCount[0] = 0
    for i in range(1, n+1):
        placeCount[i] = (factorial[n-1] * modinv((factorial[i-1] * factorial[(n-1)-(i-1)]) % mod)) % mod

    ans = 0
    for i in range(-1, -k-2, -1):
        ans = (ans + (posCount[i] * placeCount[i])) % mod
    if k == 1:
        ans -= 1
        if ans < 0:
            ans += mod

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
N,k = map(int, input().split())

# 0人の部屋がt個あるとすると、n-t個の部屋にn人がいる。
# k!=1のとき0<=t<=min(k, n-1)
# k==1のときt=1
res = 0
fact = [0]*(N+1)
ifact = [0]*(N+1)
inv = [0]*(N+1)
p=10**9+7

dic = dd(int)

def combination(n,fact,ifact):
    fact[0] = 1
    fact[1] = 1
    ifact[0] = 1
    ifact[1] = 1
    inv[1] = 1
    for i in range(2,n+1):
        fact[i] = (fact[i-1]*i)%p
        inv[i] = p - inv[p%i]*(p//i)%p
        ifact[i] = (ifact[i-1]*inv[i])%p
def op(n,k):
    if (n,k) in dic.keys():
        return dic[(n,k)]
    if k<0 or k>n or n<0:
        return 0
    dic[(n,k)] = (fact[n]*ifact[k]*ifact[n-k])%(10**9+7)
    return dic[(n,k)]

combination(N,fact,ifact)
for t in range(0, min(k, N-1)+1):
    # n-t個の部屋にn人を入れる。ただし、どの部屋にも1人以上いる必要がある
    # n個の部屋のうちどのt個を0人にするかでnCt
    # n-t個の部屋の人数でn-1Cn-t-1
    res += (op(N-1, N-t-1) * op(N, t))%p
print(res%p)

Submission status: Accepted

Solution code:
U = 2 * 10 ** 5
mod = 10 ** 9 + 7


class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


if __name__ == "__main__":
    N, K = map(int, input().split())
    comb = Combination(U + 5, mod)

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
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()))

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

co = Combination(200006)
n,m = inpl()
if m >= n:
    m = n-1
res = 1
if m == 1:
    print(co(n-1,n-2) * n)
    quit()
else:
    for i in range(m):
        tmp = i+1
        res += co(n-1,n-tmp-1) * co(n,tmp)
        res %= mod
        # print(res)
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


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

max_empty = min(n - 1, k)
comb = Combination(10 ** 6, MOD)
ans = 0
for i in range(0, max_empty + 1):
    box = n - i
    ball = n
    ans += comb.combination(ball - 1, box - 1) * comb.combination(n, box)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
P = 10**9+7
N = 700000 #使う最大値以上にする、値に注意4*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2,N+1):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b):
    if a<b: return 0 # error
    return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P

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

ans = 0
#0が0~min(n-1, k)
num = min(n-1, k) + 1
for i in range(num):
    heya = n - i
    #0
    ret = comb(n, i)
    person = n - heya
    ret = (ret * comb(person+heya-1, person))%P
    ans += ret
print(ans%P)

Submission status: Accepted

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

MOD = 10**9+7

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

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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


n, k = map(int, read().split())
mod = 10 ** 9 + 7
max_n = 2 * 10 ** 5 + 1
ans = 0
fac = [1] * max_n
inv = [1] * max_n
ifac = [1] * max_n
for i in range(2, max_n):
    fac[i] = fac[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    ifac[i] = ifac[i - 1] * inv[i] % mod

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

Submission status: Accepted

Solution code:
# comb_mod(n, c, r, mod, fac, den) ≡ nCr
def prepare(n, mod):
    # fac[i] ≡ i!
    fac = [1]
    for i in range(1, n+1):
        fac.append((fac[-1] * i) % mod)

    # rec ≡ 1 / n!
    rec = pow(fac[-1], mod-2, mod)

    # den[i] ≡ 1 / i!
    den = [1 for _ in range(n+1)]
    den[n] = rec
    for i in range(n-1, 0, -1):
        rec = (rec * (i+1)) % mod
        den[i] = rec
    
    return fac, den

def comb_mod(n, r, mod, fac, den):
    return (fac[n] * den[r] * den[n - r]) % mod

n, k = map(int, input().split())
mod = 10**9 + 7
fac, den = prepare(2*n-1, mod)

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

Submission status: Accepted

Solution code:
def nCr_frL(n,r,mod):
    ret=[1,n%mod]
    for i in range(2,r+1):
        inv=pow(i,mod-2,mod)
        ret.append((ret[-1]*(n-i+1)*inv)%mod)
    return ret

N,K=map(int,input().split())
MOD=10**9+7
com1=nCr_frL(N,N,MOD) # nCi
com2=nCr_frL(N-1,N-1,MOD) # n-1Ci

if K>N-1:
    K=N-1
ans=0
for m in range(K+1):
    ans+=(com1[m]*com2[N-m-1])%MOD
print(ans%MOD)

Submission status: Accepted

Solution code:
N, K = map(int, open(0).read().split())

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

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    
# Inverse factorial
finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

def comb(n, k):
    return fac[n] * finv[n - k] * finv[k]

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

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

Submission status: Accepted

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

MOD = 10 ** 9 + 7

def main():
    N, K = (int(_) for _ in input().split())

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

    ret = 0
    for m in range(min(K, N-1) + 1):
        ret += (fact[N] * ifact[m] * ifact[N-m])%MOD * (fact[N-1] * ifact[N-m-1] * ifact[m])%MOD
        ret %= MOD
    print(ret%MOD)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    N,K = map(int,input().split())
    MOD = 10**9+7
    
    fac = [0]*(N+1)
    invfac = [0]*(N+1)
    fac[0],fac[1] = 1,1
    invfac[0],invfac[1] = 1,1
    
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    invfac[-1] = pow(fac[-1],MOD-2,MOD)
    for i in range(N,0,-1):
        invfac[i-1] = (invfac[i]*i)%MOD
        
    def comb(x,y):
        return (fac[x]*invfac[y]*invfac[x-y])%MOD
        
    ans = 0
    for i in range(min(N,K+1)):
        a = comb(N,i)
        b = comb(N-1,N-i-1)
        ans += (a*b)%MOD
        
    print(ans%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

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


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

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

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret
N,K = map(int,input().split())

ans=0
MOD=10**9+7

F= FactMod(N,MOD)

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
#階乗
F = 200005
mod = 10**9+7
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[F-1]=pow(fact[F-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

ans=1
for i in range(1,min(n,k+1)):
    comb=(fact[n]*inv[i]*inv[n-i])%mod
    h=(fact[n-1]*inv[i]*inv[n-1-i])%mod
    ans=(ans+comb*h)%mod
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
if n - 1 < k:
    k = n-1
mod = 10**9+7
cmb1 = [1]*(n+1)
cmb2 = [1]*n
x = [0]*(n+1)
def Pow(a, n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod
for i in range(1,n+1):
    x[i] = Pow(i, mod-2)
for i in range(1,n+1):
    cmb1[i] = cmb1[i-1]*(n+1-i)%mod*x[i]%mod
for i in range(1,n):
    cmb2[i] = cmb2[i-1]*(n-i)%mod*x[i]%mod
ans = 0    
for i in range(k+1):
    ans = ((cmb1[i]*cmb2[i])%mod + ans)%mod
print(ans)

Submission status: Accepted

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

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)

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

res = []
for i in range(n):
    res.append((cmb(n, i, p) * cmb(n - 1, i, p)) % p)

if n > k:
    print(sum(res[:k + 1]) % p)
else:
    print(sum(res) % p)

Submission status: Accepted

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

    fact = [0 for i in range(NMAX+5)]
    fact[0] = 1
    invfact = [0 for i in range(NMAX+5)]
    invfact[0] = 1

    for i in range(NMAX):
        fact[i+1] = (fact[i]*(i+1))%(MOD)

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

    ans = 0
    if k >= n:
        k = n-1
    for i in range(k+1):
        z = fact[n]*invfact[i]%MOD
        z = z*invfact[n-i]%MOD
        h = fact[n-1]*invfact[i]%MOD
        h = h*invfact[n-i-1]%MOD
        ans += z*h%MOD

    print(ans%MOD)

main()

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

class Combination(object):
	def __init__(self, N, con):
		self.fac = [0] * (N + 1)
		self.inv = [0] * (N + 1)
		self.finv = [0] * (N + 1)
		self.fac[0], self.fac[1] = 1, 1
		self.inv[1] = 1
		self.finv[0], self.finv[1] = 1, 1

		# 前計算
		for i in range(2, N + 1):
			self.fac[i] = self.fac[i - 1] * i % con
			self.inv[i] = self.inv[con % i] * (con - (con // i)) % con
			self.finv[i] = self.finv[i - 1] * self.inv[i] % con

	def com(self, N, k):
		return (self.fac[N] * self.finv[k] * self.finv[N - k]) % con

#処理内容
def main():
	N, K = getlist()
	if K >= N:
		Com = Combination(2 * N - 1, con)
		ans = Com.com(2 * N - 1, N)
		print(ans)

	else:
		Com1 = Combination(N, con)
		Com2 = Combination(N - 1, con)
		ans = 0
		for i in range(1, K + 1):
			ans += Com1.com(N, i) * Com2.com(N - 1, i)
			ans %= con
		ans = (ans + 1) % con
		print(ans)
	
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n, k = map(int, input().strip().split())
k=min(k,n-1)
MOD=10**9+7

# a*a**(p-2) mod p (Fermat's little theorem)
def modInv(x,m=10**9+7):
    return pow(x,m-2,m)

class combMod:
    def __init__(self,maxN,mod=10**9+7):
        self.maxN=maxN
        self.mod=mod
        self.fac=[None]*(maxN+1) # fac[0]=1, fac[1]=1, fac[2]=2 ... fac[maxN]
        self.ifac=[None]*(maxN+1)
        # self.ifac[0]=1
        
    def calc_fact(self): # make the table
        self.fac[0]=1
        for i in range(1,self.maxN+1):
            self.fac[i] = self.fac[i-1]*i % self.mod
        self.ifac[-1] = modInv(self.fac[-1])
        for i in range(self.maxN,0,-1):
            self.ifac[i-1] = self.ifac[i]*i % self.mod
    def modnCr(self,n, r,mod=None):
        if mod is None:
            mod=self.mod
        denom = self.fac[n]
        numer = self.ifac[r] * self.ifac[n-r] % mod
        return  denom * numer % mod

combMod=combMod(2*n+1)
combMod.calc_fact()
ans=0
for ki in range(k+1):
    ans += combMod.modnCr(n, ki)*combMod.modnCr(n-ki-1+ki, ki)%MOD
print(ans%MOD)

Submission status: Accepted

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

fact = [0] * (n+1)
inv = [0] * (n+1)

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

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

if k >= n:
	k = n-1

def C(a,b):
	out = fact[a]
	out *= inv[b]
	out %= mod
	out *= inv[a-b]
	out %= mod
	return out

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

print(ans)

Submission status: Accepted

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

FAC = [1]
INV = [1]
for i in range(1,2*n+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))

def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

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