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: Wrong Answer

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

ans = 0
for k in range(max(1, N - K), N + 1):
    ans += fac[N - 1 + k - 1] * finv[k - 1] * finv[N - 1]
    ans %= MOD
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
MOD=10**9+7
ans=1
#Combination 1 O()
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 = MOD #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

if n-1<=k:
    print(cmb(2*n-1,n,MOD)%MOD)

else:
    for i in range(1,k+1):
        ans+=(cmb(n,i,MOD)*cmb(n-1,i,MOD))
        ans%=MOD
    print(ans&MOD)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
MOD=10**9+7
ans=1
#Combination 1 O()
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 = MOD #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

if n-1<=k:
    print(cmb(2*n-1,n,MOD)%MOD)

else:
    for i in range(1,k+1):
        ans+=(cmb(n,i,MOD)*cmb(n-1,i,MOD))
    print(ans&MOD)

Submission status: Wrong Answer

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

#Combination 1 O()
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 = MOD #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

if k>=n:
    k=n-1

for i in range(1,k+1):
    ans+=(cmb(n,i,MOD)*cmb(n-1,i,MOD))%MOD

print(ans&MOD)

Submission status: Wrong Answer

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

# Function of Combination mod M
# set n >= max p expected
M = 10**9+7


if k >= n-1:
    fac = [1]+[0]*(2*n-1)
    for i in range(1,2*n):
        fac[i] = fac[i-1]*i %M
        comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = comb(2*n-1,n-1)
    
else:
    fac = [1]+[0]*n
    for i in range(1,n+1):
        fac[i] = fac[i-1]*i %M
        comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = 1
    for i in range(1,k+1):
        y += (comb(n,i)*comb(n-1,n-1-i))%M
print(y)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
m = 1000000007

def comb(n, r, m):
  X, Y = 1, 1
  for i in range(r):
    X *= n-i
    Y *= i+1
    X %= m
    Y %= m
  return int(X * pow(Y, m-2, m))

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

n0 = 1
n1 = (n*(n-1))%m
n2 = 0
for i in range(2, n):
  n2 += comb(n, i, m) * comb(n-1, n-m-1, m)
  n2 %= m
print((n0 + n1 + n2)%m)

Submission status: Wrong Answer

Solution code:
mod=10**9+7
comb1=1
comb2=1
N,K=map(int,input().split())
k=min(K,N-1)
x=0
for i in range(k):
 comb1=(comb1*(N-i)*pow(i+1,mod-2,mod))%(mod)
 comb2=(comb2*(N-1-i)*pow(i+1,mod-2,mod))%(mod)
 x+=(comb1*comb2)%(mod)
print(x%(mod))

Submission status: Wrong Answer

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

N,k=map(int,input().split())
x=0
for i in range(k+1):
 x+=((cmb(N,i)%(10**9+7))*(cmb(N-1,i)%(10**9+7)))%(10**9+7)
if k==1:
 x-=1
print(x%(10**9+7))

Submission status: Wrong Answer

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

comn = [1]
for i in range(n):
    z = comn[i] * (n-i) // (i+1)
    comn.append(z)
comm = [1]
for j in range(n-1):
    q = comm[j] * (n-1-j) // (j+1)
    comm.append(q)

if k >= n:
    ans = (2 ** (n-1)) % (10 ** 9 + 7)
else:
    ans = 0

    for i in range(k+1):
        y = (comn[i] * comm[i]) % (10 ** 9 + 7)
        ans += y

    ans % (10 ** 9 + 7)

print(ans)

Submission status: Wrong Answer

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


def c(n,k):
    return (math.factorial(n) * pow(math.factorial(k), mod-2, mod) * pow(math.factorial(n-k), mod-2, mod)) % mod


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

if k % 2 != 0:
    print(ans % mod)

else:
    print((ans+1) % mod)

Submission status: Wrong Answer

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


def comb_fermat(n: int, r: int) -> int:
    if r > n:
        return 0
    if r > n-r:
        return comb_fermat(n, n-r)
    mul, div = 1, 1
    for i in range(r):
        mul *= n-i
        mul %= MOD
        div *= i+1
        div %= MOD

    ret = mul * pow(div, MOD-2, MOD) % MOD
    return ret


print(comb_fermat(2*n - 1, n))

Submission status: Wrong Answer

