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 mod_inverse(n, mod=10**9+7):
    return pow(n, mod-2, mod)


def combination(n, k, mod=10**9+7):
    numer = denom = 1
    for i in range(k):
        numer = (numer * (n-i)) % mod
        denom = (denom * (i+1)) % mod
    return (numer * mod_inverse(denom, mod)) % mod


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

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

ans = combination(2*n-1, n)
for i in range(k+1, n):
    ans -= (fact[n] * fact_inv[i] * fact_inv[n-i]) * (fact[n-1] * fact_inv[i] * fact_inv[n-1-i])
    # ans -= combination(n, i) * combination(n-1, i)
    ans %= mod
print(ans)

Submission status: Accepted

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

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

def comb(n, r, mod):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


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

Submission status: Accepted

Solution code:
mod = 1000000007


def frac_with_mod(a,m):
    outlist = [ 1 for i in range(a+1) ]
    for i in range(1,a+1):
        outlist[i] = (outlist[i-1] * i)% m
    return outlist

frac_list = frac_with_mod(4*10**5+10,10**9+7)

def comb_with_mod(a,b,c,m):
    return ( frac_list[a] * pow(frac_list[b],m-2,m) * pow(frac_list[c],m-2,m) ) % m

n, k = [ int(v) for v in input().split() ]


a = pow(frac_list[n - 1],mod-2,mod)

for i in range(2*n -1, n, -1):
    a *= i
    a %= mod

if (k >= n - 1):
    pass
else:
    for i in range(n-1, k,-1):
        j = n - i
        room = comb_with_mod(n, i, n - i, mod)
        person = comb_with_mod(n - 1, n - j, j - 1, mod)
        a -= ((room * person) % mod)
        a %= mod

print(a)

Submission status: Accepted

Solution code:
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

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

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
from collections import deque, Counter
from itertools import permutations, combinations
from heapq import heapify, heappop, heappush
from bisect import bisect, bisect_left

def comb(n, r, fact, revfact, mod):
    return (fact[n] * revfact[n - r] * revfact[r]) % mod

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    mod = 7 + 10 ** 9
    fact = [1] * (2 * N)
    revfact = [1] * (2 * N)
    for i in range(1, 2 * N): fact[i] = (fact[i - 1] * i) % mod
    revfact[2 * N - 1] = pow(fact[2 * N - 1], mod - 2, mod)
    for i in reversed(range(1, 2 * N - 1)): revfact[i] = ((i + 1) * revfact[i + 1]) % mod
    ans = 1
    if K < N:
        for i in range(1, min(K + 1, N + 1)): #i個zeroの部屋がある
            z = comb(N, i, fact, revfact, mod) #zeroにする箇所
            add = comb(N - 1, N - i - 1, fact, revfact, mod)
            ans += (z * add) % mod
    else:
        ans = comb(N + N - 1, N, fact, revfact, mod)

    print(ans % mod)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
#標準入力を高速に
import sys 
input = sys.stdin.readline

def factorial_mod(x, y, mod):
    factorial = 1
    for i in range(x,y+1):
        factorial *= i
        factorial %= mod
    return factorial

def n_C_k(n,k,mod):
    factorial_nk = factorial_mod(n-k+1, n, mod)
    factorial_k = factorial_mod(1,k,mod)
    conbi=factorial_nk*pow(factorial_k, mod-2, mod)
    return conbi%mod

#main関数(若干早くなる)
def main():
    n, k = map(int, input().split())
    mod = 10**9+7
    ans = 1+n*(n-1)

    a = n
    #a = n_C_k(n, 1, mod)
    #b = n_C_k(n-1, 1, mod)
    b = n-1

    for i in range(1, min(n, k)):
        temp1 = (n-i)*pow(i+1, mod-2, mod)%mod
        a *= temp1
        a %= mod
        temp2 = (n-1-i)*pow(i+1, mod-2, mod)%mod
        b *= temp2
        b %= mod
        temp3 = a*b%mod
        ans += temp3
        ans %= mod

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():

    n, k = map(int, input().split())
    mod = pow(10, 9) + 7

    g1 = [1, 1]
    g2 = [1, 1]
    inv = [0, 1]

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

    def combi(n, r):
        r = min(r, n-r)
        return g1[n]*g2[r]*g2[n-r]%mod

    if k >= n-1:
        k = n-1
    ans = 1
    for i in range(1, k+1):
        ans += (combi(n, i) * combi(n-1, n-i-1)) % mod
    return ans % mod


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
MAX_NUM = 4*10**5
pr = 10**9+7
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
a=c(2*n-1,n)
if k>=n-1:
    print(a)
