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:
def mod_inv(a, p):
    return pow(a, p-2, p)

def mod_binominal(n, r, p):
    if n < r:
        return 1
    numerator = 1
    for i in range(r):
        numerator = (numerator * (n-i)) % p
    
    denominator = 1
    for i in range(1, r+1):
        denominator = (denominator * i) % p

    return numerator * mod_inv(denominator, p) % p


def resolve():
    n, k = map(int, input().split())
    p = 10**9+7
    
    K = min(n, k)
    sum = 0
    for i in range(1, K+1):
        sum += ((mod_binominal(n, i, p) + p) % p) * ((mod_binominal(n - 1, i, p) + p) % p)

    print(sum + 1)



if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *
from bisect import *
import copy

n,k=map(int,input().split())
mod=10**9+7
fac=[0,1]
for i in range(2,2*n+1):
    fac.append(fac[i-1]*i%mod)
ifac=[pow(i,mod-2,mod) for i in fac]

def comb(a,b):
    if a==0 and b==0:return(1)
    if a<b or a<0:return(0)

    return((fac[a]*ifac[a-b]*ifac[b])%mod)

count=1
for m in range(0,min(k+1,n)):

    count=(count+comb(n,m)*comb((n-m)+m-1,n-m-1))%mod
print(count)

Submission status: Wrong Answer

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

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def comb(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

ans=0
for i in range(k+1):
    zs=i
    os=n-i
    sm=comb(n,zs) * comb(n-1,i)
    sm %= (10**9+7)
    ans+=sm

print(ans%(10**9+7))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
print(k)
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: Wrong Answer

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:
  comb_sum=1
  fact=1
  comb1=1
  comb2=1
  for i in range(1,k+1):
    comb1*=(n-i+1)//i
    comb2*=(n-i)//i
    comb=(comb1*comb2)%MOD
    comb_sum+=comb
  
  print(comb_sum%MOD)

Submission status: Wrong Answer

Solution code:
mod=10**9+7
n,k=map(int,input().split())
ans=0
coef1=n
coef2=n-1
for i in range(1,min(k+1,n)):
  tmp=1
  tmp*=coef1
  tmp%=mod
  tmp*=coef2
  tmp%=mod
  ans+=tmp
  ans%=mod  
  coef1*=n-i
  coef1%=mod
  coef1*=pow(i+1,mod-2,mod)
  coef1%=mod
  coef2*=n-1-i
  coef2%=mod
  coef2*=pow(i+1,mod-2,mod)
  coef2%=mod
if k%2==0 or k>=n:
  ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
M = 10 ** 9 + 7

def inv(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return x0

def comb(n, k):
    r1 = 1
    for i in range(k):
        r1 = r1 * (n - i) % M
    r2 = 1
    for i in range(k):
        r2 = r2 * (i + 1) % M
    return r1 * inv(r2, M) % M

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

def solve(n, k):
    if k >= n:
        return h(n, n)
    r = 0
    for i in range(k + 1):
        r += comb(n, i) * h(n - i, i) % M
        # print('i=', i, 'r=', r)
        # print('h(n, i)=', h(n, i), 'h(n - i, i)=', h(n - i, i))
    return r

n, k = [int(x) for x in input().split()]
print(solve(n, k))

Submission status: Wrong Answer

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:
  comb_sum=1
  fact=1
  comb1=1
  comb2=1
  for i in range(1,k+1):
    comb1=(comb1*(n-i+1)//i)%MOD
    comb2=(comb2*(n-i)//i)%MOD
    comb=(comb1*comb2)%MOD
    comb_sum+=comb
  
  print(comb_sum%MOD)

Submission status: Wrong Answer

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

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


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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)



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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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)

ans=cmb(2*n-1,n-1,mod)

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

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
ans = 0
for i in range(min(N-K,0),N+1):
  m = cmb(N,i,MOD)%MOD
  m *= cmb(N-1,i-1, MOD)%MOD
  ans += m
  ans %= MOD
print(ans)

Submission status: Wrong Answer

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(n, 0, -2):
  ans = (ans + f.comb(n, i) ** 2) % p
print(ans)

Submission status: Wrong Answer

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

mod = 10**9+7 #出力の制限
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 )


if k >= n - 1:
    ans = cmb(2 * n - 1, n, mod)

else:
    ans = cmb(n - k + n - 1, k, mod) * cmb(n, k, mod) * g2[k]
    ans %= mod

print(ans)

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



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


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

ans = 0
now = 22583772
print(679723794-now)
if k >= n-1:
    print(cmb(2*n-1,n-1,mod))
else:
    print((cmb(2*n-1,k,mod)*cmb(n,k-1,mod))%mod)

Submission status: Wrong Answer

Solution code:
def combination(n,r,mod=10**9+7):
    n1 = n+1
    r = 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

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

if k>=n-1:
    ans = combination(2*n-1,n)
else:
    a = k+1
    ans = combination(2*a-1,a)

print(ans)

Submission status: Wrong Answer

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


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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)