Solution code:
n,a=map(int,input().split())
p=1000000007
def prmd(n,i):#nPiをpで割ったときの余り．
    P=1
    for j in range(i):
        P=(P*(n-j))%p
    return (P)
def bin(N):#Nの２進数を表したときの桁数．
    t=0
    while N>0:
        N=N//2
        t=t+1
    return (t)
def blis(m):#Nの２進数を表す．
    lists=[]
    for i in range(bin(m)):
        lists.append(m%2)
        m=m//2
        if m==0:
            break
    return (lists)
def modu(a,m,q):#a**mを素数qで割ったときの余り．素数と書いたのはフェルマーの小定理を考慮している．
    t=a%q
    lista=[]
    for i in range(bin(m)):
        lista.append(t)
        t=(t**2)%q
    listb=[]
    for j in range(bin(m)):
        listb.append(lista[j]*blis(m)[j])
    s=1
    for k in range(bin(m)):
        if listb[k]>0:
            s=(s*listb[k])%q
    return (s)
X=prmd(2*n-1,n-1)
Y=modu(prmd(n-1,n-1),p-2,p)#(X*Y)%pは2n-1Cn-1をpで割った余を表す．
if n-1<a:
    print ((X*Y)%p)
else:
    u=0
    for i in range(a+1):
        u=u+prmd(n,i)*prmd(n-1,n-1-i)*modu(prmd(i,i),p-2,p)*modu(prmd(n-1-i,n-1-i),p-2,p)
        u=u%p
    print (u,u)

Submission status: Wrong Answer

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

k=min(k,n-1)
c=[1]+[0]*k
h=[1]+[0]*k

