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:
#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"
exit $?
'''
import sys


def _ia(): return [int(x) for x in sys.stdin.readline().strip().split()]


MOD = 10**9 + 7


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


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


def pow(a, n):
    ret = 1
    an = a
    while n > 0:
        if n & 1 == 1:
            ret = (ret * an) % MOD
        an = (an * an) % MOD
        n >>= 1
    return ret


def div(a, b):
    if a % b == 0:
        return a//b
    return (a * pow(b, MOD-2)) % MOD


def comb(n, k):
    global fact, ifact
    if k == 0:
        return 1
    return mul(mul(fact[n], ifact[n-k]), ifact[k])


n, k = _ia()
k = min(n-1, k)

fact = [1] * (n+1)
ifact = [1] * (n+1)
for i in range(1, n+1):
    fact[i] = mul(i, fact[i-1])
    ifact[i] = div(ifact[i-1], i)

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

Submission status: Accepted

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

mod = 10**9+7

m = 10**5 * 4 +10 
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

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

ans = 0
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:
n,k=map(int,input().split())
mod=10**9+7
bikkuri=[0 for i in range(2*n+5)]
bikkuri[0]=1
gyaku=[0 for i in range(2*n+5)]
gyaku[0]=1
for i in range(1,2*n+5):
    bikkuri[i] = (i * bikkuri[i-1])%mod
    gyaku[i]=pow(bikkuri[i], mod-2, mod)
def comb(a,b):
    return bikkuri[a]*gyaku[b]%mod*gyaku[a-b]%mod
if n<=k:
    ans=comb(2*n-1,n)%mod
elif k==1:
    ans=n*n-1
    ans%=mod
else:
    ans=0
    for i in range(k+1):
        if i==0:
            ans+=1
            ans%=mod
        else:
            ans+=comb(n,n-i)*comb(n-1,i)
            ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import log10, ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k = MAP()

lim = 10**6  # 必要そうな階乗の限界を入れる
factorial = [1]
for i in range(1, lim):
    factorial.append(factorial[i-1] * i % mod)

def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod

def C(n, r):
    return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod
x_inv = [0] * lim
x_inv[-1] = power(factorial[-1], mod-2)
for i in range(lim-2, -1, -1):
    x_inv[i] = x_inv[i+1] * (i+1) % mod

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

Submission status: Accepted

Solution code:
import sys
import itertools

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


class Comb(object):

    def __init__(self, n, MOD=1e9 + 7):
        self.MOD = MOD

        fac = [0] * (n + 10)
        finv = [0] * (n + 10)
        inv = [0] * (n + 10)

        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1

        for i in range(2, n + 10):
            fac[i] = fac[i - 1] * i % MOD
            inv[i] = MOD - inv[int(MOD % i)] * (MOD // i) % MOD
            finv[i] = finv[i - 1] * inv[i] % MOD
        self.fac = fac
        self.finv = finv
        self.inv = inv

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

    def calc_h(self, n, k):
        return self.calc_c(n + k - 1, k)


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

comb = Comb(n, MOD)

ans = 0

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

print(ans % MOD)

Submission status: Accepted

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

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

	tmp *= comb
	tmp %= mod

	H *= n-i
	H %= mod
	H *= pow(i, mod-2, mod)
	H %= mod

	tmp *= H
	tmp %= mod

	ans += tmp
	ans %= mod

print(ans)

Submission status: Accepted

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

mod = 10 ** 9 + 7
f = [1]
for i in range(1,2*n+1):
    f.append((f[-1] * i) % mod)
def comb(n,r):
    return f[n] * (pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod) % mod

ans = comb(2*n-1, n)
if n-1 <= k:
    print(ans)
    sys.exit()

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

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

inv_table = [0]+[1]
for i in range(2,k+1):
  inv_table.append(-1*(MOD//i)*inv_table[MOD%i] %MOD)

comb_sum=1
fact=1
comb1=1
comb2=1
for i in range(1,k+1):
  comb1=(comb1*(n-i+1)*inv_table[i])%MOD
  comb2=(comb2*(n-i)*inv_table[i])%MOD
  comb=(comb1*comb2)%MOD
  comb_sum+=comb

print(comb_sum%MOD)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[解説AC]
一回の操作で行うことは動く人を1人決める+動き先を1つ決める
⇒0人の部屋は選べない
⇒0人の部屋を固定して考える.
0人の部屋をm個作る場合(0 <= m <= min(n-1,k))
nCm(n個のうちm個選ぶ)(移動元) * n-mHm(n-m個のうち重複ありでm個選ぶ)(移動先)
"""
def C(n,r):
    return fact[n] * pow(fact[n-r],mod-2,mod) * pow(fact[r],mod-2,mod) % mod


n,k = LI()

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

ans = 0

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

Submission status: Accepted

Solution code:
import sys
from math import factorial
n, k = [int(i) for i in sys.stdin.readline().split()]
mod = 10**9+7
fact_ls = [1]
res = 1
for i in range(1, n+1):
    res = res * i % mod
    fact_ls.append(res)

def my_fact(r):
    return fact_ls[r]

def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    # [x,y]
    return [w[0], w[1]]


# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m

def nCr(n, r, mod):
    a = my_fact(r)
    b = 1
    for i in range(1, r + 1):
        b = b * (n - i + 1) % mod
    a = mod_inv(a, mod)
    return b * a

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

def calc_func(n, r):
    a = my_fact(r)
    c = my_fact(n - r)
    b = my_fact(n)
    d = my_fact(n-1)
    e = my_fact(n-1-r)
    a = mod_inv(a, mod)
    c = mod_inv(c, mod)
    e = mod_inv(e, mod)
    return b * a * c % mod * d * e * a % mod

res = 1
for i in range(1, min(n, k + 1)):
    res = (res + calc_func(n, i)) % mod
print(res)

Submission status: Accepted

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

mod = 10 ** 9 + 7
f = [1]
for i in range(1,2*n+1):
    f.append((f[-1] * i) % mod)
def comb(n,r):
    return f[n] * (pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod) % mod

ans = comb(2*n-1, n)
if n-1 <= k:
    print(ans)
    sys.exit()

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

print(ans)

Submission status: Accepted

Solution code:
def pow(x, n, mod=None):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n >>= 1
    return ret
n,k = map(int,input().split())
mod = 10**9+7
fact = [None]*(1+n)
finv = [None]*(1+n)
fact[0] = 1
for i in range(1,n+1):
    fact[i] = (fact[i-1]*i)%mod
finv[n] = pow(fact[n],mod-2, mod=mod)
for i in range(n,0,-1):
    finv[i-1] = (finv[i]*i)%mod
def comb(n,k):
    tmp = (finv[n-k]*finv[k])%mod
    return (tmp*fact[n])%mod
ans = 0
for m in range(min(n,k+1)):
    ans = (ans+comb(n,m)*comb(n-1,m))%mod
print(ans)

Submission status: Accepted

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

ans = 0
lim = 2*(10**5) + 5
mothers = [1] * lim
mothers_inv = [1] * lim
for i in range(1, lim):
    mothers[i] = mothers[i-1] * i % mod
    mothers_inv[i] = pow(mothers[i], mod-2, mod)


def calc(n,k):
    child = mothers[n] * mothers_inv[n-k] % mod
    mother_inv = mothers_inv[k]
    return((child * mother_inv)%mod)

def calc2(n,k):
    child = 1
    for i in range(n, n-k, -1):
        child = child * i % mod
    mother_inv = mothers_inv[k]
    return((child * mother_inv)%mod)

if( n <= k+1):
    ans = calc2(2*n-1, n-1)
    print(ans)
    exit()

ans = calc2(2*n-1, n-1)

for i in range(1,n-k):
    if(i ==1):
        c1 = 1
    else:
        c1 = calc(n-1, i-1)

    c2 = calc(n, i)
    ans = (ans - c1 * c2)%mod


print(ans)

Submission status: Accepted

Solution code:
# min(n-1,k)以下の自然数mに対してnCm*n-1Cn-m-1の和を求める
n, k = map(int, input().split())
p = 10 ** 9 + 7
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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


def cmb(n, r):
    return g1[n] * g2[r] * g2[n - r] % p


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

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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


n,k = LI()

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

ans = 0

for i in range(min(n,k+1)):
    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())
MOD = 10**9 + 7

from math import factorial
class Facts():
    """
    階乗のメモ化
    組み合わせ数、順列数の計算を高速に行う
    """
    def __init__(self, max_num=2*10**5, p=10**9 + 7):
        self.p = p
        self.max_num = max_num
        self.fact = [1] * (self.max_num + 1)
        self.ifact = [1] * (self.max_num + 1)
        for i in range(1, self.max_num + 1):
            self.fact[i] = self.fact[i-1] * i
            self.fact[i] %= self.p
            self.ifact[i] = self.power_func(self.fact[i], self.p-2)

    def comb(self, n, k):
        """ nCk mod p を求める """
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a = self.fact[n]
        return (a*self.ifact[k] * self.ifact[n-k]) % self.p


    def power_func(self, a, b):
        """ a^b mod p　を繰り返し二乗法で求める """
        if b == 0:
            return 1
        if b % 2 == 0:
            d = self.power_func(a, b//2)
            return d*d % self.p
        if b % 2 == 1:
            return (a*self.power_func(a, b-1)) % self.p

facts = Facts()

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

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

inv_table = [0]+[1]
for i in range(2,k+1):
  inv_table+=[inv_table[MOD%i]*(MOD-int(MOD/i))%MOD]

comb_sum=1
fact=1
comb1=1
comb2=1
for i in range(1,k+1):
  comb1=(comb1*(n-i+1)*inv_table[i])%MOD
  comb2=(comb2*(n-i)*inv_table[i])%MOD
  comb=(comb1*comb2)%MOD
  comb_sum+=comb

print(comb_sum%MOD)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
mod = 10**9+ 7 
def power_(n, p, mod):
    if p == 1:
        return n
    if p % 2 == 0:
        return (power_(n, p//2, mod) ** 2) % mod
    else:
        return n * (power_(n, p//2, mod) ** 2) % mod
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
#a/b = a*(b`)となるb`を求める
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod
fact = [1 for i in range(n*2+1)]
for i in range(1,n*2+1):
    fact[i] = (fact[i-1] * i) % mod
if k + 1 >= n:
    child = fact[n * 2  - 1]
    mother = mod_inv(fact[n], mod) * mod_inv(fact[n-1], mod)
    print((child * mother) % mod)
else:
    #k人までは自由に振り分け、そのあとはnCn-k
    bow = n - k - 1
    """
    child = fact[bow + k]
    mother = (mod_inv(fact[k], mod) * mod_inv(fact[bow], mod)) % mod
    combi = (fact[n] * mod_inv(fact[n - k],mod) * mod_inv(fact[k],mod)) % mod
    aa = power_(n,k,mod)
    aa -= combi
    """
    ans = 0
    #実際に移動する人数を固定
    #ではなく、0人の部屋を固定する
    for i in range(k+1):
        bow = n - i - 1
        child = fact[bow + i]
        mother = (mod_inv(fact[i], mod) * mod_inv(fact[bow], mod)) % mod
        combi = (fact[n] * mod_inv(fact[n - i],mod) * mod_inv(fact[i],mod)) % mod
        ans += (child * mother * combi) % mod
        ans %= mod
    print(ans % mod)

Submission status: Accepted

Solution code:
class Combination:
    '''MOD上の
    計算量：階乗・逆元テーブルの作成O(N)
    nCkを求める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 = [pow(self.fact[i], MOD - 2, MOD) for i in range(n + 1)]
        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[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 = list(map(int, input().split()))
MOD = 10 ** 9 + 7
comb = Combination(5 * 10 ** 5 + 10, MOD)

ans = 0

# 0の個数で場合分けする
for cnt_0 in range(0, min(n, k + 1)):
    ball = n
    box = n - cnt_0
    tmp = comb.combination(ball - 1, box - 1)
    tmp *= comb.combination(n, cnt_0)
    ans += tmp
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

def pow_mod(x,n):
  if n==0:
    return 1
  elif n==1:
    return x
  else:
    xn2=pow_mod(x,n//2)
    if n%2==0:
      return (xn2*xn2)%MOD
    else:
      return (xn2*xn2*x)%MOD

def fact_mod(a):
  if a<=1:
    return 1
  else:
    return a*fact_mod(a-1)%MOD
  
def perm_mod(n,a):
  if a==1:
    return n
  else:
    return (n*perm_mod(n-1,a-1))%MOD

def inv_mod(a):
  return pow_mod(a,MOD-2)%MOD
  
def comb_mod(na,fa):
  ainv=inv_mod(fa)
  return (na*ainv)%MOD
  
if k>=n-1:  
  #nHn=(2n-1)Cn
  perm=perm_mod(2*n-1,n)
  fact=fact_mod(n)
  comb=comb_mod(perm,fact)
  #print(perm,fact,comb)
  print(comb)
else:
  inv_table = [0]+[1]
  for i in range(2,k+1):
    inv_table+=[inv_table[MOD%i]*(MOD-int(MOD/i))%MOD]
  
  comb_sum=1
  fact=1
  comb1=1
  comb2=1
  for i in range(1,k+1):
    #comb1=comb1*(n-i+1)//i
    comb1=(comb1*(n-i+1)*inv_table[i])%MOD
    #comb2=comb2*(n-i)//i
    comb2=(comb2*(n-i)*inv_table[i])%MOD
    comb=(comb1*comb2)%MOD
    comb_sum+=comb
  
  print(comb_sum%MOD)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
class factorial:
  def __init__(self, n, p=10**9 + 7):
    self.__p  = p
    self.__fac  = [0] * (n+1)
    self.__inv  = [0] * (n+1)
    self.__finv = [0] * (n+1)

    self.__fac[0] = self.__fac[1] = 1
    self.__inv[1] = 1
    self.__finv[0] = self.__finv[1] = 1

    for i in range(2, n+1):
      self.__fac[i] = self.__fac[i-1] * i % p
      self.__inv[i] = p - self.__inv[p%i] * (p // i) % p
      self.__finv[i] = self.__finv[i-1] * self.__inv[i] % p
  
  def fact(self, n):
    return self.__fac[n]
  
  def perm(self, n, k):
    return self.__fac[n] * self.__finv[n-k] % self.__p
  
  def comb(self, n, k):
    return self.perm(n, k) * self.__finv[k] % self.__p

f = factorial(n)
p = 10**9 + 7
ans = 0
for i in range(min(k+1, n)):
  ans = (ans + f.comb(n, i) * f.comb(n-1, n-i-1)) % p
print(ans)

Submission status: Accepted

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def power_func(a,b,p):
  if b==0:
    return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return (d*d)%p
  else:
    return (a*power_func(a,b-1,p))%p
n,k=map(int,input().split())
mod=10**9+7
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
r=min(k,n)
for i in range(r+1):
  ans=(ans+cmb(n,i,mod)*cmb(n-1,i,mod))%mod
print(ans)

Submission status: Accepted

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

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

ans=0
if k>=n-1:
    ans=fac[n+n-1]*ifac[n]*ifac[n-1]%MOD
else:
    for i in range(k+1):
        if i>n: break
        tmp=fac[n]*ifac[n-i]*ifac[i]%MOD
        tmp=tmp*fac[i+n-i-1]*ifac[n-i-1]*ifac[i]%MOD
        ans=(ans+tmp)%MOD

print(ans)

Submission status: Accepted

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

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

N = 2 * 2 * 10 ** 5
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 )


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

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']
Yn=['Yes','No']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
#ts=time.time()
sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo


show_flg=False
show_flg=True

ans=0

n,k=LI()
cm=Comb(2*n+10)
if k>=n-1:
    ans=cm.comb(n+n-1,n)
else:
    for i in range(k+1):
        ans+=cm.comb(n,i)*cm.comb(n-1,i)
        ans%=mo
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
inpl = lambda: list(map(int,input().split()))
def inv_mod(a, p=10**9+7):
    p = abs(p)
    a %= p
    stack = []
    p0 = p
    while a > 1:
        d, a, p = p//a, p%a, a
        stack.append(d)
    x, y = 1, 0
    while stack:
        d = stack.pop()
        x, y = y-d*x, x
    return x % p0
n, k = inpl()
if k >= n:
    k = n-1
ans = 1
t = 1
for i in range(k):
    t *= (n-1-i)*(n-i)
    t %= MOD
    j = inv_mod(i+1)
    t *= j*j % MOD
    ans += t
    ans %= MOD
print(ans)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class ModTools:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        # 階乗テーブル
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        # 階乗の逆元テーブル
        inverse = [1] * MAX
        # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            # 最後から戻っていくこのループならMAX回powするより処理が速い
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """

        if n < r: return 0
        # 10C7 = 10C3
        r = min(r, n-r)
        # 分子の計算
        numerator = self.fact[n]
        # 分母の計算
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

    def nHr(self, n, r):
        """ 重複組み合わせ """

        # r個選ぶところにN-1個の仕切りを入れる
        return self.nCr(r+n-1, r)

N, K = MAP()

mt = ModTools(N*2, MOD)
ans = 0
for i in range(min(K+1, N)):
    ans += mt.nCr(N, i) * mt.nHr(N-i, i)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

M = Mod(10**9+7)


class Combination:
    def __init__(self, n, mod):

        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)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.MOD


@mt
def slv(N, K):
    C = Combination(N*2, 10**9+7)
    ans = 0
    for i in range(0, min(K+1, N)):
        r = N - i
        t = M.mul(C(N, i), C(r+i-1, i))
        ans = M.add(ans, t)

    return ans




def main():
    N, K = read_int_n()
    print(slv(N, K))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

def getComb(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

def getCombNs(n, invs, MOD):
    combNs = [1] * (n//2+1)
    for x in range(1, n//2+1):
        combNs[x] = (combNs[x-1] * (n-x+1) * invs[x]) % MOD
    return combNs + combNs[:(n+1)//2][::-1]

def getInvs(n, MOD):
    invs = [1] * (n+1)
    for x in range(2, n+1):
        invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
    return invs


ans = getComb(2*n-1, n, MOD)

if k < n-1:
    m = n-1-k
    invs = getInvs(n+3, MOD)
    combNs = getCombNs(n, invs, MOD)
    combN1s = getCombNs(n-1, invs, MOD)

    for i in range(m):
        ans -= combN1s[i] * combNs[i+1] % MOD
        ans %= MOD

print(ans)

Submission status: Accepted

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

mod = 10**9+7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル



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


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(n+1,k+1)):
    ans += cmb(n,i,mod)*cmb(n-1,i,mod)
    ans %= mod
print(ans)

Submission status: Accepted

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



mod = 10**9+7
 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,2*n+1):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
      
    return fact[n]*finv[r]*finv[n-r]%mod

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



ans = 0

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