ans=cmb(2*n-1,n-1,mod)

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

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

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])
            result %= MOD

    return result%MOD

def solve():
    n, k = [int(_) for _ in input().split()]
    zen = cmb(2 * n - 1, n - 1)
    res = 0
    if n - k > 1:
        for i in range(1, n - k):
            res += cmb(n, i) * cmb(n + i - 1, i - 1)
            res %= MOD
    return (zen - res)%MOD
if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

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:
    if k % 2 == 1:
        ans -= 1
    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: Wrong Answer

Solution code:
N,K=map(int, raw_input().split())
 
mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, 2*N+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod

print ncr(N+N-1,N-1)

Submission status: Wrong Answer

Solution code:
def modinv(a,m):
    return pow(a,m-2,m)


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



if n-1 <= k:
    N = n + min(n-1,k)
    ans = 1
    for i in range(1,n):
        ans = ans*(N+1-i)*modinv(i,P)%P

else:
    ans = 0
    nCl = 1
    n1Cl = 1
    for l in range(1,k+1):
        nCl = nCl*(n+1-l)*modinv(l,P)%P
        n1Cl = n1Cl*(n-l)*modinv(l,P)%P
        ans = (ans+nCl*n1Cl)%P

print((ans+1)%P)

Submission status: Wrong Answer

Solution code:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def invmod(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

n, k = map(int, input().split())
c = 10**9 + 7
if k >= n-1:
    a = 2*n - 1
    ans = a
    temp = a
    for i in range(1, n-1):
        temp = temp*(a-i) % c
        temp = temp*invmod(i+1, c) % c
    print(temp)
else:
    temp1 = n
    temp2 = n-1
    ans = 1 + (temp1 * temp2) % c
    for i in range(1, k):
        temp1 = temp1*(n-i) % c
        temp2 = temp2*(n-i-1) % c
        inv = invmod(i+1, c)
        temp1 = temp1*inv % c
        temp2 = temp2*inv % c
        
        ans += temp1 * temp2 % c
    print(ans)

Submission status: Wrong Answer

Solution code:
def e_roaming(MOD=10**9 + 7):
    N, K = [int(i) for i in input().split()]
    from operator import mul
    from functools import reduce

    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])
                result %= MOD

        return result

    return cmb(2 * N - 1, N) if K >= N - 1 else sum([cmb(N, k) * cmb(N - 1, k) for k in range(K + 1)])

print(e_roaming())

Submission status: Wrong Answer

Solution code:
def modpow(a,n,mod):
    res = 1;
    while (n > 0):
        if (n%2==1):
          res = res * a % mod;
        a = a * a % mod;
        n=n//2;
    
    return res;

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

Submission status: Wrong Answer

Solution code:
def powermod(a,n,p):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res
def combimod(n, r, p):
    a = 1
    for i in range(n-r+1, n+1):
        a *= i
        a %= p
    b = 1
    for i in range(1, r + 1):
        b *= i
        b %= p
    return (a * powermod(b, p-2, p)) % p
n, k = map(int, input().split())
if n - 1 < k:
    k = n - 1
res = 0
for i in range(k + 1):
    res += (combimod(n-1, i, 1000000007) * combimod(n, i, 1000000007)) % 1000000007
print(res)

Submission status: Wrong Answer

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

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


p = 10 ** 9 + 7
N = 2 * (10**5)  # 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)
ans=0
if(k<n-1):
    for i in range(1,k):
        ans+=cmb(n,i,p)*cmb(n-1,i,p) % p
        #print(ans)
    ans+=1 % p
else:
    for i in range(1,n):
        ans+=cmb(n,i,p)*cmb(n-1,i,p) % p
        #print(ans)
    ans+=1 % p
print(ans)

Submission status: Wrong Answer

Solution code:
mod = int(1e9 + 7)
n, k = map(int, input().split())
a, b, c = 1, 1, 1


for i in range(1, 2*n):
    a *= i 
    a %= mod
for i in range(1, n+1):
    b *= i
    b %= mod
for i in range(1, n):
    c *= i
    c %= mod
# kakeru = (b * c) % mod
# print(a / kakeru)
print(a / (b*c))

Submission status: Wrong Answer

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

mod = 10**9 + 7

mod = 10**9 + 7

# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
	if a == 0:
		return 1
	elif a == 1:
		return x
	elif a % 2 == 0:
		return power(x, a//2) **2 % mod
	else:
		return power(x, a//2) **2 * x % mod

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
	return power(x, mod-2)

# 二項係数の左側の数字の最大値を max_len　とする。nとかだと他の変数と被りそうなので。
# factori_table = [1, 1, 2, 6, 24, 120, ...] 要は factori_table[n] = n!
# 計算時間はO(max_len * log(mod))

max_len = 2 * n - 1 #適宜変更する

factori_table = [1] * (max_len + 1)
factori_inv_table = [1] * (max_len + 1)
for i in range(1, max_len + 1):
	factori_table[i] = factori_table[i-1] * (i) % mod
	factori_inv_table[i] = modinv(factori_table[i])

def binomial_coefficients(n, k):
	# n! / (k! * (n-k)! )
	return (factori_table[n] * factori_inv_table[k] * factori_inv_table[n-k]) % mod

if k >= n-1:
    # nHn = 2n-1 C n
    print(binomial_coefficients(2 * n - 1, n))
else:
    # 移動がk回←→ 人数0の部屋がk個以下
    # 人数0の部屋がちょうどj個のものは
    # nCj(人数0の部屋の選び方) * jH(n-j) (余剰のj人を残りの部屋に入れる)
    ans = 0
    for j in range(k):
        if j == 0:
            ans += 1
        else:
            ans += binomial_coefficients(n, j) * binomial_coefficients(n-1, j-1) 
            ans %= mod
    print(ans)

Submission status: Wrong Answer

Solution code:
def modpow(a,n,mod):
    res = 1;
    while (n > 0):
        if (n%2==1):
          res = res * a % mod;
        a = a * a % mod;
        n=n//2;
    
    return res;

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+100
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())
if k>=n-1:
  ans=cmb(2*n-1,n-1,mod)
else:
  ans=cmb(n,k,mod)*modpow(k,n-k,mod)
  ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
#### 逆元リストいらない
mod = 10 ** 9 + 7
fact = [1]
fact_inv = [1]
for i in range(4*10**5+5):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))
def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod
if k >= n-1:
    ans = mod_comb_k(2*n-1,n-1,mod)
else:
    ans = mod_comb_k(2*n-1,n-1,mod)
    ans -= mod_comb_k(2*n-1-k,n-1-k,mod)
    if ans < 0:
        ans += mod
print(ans)

Submission status: Wrong Answer

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

if k%2==0:
    f=0
else:
    f=1

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def fact_m(n, modulus=10**9+7):
    ans=1
    if n <= modulus//2:
        for i in range(1,n+1):
            ans = (ans * i) % modulus
    else:
        for i in range(1,modulus-n):
            ans = (ans * i) % modulus
        ans = modinv(ans, modulus)

        if n % 2 == 0:
            ans = -1*ans + modulus
    return ans % modulus


ans=0
for i in range(f,k+1,2):
    zs=i
    os=n-i

    sm=fact_m(zs+os) / (fact_m(zs)*fact_m(os))

    sm *= (zs+os)
    sm %= 10**9+7

    ans+=sm

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
mod = int(1e+9) + 7
def extgcd(a, b):
  if b == 0:
    return 1, 0
  else:
    x, y, u, v, k, l = 1, 0, 0, 1, a, b
    while l != 0:
      x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
      k, l = l, k % l
    return x
def inved(x):
  a = extgcd(x, mod)
  return a % mod
def doubling(N, M):
  y = 1
  base = N
  while M != 0:
    if M % 2 == 1:
      y *= base
      y %= mod
    base *= base
    base %= mod
    M //= 2
  return y
fact = [1 for i in range(2*n)]
invf = [0 for i in range(2*n)]
for i in range(2*n-1):
  fact[i+1] = (fact[i] * (i + 1)) % mod
invf[2*n-1] = inved(fact[2*n-1])
for i in range(2*n-1, 0, -1):
  invf[i-1] = (invf[i] * i) % mod
if n <= k + 1:
  print((fact[2*n-1]*invf[n]*invf[n-1])%mod)
else:
  FK = fact[2*k-1] * invf[k]
  FK %= mod
  FK *= invf[k-1]
  FK %= mod
  FN = fact[n] * invf[k+1]
  FN %= mod
  FN = invf[n-k-1]
  FN %= mod
  print((FK * FN) % mod)

Submission status: Wrong Answer

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