for i in range(1,k+1):
  c[i]=(c[i-1]*(n-i+1)//i)%m
  h[i]=(h[i-1]*(n-i)//i)%m

t=0
for i in range(k+1):
  t+=(c[i]*h[i])%m

print(t%m)

Submission status: Wrong Answer

Solution code:
n,a=map(int,input().split())
p=1000000007
def prmd(n,i):#nPiをpで割ったときの余り．
    P=1
    for j in range(i):
        P=(P*(n-j))%p
    return (P)
def bin(N):
    t=0
    while N>0:
        N=N//2
        t=t+1
    return (t)
def blis(m):
    lists=[]
    for i in range(bin(m)):
        lists.append(m%2)
        m=m//2
        if m==0:
            break
    return (lists)
def modu(a,m,q):
    t=a%q
    lista=[]
    for i in range(bin(m)):
        lista.append(t)
        t=(t**2)%q
    listb=[]
    for j in range(bin(m)):
        listb.append(lista[j]*blis(m)[j])
    s=1
    for k in range(bin(m)):
        if listb[k]>0:
            s=(s*listb[k])%p   
    return (s)
X=prmd(2*n-1,n-1)
Y=modu(prmd(n-1,n-1),p
       -2,p)
print ((X*Y)%p)

Submission status: Wrong Answer

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

fact = [1]*(U+1)
fact_inv = [1]*(U+1)

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

for i in range(U,0,-1):
	fact_inv[i-1] = (fact_inv[i]*i)%MOD

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

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

Submission status: Wrong Answer

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

def mfactorial(n, mod):
    if n >= mod:
        return 0
    result = 1
    for i in range(1, n+1):
        result *= i
        result %= mod
    return result

def mbinomial(n, k, primemod):
    child = mfactorial(n, primemod) % primemod
    mother = mfactorial(n-k, primemod) * mfactorial(k, primemod) % primemod
    return child * pow(mother, primemod - 2, primemod) % primemod

if k >= n:
    print(mbinomial(2 * n - 1, n, MOD))
else:
    answer = 0
    for i in range(k+1):
        answer += mbinomial(n, i, MOD) * mbinomial(n-1, i, MOD) % MOD
    print(answer)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
mod = 10 ** 9 + 7
def cb(n, k):
    global mod
    ret = a = b = 1
    for i in range(k):
        a *= n-i
        a %= mod
        b *= i + 1
        b %= mod
    m = mod-2
    while m > 0:
        if m % 2 != 0:
            ret *= b
            ret %= mod
        b *= b
        b %= mod
        m //= 2
    ret *= a
    ret %= mod
    return ret

k = min(k, n - 1)
dp1 = [1] # nCi의 값을 저장
dp2 = [1] # n-1Ci의 값을 저장
ans = 1
for r in range(1, k + 1):
    tmp = dp1[-1] * (n - r + 1) // r
    tmp %= mod
    dp1.append(tmp)

    tmp2 = dp2[-1] * (n - r) // r
    tmp2 %= mod
    dp2.append(tmp2)

    ans += tmp * tmp2
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin



def prepare(n, p):
    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)
    return fact, factinv


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


def get_result(data):
    n, k = data
    mod = 10**9+7
    fact, factinv = prepare(n, mod)
    ans = 0
    for m in range(n):
        # xHy = x+y−1Cx−1
        ans += (cmb(n, m, mod, fact, factinv) * cmb(n-1, n-m-1, mod, fact, factinv)) % mod
    ans %= mod
    return ans

if __name__ == '__main__':
    data = list(map(int, stdin.readline().split(' ')))
    result = get_result(data)
    print(result)

Submission status: Wrong Answer

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

k = min([k, n-1])


ans = 0
key = 1

for i in range(k):
    ans += key
    ans %= mod
    key = (((key*(n-i)%mod)*(n-i-1)%mod)*pow(pow(i+1, mod-2, mod), 2, mod))%mod
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

mod7 = 10 ** 9 + 7


def power(a, b, mod):
    p = 1
    q = a
    while b != 0:
        if b % 2 == 1:
            p = (p * q) % mod
        q = (q * q) % mod
        b = b // 2
    return p


def fact(n, mod):
    p = 1
    for i in range(1, n + 1):
        p = (p * i) % mod
    return p


def combi(n, a, mod):
    if a == 0:
        return 1
    else:
        inv_af = power(fact(a, mod), mod - 2, mod)
        p = 1
        for i in range(a):
            p = (p * (n - i)) % mod
        return inv_af * p % mod


def blank(n, b, mod):
    Ans = combi(n, b, mod) * combi(n - 1, b, mod) % mod
    return Ans


def solve(n, k):
    global mod7
    Answer = 0
    if k < n - 1:
        for i in range(k + 1):
            Answer = Answer + blank(n, i, mod7) % mod7

    else:
        Answer = combi(2 * n - 1, n - 1, mod7)
    return Answer


print(solve(n, k))

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7

var_n,var_k = map(int,input().split())
all_list = []

first_inner_list = []
for i in range(var_n):
    first_inner_list.append(1)
all_list.append(first_inner_list)
#print(all_list)

for h in range(var_k):
    print(h)
    before_len = len(all_list)

    for i in range(before_len):
        before_ope = all_list.pop(0)
        for j in range(var_n):
            if before_ope[j] > 0:
                ope1 = before_ope.copy()
                ope1[j] = before_ope[j] - 1
                for k in range(var_n):
                    if j == k:
                        continue
                    else:
                        ope2 = ope1.copy()
                        ope2[k] = ope1[k] + 1
                        all_list.append(ope2)
    
    all_list = list(set(list(map(tuple, all_list))))
    
    for i in range(len(all_list)):
        element = list(all_list.pop(i))
        all_list.insert(i, element)

print(len(all_list) % mod)

Submission status: Wrong Answer

Solution code:
m = 10 ** 9 + 7 

def comb(n, r, mod):
    p, q = 1, 1
    for i in range(r):
        p = p * (n - i) % mod
        q = q * (i + 1) % mod
    return p * pow(q, mod - 2, mod) % mod

def main():
    n, k = map(int,input().split())
    ans = 0
    if k >= (n-1):
        ans = comb(2*n-1,n-1,m)
    else:
        ans = comb(n-1+k,k,m) + comb(n-k,k,m)
        ans = ans % m
    print(ans)
      

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import numpy as np

MOD=1000000007

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

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

ret = 1
for i in range(1,k+1):
    ret = (ret + nCr(n,i)*nHr(i,n-i))%MOD

print(ret)

Submission status: Wrong Answer

Solution code:
class Mint:
    
    MOD = 10**9+7
    
    def __init__(self, x=0):
        self.x = (x%self.MOD + self.MOD) % self.MOD
    
    def __iadd__(self, other):
        self.x += other.x
        if self.x >= self.MOD:
            self.x -= self.MOD
        return self
    
    def __isub__(self, other):
        self.x += self.MOD - other.x
        if (self.x >= self.MOD):
            self.x -= self.MOD
        return self
    
    def __imul__(self, other):
        self.x *= other.x
        self.x %= self.MOD;
        return self;
    
    def __add__(self, other):
        ans = Mint(self.x)
        ans += other
        return ans
        
    def __sub__(self, other):
        ans = Mint(self.x)
        ans -= other
        return ans
    
    def __mul__(self, other):
        ans = Mint(self.x)
        ans *= other
        return ans
    
    def __pow__(self, n):
        if n == 0:
            return Mint(1)
        a = self.__pow__(n >> 1)
        a *= a
        if n&1:
            a *= self
        return a
    
    def inv(self):
        return self**(self.MOD-2)
    
    def __ifloordiv__(self, other):
        self *= other.inv()
        return self
    
    def __floordiv__(self, other):
        ans = Mint(self.x)
        ans //= other
        return ans
        
class Comb2:
    
    def __init__(self, n):
        self.n = n
        self.fact = [Mint(1)]*(n+1)
        self.ifact = [Mint(1)]*(n+1)
        for i in range(1, n+1):
            self.fact[i] = self.fact[i-1]*Mint(i)
        self.ifact[n] = self.fact[n].inv()
        for i in range(n, 0, -1):
            self.ifact[i-1] = self.ifact[i]*Mint(i)
    
    def comb(self, k):
        assert self.n < Mint.MOD
        if k < 0 or k > self.n:
            return Mint(0)
        if k == 0 or k == self.n:
            return Mint(1)
        return self.fact[self.n]*self.ifact[k]*self.ifact[self.n-k]
        

def Main(N, K):
    ans = Mint(0)
    A = Comb2(N)
    for i in range(N):
        a = A.comb(i)**2
        b = Mint(N-i+1)//Mint(N)
        ans += a*b
        if i == K:
            return ans.x
    return ans.x

def main():
    N, K = list(map(int, input().split()))
    print(Main(N, K))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

def cmb(n, r):
    res = 1
    fac = 1
    for i in range(r):
        res *= (n-i)
        res %= mod
        fac *= (i+1)
        fac %= mod
    return res*pow(fac, mod-2, mod) % mod

answer = 0

for m in range(k+1):
    answer += cmb(n, m)*cmb(n-1, n-m-1) % mod

print(answer % mod)

Submission status: Wrong Answer

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

MOD = 1000000007  # type: int

from functools import lru_cache

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

    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

    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) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)


    ans = 0
    for i in range(k+1):
        ans += cmb(n, i, MOD) * cmb((n-i-1)+i, i, MOD)

    print(ans)


    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    k = int(next(tokens))  # type: int
    solve(n, k)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