else:
    for i in range(k+1,n):
        a=(a-c(n,i)*c(n-1,n-i-1))%pr
    print(a)

Submission status: Accepted

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

class BiCoeff(object):
    def __init__(self, MAX, m):
        super(BiCoeff, self).__init__()
        fac = [0]*MAX
        finv = [0]*MAX
        inv = [0]*MAX

        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2,MAX):
            fac[i] = (fac[i-1]*i)%m
            inv[i] = m - (inv[m%i] * (m//i))%m
            finv[i] = (finv[i-1] * inv[i])%m

        self.MAX = MAX
        self.m = m
        self.fac = fac
        self.finv = finv
        self.inv = inv

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


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

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

res = 0
for i in range(1,n+1):
    if n-i<=k:
        res += bicoeff.calc(n-1,i-1)*bicoeff.calc(n,i)
        res %= MOD
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
fact = [i for i in range(4 * 10 ** 5 + 1)]
fact[0] = 1
for i in range(4 * 10 ** 5):
    fact[i + 1] *= fact[i]
    fact[i + 1] %= mod

def combination_mod(n, k, mod):
    """ power_funcを用いて(nCk) mod p を求める """
    """ nCk = n!/((n-k)!k!)を使用 """
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = fact[n] % mod
    b = fact[k] % mod
    c = fact[n - k] % mod
    return (a * pow(b, mod - 2, mod) * pow(c, mod - 2, mod)) % mod

#solve
def solve():
    n, k = LI()

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

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

ans = 0
for i in range(0, k+1):
    if i == 0:
        zero_pt = 1
    else:
        zero_pt = comb(n, i)
    rest = i
    sikiri = n - i - 1
    if sikiri == 0:
        plus_pt = 1
    else:
        plus_pt = comb(rest + sikiri, sikiri)
    ans += zero_pt * plus_pt
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
INF=10**9+7
p=[0]*n
p[0]=1
def modinv(a,m):
    b=m
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while not b==0:
        q=a//b
        (a,b)=(b,a%b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx%m
x=n-1
y=n
for i in range(1,n):
    p[i]=(x*y)%INF
    a=n-1-i
    b=modinv(i+1,INF)
    x=(x*a*b)%INF
    a = n - i
    b = modinv(i+1, INF)
    y = (y * a * b) % INF
ans=0
if k>=n:
    for i in range(n):
        ans=(ans+p[i])%INF
else:
    for i in range(k+1):
        ans=(ans+p[i])%INF
print(ans)

Submission status: Accepted

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

comb0 = [1] * (n)

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

comb1 = [1] * (n)

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

ans = 0

for i in range(min(n - 1, k) + 1):
    ans += comb0[i] * comb1[i]
    ans %= mod

print(ans)

Submission status: Accepted

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

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

mod=10**9 + 7
fact=[1,1]
factinv=[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 // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)
    
ans=0

if k>=(n-1):
    ans=cmb(2*n-1,n,mod)
else:
    for i in range(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

def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
    x,y = w[0],w[1]    # a*x+y*mod = 1
    return (mod+x%mod)%mod

max_num = 2*10**5+1
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

for i in range(2,max_num):
    fact[i] = fact[i-1] * i % mod
    ifact[i] = ifact[i-1] * inv(i,mod) % mod

def comb(x,y):
    return fact[x] * ifact[y] * ifact[x-y] % mod

ans = 1

ff = min(k+1,n)

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

print(ans)

Submission status: Accepted

Solution code:
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
    
n,k = map(int,input().split())
A = [1 for _ in range(n+1)]
for i in range(2,n+1):
    A[i] = (i*A[i-1])%p
B = [1 for _ in range(n+1)]
B[n] = pow(A[n],p-2)
for i in range(n-1,1,-1):
    B[i] = (B[i+1]*(i+1))%p

cnt = 0
for i in range(min(k,n-1)+1):
    a = (A[n]*B[n-i]*B[i])%p
    b = (A[n-1]*B[n-1-i]*B[i])%p
    cnt = (cnt+a*b)%p
print(cnt)

Submission status: Accepted

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

def mod_inverse(a, p):
    mod = 1
    p_bin = bin(p-2)
    for i in range(len(p_bin) - 1, 1, -1):
        if i == len(p_bin) - 1:
            mul = a
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
        else:
            mul = mul ** 2
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
    return mod

b = []
for i in range(a):
    b.append(mod_inverse(i + 1, p))
b1 = [1]
b2 = [1]
for i in range(a):
    temp = b1[-1] * (n - i)
    temp *= b[i]
    temp %= p
    b1.append(temp)
    temp2 = b2[-1] * (n - 1 - i)
    temp2 *= b[i]
    temp2 %= p
    b2.append(temp2)
ans = 0
for i in range(a + 1):
    ans += b1[i] * b2[i]
    ans %= p
print(ans)

Submission status: Accepted

Solution code:
MAX_NUM = 2 * (10**5)+ 10
MOD = 10**9+7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

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

for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

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

sum = 1
t = 1
for i in range(min(n, k)):
  t = ((t * (n-i)) % MOD * (n-i-1)) % MOD
  t = ((t * inv[i+1]) % MOD * inv[i+1]) % MOD
  sum = (sum + t) % MOD

print(sum)

Submission status: Accepted

Solution code:
import sys

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)



#modのn!と、n!の逆元を格納したリストを返す(拾いもの)
#factorialsには[1, 1!%mod , 2!%mod , 6!%mod… , n!%mod] が入っている
#invsには↑の逆元が入っている

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    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 modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod


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

fac,inv = modfac(2*n,mod)
"""
nm1lis = [1]
for i in range(n):
    nm1lis.append(nm1lis[-1] * (n-1) % mod)

print (nm1lis)
"""

if k >= n:
    print (modnCr(2*n-1,n,mod,fac,inv))
    sys.exit()

"""
求めるのは人数の組み合わせ
どうする？
不可能なものの数を数えて引くか？
k+2以上の人数の部屋があったら不可能
k+2人以上が1つあるときの組み合わせ- (2つあるときの組み合わせ) + …

でいけそうかな？
それ以外は可能なのか？

0の数がk恋かの組み合わせ
0の数がk個より大きいなら不可能

0がk+1個…Nこ
"""

ans = modnCr(2*n-1,n,mod,fac,inv)
loop = 1

for i in range(k+1,n):

    bn = n - i - 1
    now = modnCr(n,i,mod,fac,inv) * modnCr(i+bn,bn,mod,fac,inv)

    ans -= now
    
    ans %= mod

    loop += 1

print (ans)

"""

while (k+2)*loop <= n:

    now = modnCr(n,loop,mod,fac,inv) * modnCr(n-1 + (n-(k+2)*loop),n-1,mod,fac,inv)
    if loop % 2 == 1:
        ans -= now
    else:
        ans += now

    ans %= mod

    loop += 1

"""

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

    mi = min(k, n - 1)

    cl = Calc(max_value=n * 2 - 1, mod=mod)

    ret = 0
    for r in range(mi + 1):
        ret += cl.combination(n - 1, n - r - 1) * cl.combination(n, r)
        ret %= mod

    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

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 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


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

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

def make_table(size=10**6, p=MOD):
    fac = [None] * (size + 1)
    fac[0] = 1
    for i in range(size):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (size + 1)
    ifac[size] = pow(fac[size], p-2, p)
    for i in range(size, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    return fac, ifac

fac, ifac = make_table(5*10**5)

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

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

n, k = map(int, sys.stdin.readline().split())

def main():
    if k >= n - 1:
        return nHr(n, n)
    else:
        res = nHr(n, n)
        for i in range(k+1, n+1):
            res -= comb(n, i) * nHr(n-i, i) % MOD
            res %=MOD

        return res % MOD
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
p = 10 ** 9 + 7
N = (10 ** 5)*2 +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 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


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

ans = [1]

# i人が動いた
# iのときi-1を再現可能
# iを考えるときi部屋は空になる
# 残りのn-i部屋から選ぶ
# 1,6,3

for  i in range(1,N+1):
    mm1 = cmb(N,i,p)
    # mm2 = (cmb(N-i,1,p)*ans[i-1])%p
    # nHr n:n-i, r:i
    mm2 = cmb(N-i+i-1,i,p)

    ans.append((mm1*mm2)%p)

mm = 0
for i in range(min(N+1,K+1)):
    mm += ans[i]
    mm %= p
print(mm)

# print(15*14)
# print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
INF = 10 ** 20
MOD = 10**9 + 7
def combmod(n, k, mod=MOD):
    if k == 0:
        return 1
    if k == 1:
        return n
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

def main():
    n, k = getList()
    if k >= n-1:
        ans = combmod(n+n-1, n)
    else:
        # ans = 0
        ans = 1
        tmp = 1
        for i in range(1, k+1):
            tmp *= n-i
            tmp *= n + 1 - i
            tmp *= pow(i, MOD-2, MOD)
            tmp *= pow(i, MOD - 2, MOD)
            ans += tmp
            tmp %= MOD
            # tmp = combmod(n-1, i)
            # tmp *= combmod(n, i)
            # tmp %= MOD
            # ans += tmp
            ans %= MOD
        # ans = combmod(n, k+1)
        # print(ans)
        # ans *= combmod(k+k+1, k+1)
        # # ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

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

    return modFacts, invs


N, K = map(int, input().split())
modFacts, invs = prepare(N)

ans = 0
for k in range(min(K + 1, N)):
    num = (modFacts[N - 1] * invs[N - k - 1] * invs[k]) % MOD
    zero = (modFacts[N] * invs[k] * invs[N - k]) % MOD
    ans += (num * zero) % MOD
    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 = 4*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 )

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

else:
    print(cmb(2*n-1,n,mod))

Submission status: Accepted

Solution code:
MOD=10**9+7
n,k=map(int,input().split())
def modpow(a, p, mod=MOD):
    # return a**p (mod MOD) O(log p)
    if p==0: return 1
    if p%2==0:
        half = modpow(a, p//2, mod)
        return half*half % mod
    else:
        return a * modpow(a, p-1, mod) % mod

ret=modpow(2,n)
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
def comb(x,n):
    divd=1
    for i in range(n):
        divd*=ModInt(x-i)
    for i in range(n):
        divd/=ModInt(i+1)
    return divd
if k<n-1:
    combl_1=[1]*n
    combl_2=[1]*(n+1)
    combl_1[1]=n-1
    combl_2[1]=n
    for i in range(2,n):
        combl_1[i]=ModInt(n-i)*combl_1[i-1]/ModInt(i)
        combl_2[i]=ModInt(n-i+1)*combl_2[i-1]/ModInt(i)
    ans=0
    for i in range(k+1):
        ans+=combl_1[i]*combl_2[i]
    print(ans)
if k>=n-1:
    print(comb(2*n-1,n-1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# %%
import numpy as np
# %%
stdin = open(0)

# %%
N, K = map(int, stdin.read().split())

# %%
MOD = 10 ** 9 + 7

# %%


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


def make_fact(U, MOD=MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD - 2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    fact.flags.writeable = False
    fact_inv.flags.writeable = False
    return fact, fact_inv


# %%
fact, fact_inv = make_fact(N + 10)

# %%
if K >= N:
    K = N - 1
x = fact[N] * fact_inv[0:K + 1] % MOD * fact_inv[N - K:N + 1][::-1] % MOD
y = fact[N - 1] * fact_inv[0:K + 1] % MOD * fact_inv[N - K - 1:N][::-1] % MOD
answer = np.sum(x * y % MOD) % MOD

# %%
print(answer)

# %%

Submission status: Accepted

Solution code:
MOD = 10**9+7
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

class comb():
    # class <mint> should be imported
    def __init__(self, n):
        self.n = n
        fact = [0]*(n+1) # 1-indexed
        ifact = [0]*(n+1) # 逆元
        fact[0] = mint(1)
        for i in range(1, n+1):
            fact[i] = fact[i-1]*i
        ifact[-1] = pow(fact[-1], MOD-2)
        for i in range(n, 0, -1):
            ifact[i-1] = ifact[i]*i
        self.fact = fact
        self.ifact = ifact
    def calc(self, n, k):
        if k<0 or k>n:
            return 0
        return self.fact[n]*self.ifact[k]*self.ifact[n-k]

n,k = map(int, input().split())
cb=comb(200005)

ans=mint(0)

for i in range(min(n,k+1)):
    ans+=cb.calc(n,i)*cb.calc(n-1, i)



print(ans)