#割り算のやーつ
MOD = 1000000007
# 二項係数関連.
class COM():
    def __init__(self, MAX, MOD):
        self.MOD = MOD
        self.MAX = MAX
        self.fac = [1] * MAX
        self.finv = [1] * MAX
        inv = [1] * MAX
        for i in range(2, MAX):
            self.fac[i] = self.fac[i - 1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i - 1] * inv[i] % MOD
    def calc_COM(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.MOD) % self.MOD
    def calc_PER(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * self.finv[n - k] % self.MOD
    def calc_FAC(self, n):
        if self.MAX <= n:
            return 0
        return self.fac[n]

com = COM(n * 2, MOD)
if(k == 1):
    # 0となる部屋と2となる部屋がそれぞれある.組み合わせ.
    print((n * (n - 1)) % MOD)
elif(n-1 <= k):
    # すべての組み合わせがあり得る.
    print(com.calc_COM(n*2-1, n) % MOD)
else:
    # 動けない人たちが現れる.
    # ∴0人の部屋は必ずk以下.逆も成り立つ.
    # この時、0人となる部屋をn-k(=r)以下で選び、そのそれぞれについて、rの部屋での移動パターンがどれだけあるかを求めればよい
    
    ans = 1 # 0人となる部屋が0の場合.1通り.
    for r in range(1, k + 1):
        ans += (com.calc_COM(n, r) * com.calc_COM(n - 1, r)) % MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
X,K = map(int,input().split())
N = X*2
mod = 10**9+7
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
def perm(n, k):
  return fact[n] * rfact[n-k] % mod
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % mod
N = X
patterns = [1]
for i in range(N+1):
    pattern = patterns[-1]*N*(N-1)
    pattern %= mod
    patterns.append(pattern)
max_value = comb(2*N-1,N-1)%mod
if K <= N-1:
    print(patterns[K]%mod)
else:
    print(max_value)

Submission status: Wrong Answer

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


#割り算のやーつ
MOD = 1000000007
# 二項係数関連.
class COM():
    def __init__(self, MAX, MOD):
        self.MOD = MOD
        self.MAX = MAX
        self.fac = [1] * MAX
        self.finv = [1] * MAX
        inv = [1] * MAX
        for i in range(2, MAX):
            self.fac[i] = self.fac[i - 1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i - 1] * inv[i] % MOD
    def calc_COM(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.MOD) % self.MOD
    def calc_PER(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * self.finv[n - k] % self.MOD
    def calc_FAC(self, n):
        if self.MAX <= n:
            return 0
        return self.fac[n]

com = COM(n * 2, MOD)
if(k == 1):
    # 0となる部屋と2となる部屋がそれぞれある.組み合わせ.
    print((n * (n - 1)) % MOD)
elif(n-1 <= k):
    # すべての組み合わせがあり得る.
    print(com.calc_COM(n*2-1, n) % MOD)
else:
    # 動けない人たちが現れる.
    # ∴0人の部屋は必ずk以下.逆も成り立つ.
    # この時、0人となる部屋をn-k(=r)以下で選び、そのそれぞれについて、rの部屋での移動パターンがどれだけあるかを求めればよい
    
    ans = 1 # 0人となる部屋が0の場合.1通り.
    for r in range(1, k + 1):
        ans += (com.calc_COM(n, r) * com.calc_COM(n - 1, r)) % MOD
        print(r, ans)
    print(ans)

Submission status: Wrong Answer

Solution code:
X,K = map(int,input().split())
N = X*2
mod = 10**9+7
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
def perm(n, k):
  return fact[n] * rfact[n-k] % mod
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % mod
N = X
patterns = [1]
for i in range(N+1):
    pattern = patterns[-1]*N*(N-1)
    pattern %= mod
    patterns.append(pattern)
max_value = comb(2*N-1,N-1)%mod
print(patterns)
if K <= N-1:
    print(patterns[K]%mod)
else:
    print(max_value)

Submission status: Wrong Answer

Solution code:
from math import factorial
def comb(n,k,p):
  if n<0 or k<0 or n<k:return 0
  if n==0 and k==0:return 1
  a=factorial(n)%p
  b=factorial(k)%p
  c=factorial(n-k)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
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
if k>=n-1:
  print(comb(2*n-1,n,mod))
else:
  print((power_func(n-1,k,mod)*3)%mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
mod = int(1e9+7)


def combination(n, r, mod):
    np1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (np1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


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

Submission status: Wrong Answer

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

#def combination(a,b):
#	out = 1
#	b = min(a-b,b)
#	for q in range(a-b+1, a+1):
#		out *= q
#		out %= mod

#	for q in range(1,b+1):
#		out *= pow(q, mod-2, mod)

#	out %= mod

#	return out




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

	tmp = 1
	tmp *= comb
	tmp *= pow(n-i, i, mod)
	tmp %= mod
	ans += tmp
	ans %= mod
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
mod=10**9+7
ans=0
fac=[1]
for i in range(n+1):
	r=fac[i]*(i+1)%mod
	fac.append(r)
def c(x,y):
	if x<y:
		return 0
	r=pow(fac[y]*fac[x-y]%mod,mod-2,mod)
	return r*fac[x]%mod
if k%2==0:
	ans+=1
for i in range(1,min(k,n-1)+1):
	kari=c(n,i)
	kari*=c(n-1,i)
	ans+=kari
	ans%=mod
print(ans)