MOD = 1000000007  # type: int

from functools import lru_cache

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

    def combination_with_mod(n, r, mod=10**9+7):
        n1, r = n+1, min(r, n-r)
        numer = denom = 1
        for i in range(1, r+1):
            numer = numer * (n1-i) % mod
            denom = denom * i % mod
        return numer * pow(denom, mod-2, mod) % mod
        # return kai[n] // (kai[n-r] * kai[r]) % MOD

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

    print(ans)


    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    k = int(next(tokens))  # type: int
    solve(n, k)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from functools import reduce
mod=10**9+7

def f(A,B):
 if B==0:
  den=1
  num=1
 else:
  den=reduce(lambda x,y:x*y%mod,range(A,A-B,-1))
  num=reduce(lambda x,y:x*y%mod,range(1,B+1))
 return den*pow(num,mod-2,mod)%mod

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

Submission status: Wrong Answer

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

def modcomb(n,a,mod):
    cnt = 1
    for i in range(a):
        cnt *= (n-i)
        cnt *= pow(i+1,mod-2,mod)
        cnt %= mod
    # print(cnt)
    return cnt

cnt1 = modcomb(2*(n-1),n-1,MOD)
cnt2 = modcomb(2*(n-1),n,MOD)
# cnt1 = modcomb(2*(n-1),n-1,MOD)
# cnt2 = modcomb(2*(n-1),n,MOD)
ans = (cnt1+cnt2)%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce
mod=10**9+7

def f(n,k):
 dem=reduce(lambda x,y:x*y%mod,range(n+k,n-1,-1))
 num=reduce(lambda x,y:x*y%mod,range(1,k+2))
 return dem*pow(num,mod-2,mod)%mod

# stdin=open(0)
n,k=map(int,input().split())

ans=f(n,k)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

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

inv_list = [1]  # 0で割るというのは定義されないので無視。
for i in range(n):
    inv_list.append(int(MOD - inv_list[(MOD % (i + 2)) - 1] * (MOD // (i + 2)) % MOD))
if k >= 10 ** 5 - 1:
    ans = 1
    for i in range(2 * n - 1):
        ans *= (i + 1)
        ans %= MOD
    for i in range(n):
        ans *= inv_list[i]
        ans *= inv_list[i]
        ans %= MOD
    ans *= n
    ans %= MOD
    print(ans)
else:
    ans = 1
    nCm = 1
    nmHm = 1
    for i in range(k):
        nCm *= n - i
        nCm *= inv_list[i]
        nCm %= MOD
        nmHm *= (n - 1) - i
        nmHm *= inv_list[i]
        nmHm %= MOD
        ans += nCm * nmHm
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
mod=10**9+7
n_max=4*(10**5+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
FI[n_max-1]=pow(F[n_max-1],mod-2,mod)
for i in reversed(range(n_max-1)):
  FI[i]=(FI[i+1]*(i+1))%mod
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

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

  print(ans)

Submission status: Wrong Answer

Solution code:
def nCrMOD(a,b,m):
    c = 1
    for i in range(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

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

ans_m =[ nCrMOD(n,m,mod) * nCrMOD(n-1,n-m-1,mod)%mod for m in range(n+1)]
if k >=n-1:
    print(sum(ans_m)%mod)
else:
    print(sum(ans_m[:k+1])%mod)

Submission status: Wrong Answer

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

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

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

N, K = map(int, input().split())
MOD = 10**9+7
n = max(N,K)
ans = 0
for i in range(max(1,N-n),N+1):
  m = cmb(N,i,MOD)
  m *= cmb(N-1,i-1, MOD)
  ans += m
  ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
[n,k] = [int(s) for s in sys.stdin.read().split()] #リスト作成

mod = 10**9+7
def comb(p,q,A): #pCq modA
  X = 1
  Y = 1
  for i in range(1, q+1):
    X = (X*(p-i+1))%A
    Y = (Y*i)%A
  return (X*pow(Y, A-2, A))%A #X*Y^(-1) modA
ans = 0
for i in range(min(n,k)+1): #i:空の部屋の数
  ans += (comb(n,i,mod)*comb(n-1,n-i-1,mod))%mod
print(ans % mod)

Submission status: Wrong Answer

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

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

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

N, K = map(int, input().split())
MOD = 10**9+7
n = K%N if K%N!=0 else N
ans = 0
for i in range(max(1,N-n),N+1):
  m = cmb(N,i,MOD)
  m *= cmb(N-1,i-1, MOD)
  ans += m
  ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
mod=10**9+7
k=min(k,n)
ans=1
g=1
h=1
for i in range(k):
    g*=(n-i)*pow(k+i,mod-2,mod)
    g%=mod
    h*=(n-1-i)*pow(k+i,mod-2,mod)
    h%=mod
    ans+=g*h%mod
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 8)

# Wrong Answer
# WA


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

# 階乗、Combinationコンビネーション(numpyを使う)


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


def make_fact(U, 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]
    return fact, fact_inv


U = 10**6
fact, fact_inv = make_fact(U, MOD)


def mod_comb_k(n, k, mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n - k] % mod


ans = 0
for i in range(N):
    if K < i:
        continue

    if i == 0:
        ans += 1
        continue

    '''
    a = mod_comb_k(N - 1, i, MOD)
    b = mod_comb_k(N, i, MOD)
    c = a * b
    c %= MOD
    '''
    ans += mod_comb_k(N-1, i, MOD) * mod_comb_k(N, i, MOD)

print(ans)

Submission status: Wrong Answer

Solution code:
m=10**9+7;f=[1];n,k=map(int,input().split())
for i in range(10**6):f+=[f[i]*(i+1)%m]
def c(a,b):return f[a]*pow(f[b],m-2,m)*pow(f[a-b],m-2,m)%m
s=c(n*2-1,n-1)
if k>n-2:print(s)
else:print(s+(m-sum(c(n-1,i)*c(n,n-i)for i in range(n-1,k,-1))%m)%m)