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: Time Limit Exceeded

Solution code:
from functools import lru_cache

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


MOD = 10 ** 9 + 7


@lru_cache(maxsize=None)
def modInverse(a, p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a, p - 2, p)

@lru_cache(maxsize=None)
def nCr(n, r, p=MOD):
    # Modulo binomial coefficients
    num = 1
    den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return num * modInverse(den, p) % p


if N - 1 < K:
    # Any combo is achievable so this is stars and bars
    # N people into N rooms, which means N - 1 dividers
    stars = N
    bars = N - 1
    print(nCr(stars + bars, bars))
else:
    # Group by number of empty rooms
    # With K moves there can only be at most K empty rooms
    # Max of N - 1 empty rooms in general
    assert K + 1 <= N
    tot = 0
    for numEmpty in range(K + 1):
        numNonEmpty = N - numEmpty
        stars = numEmpty  # Everyone moving into an occupied room
        bars = numNonEmpty - 1
        tot += nCr(stars + bars, bars) * nCr(N, numEmpty)
    print(tot % MOD)

Submission status: Time Limit Exceeded

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


MOD = 10 ** 9 + 7


def modInverse(a, p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a, p - 2, p)


def nCr(n, r, p=MOD):
    # Modulo binomial coefficients
    num = 1
    den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return num * modInverse(den, p) % p


if N - 1 < K:
    # Any combo is achievable so this is stars and bars
    # N people into N rooms, which means N - 1 dividers
    stars = N
    bars = N - 1
    print(nCr(stars + bars, bars))
else:
    tot = 0
    # Group by number of empty rooms
    # With K moves there can only be at most K empty rooms
    # Max of N - 1 empty rooms in general
    assert K + 1 <= N
    for numEmpty in range(K + 1):
        numNonEmpty = N - numEmpty
        stars = numEmpty  # Everyone moving into an occupied room
        bars = numNonEmpty - 1
        tot += nCr(stars + bars, bars) * nCr(N, numEmpty)
    print(tot % MOD)

Submission status: Time Limit Exceeded

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
    r2 = 1
    for i in range(k):
        r1 = r1 * (n - i) % M
        r2 = r2 * (i + 1) % M
    return r1 * inv(r2, M) % M

memo = {}
def memo_comb(n, k):
    if k == 0:
        return 1
    if (n, k) in memo:
        return memo[(n, k)]
    comb_n_k_1 = memo_comb(n, k - 1)
    r = comb_n_k_1 * (n - k + 1) % M
    return r * inv(k, M) % M

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

def solve(n, k):
    if k >= n:
        return h(n, n)
    r1, r2, r3 = 1, 1, 1
    r = 0
    for i in range(k + 1):
        # r = (r + comb(n, i) * comb(n - 1, i)) % M
        r = (r + (r1 * inv(r2, M) % M) * (r3 * inv(r2, M) % M)) % M
        r1 = r1 * (n - i) % M
        r2 = r2 * (i + 1) % M
        r3 = r3 * (n - 1 - 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: Time Limit Exceeded

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
  
inv_table = [0]+[1]
for i in range(2,k+1):
  inv_table+=[inv_table[MOD%i]*(MOD-int(MOD/i))%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
    comb1=(comb1*(n-i+1)*inv_table[i])%MOD
    #comb2=comb2*(n-i)//i
    comb2=(comb2*(n-i)*inv_table[i])%MOD
    comb=(comb1*comb2)%MOD
    comb_sum+=comb
  
  print(comb_sum%MOD)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
 
n,k = map(int, input().split())
 
################
p = 10**9 + 7
def comb(n,k,p):
  ans = 1
  for i in range(1,k+1):
    ans = ans * (n - (i-1)) % p
    ans = ans * pow(i, p-2, p)
  return ans
################
 
if k >= n:
  ans = comb(2*n-1, n, p) % p
else:
  ans = 0
  for i in range(0,k+1):
    temp = (comb(n-1, i, p) % p) * (comb(n, i, p) % p) % p
    ans = (ans + temp) % p
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
MOD = 10**9+7

MAXN = 2*10**5+5
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

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

Submission status: Time Limit Exceeded

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
    comb2=comb2*(n-i)//i
    comb=(comb1*comb2)%MOD
    comb_sum+=comb
  
  print(comb_sum%MOD)

Submission status: Time Limit Exceeded

Solution code:
def comb(n,k,p):
  from math import factorial
  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
ans=0
r=min(k,n)
for i in range(r+1):
  ans=(ans+comb(n,i,mod)*comb(n-1,i,mod))%mod
print(ans)

Submission status: Time Limit Exceeded

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
    comb2=comb2*(n-i)//i
    comb=(comb1*comb2)%MOD
    comb_sum+=comb
  
  print(comb_sum%MOD)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
 
n,k = map(int, input().split())
 
################
p = 10**9 + 7
def comb(n,k,p):
  ans = 1
  for i in range(1,k+1):
    ans = ans * (n - (i-1)) % p
    ans = ans * pow(i, p-2, p)
  return ans
################
 
if k >= n:
  ans = comb(2*n-1, n, p) % p
else:
  ans = 0
  for i in range(0,k+1):
    temp = comb(n-1, i, p) % p
    temp2 = comb(n, i, p) % p
    temp = temp * temp2 % p
    ans = (ans + temp) % p
    
print(ans)

Submission status: Time Limit Exceeded

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 = (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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
 
n,k = map(int, input().split())
 
################
p = 10**9 + 7
def comb(n,k,p):
  ans = 1
  for i in range(1,k+1):
    ans = ans * (n - (i-1)) % p
    ans = ans * pow(i, p-2, p)
  return ans
################
 
if k >= n:
  ans = comb(2*n-1, n, p) % p
else:
  ans = 0
  for i in range(0,k+1):
    temp = comb(n-1, n-i-1, p) % p
    temp2 = comb(n, i, p) % p
    temp = temp * temp2 % p
    ans = (ans + temp) % p
    
print(ans)

Submission status: Time Limit Exceeded

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

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

################
p = 10**9 + 7
def comb(n,k,p):
  ans = 1
  for i in range(1,k+1):
    ans = ans * (n - (i-1)) % p
    ans = ans * pow(i, p-2, p)
  return ans
################

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

Submission status: Time Limit Exceeded

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) % MOD for k in range(K + 1)]) % MOD

print(e_roaming())

Submission status: Time Limit Exceeded

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 = 3*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 )

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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 = 10**6 +1
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:
    print(cmb(2*n-1, n-1, mod))
    exit()

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

Submission status: Time Limit Exceeded

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

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

################
p = 10**9 + 7
def comb(n,k,p):
  ans = 1
  for i in range(1,k+1):
    ans = ans * (n - (i-1)) % p
    ans = ans * pow(i, p-2, p)
  return ans
################

MAX = comb(2*n-1, n, p)%p



if k >= n:
  print(MAX)
else:
  ans = 0
  for i in range(0,k+1):
    temp = comb(n-1, n-i-1, p)%p
    temp2 = comb(n, i, p)%p
    temp = temp * temp2 %p
    ans = (ans + temp ) %p
    
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
def factorial(n, mod=10**9+7):
    a = 1
    for i in range(1,n+1):
        a = a * i % mod
    return a


def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


def comb(n, k, mod=10**9+7):
    if n < k or k < 0:
        result = 0
    else:
        a = factorial(n, mod=mod)
        b = factorial(k, mod=mod)
        c = factorial(n-k, mod=mod)
        result = (a * power(b, mod-2, mod=mod) * power(c, mod-2, mod=mod)) % mod
    return result

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

if k >= n:
  print(comb(2*n-1, n))
  quit()

def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


fl = [-1]*(k+1)
fl[0] = 1
def f(i):
  global fl
  if fl[i] > 0: return fl[i]
  else:
    if i <= n//2:
      res = f(i-1)*(n-i+1)*(n-i)
      t = power(i, MOD-2)
      res *= t
      res %= MOD
      res *= t
      res %= MOD
      fl[i] = res
      return res
    else:
      res = f(n-i) * (n-i)
      res *= power(i, MOD-2)
      res %= MOD
      fl[i] = res
      return res


ans = 0
for i in range(k+1):
  ans += f(i)
  ans %= MOD


print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

n,k = LI()

# 互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

# aの逆元(mod M)を求める（aとMは互いに素）
def mod_inv(a,M=mod):
    x = extgcd(a,M)[0]
    return (M+x%M)%M

def nCk2(n,k):
    x = [0]*(k+1)
    x[0] = 1
    for i in range(1,k+1):
        x[i] = x[i-1]*(n-k+i)*mod_inv(i) % mod
    return x[-1]

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

Submission status: Time Limit Exceeded

Solution code:
#コンビネーション。
def comb(n,m,p=10**9+7):
    if n < m : return 0
    if n < 0 or m < 0:return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p

#累乗
def mpow(x: int, k: int, MOD=1000000007) -> int:
    res = 1
    y = x
    while (k):
        if(k % 2 == 1):
            res = (res * y) % MOD
        y = (y ** 2) % MOD
        k = k // 2
    return res

[n,k] = list(map(int,input().split()))

if k>=n:
    k = n
output = 0
for i in range(1,k+1):
    output += comb(n,i)*comb(n-1,n-i-1)
    output = output%(10**9+7)
if k>=2:
    output+=1
print(output)

Submission status: Time Limit Exceeded

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))
MOD=10 ** 9 + 7

def combination(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


n, k = MI()

if k >= n:
    print(combination(2 * n - 1, n, MOD))
    exit(0)

ans = 1
for l in range(1, k + 1):
    ans += combination(n, l) * combination(n - 1, l)
    ans %= MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
def factorial(n, mod=10**9+7):
    a = 1
    for i in range(1,n+1):
        a = a * i % mod
    return a


def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


def comb(n, k, mod=10**9+7):
    if n < k or k < 0:
        result = 0
    else:
        a = factorial(n, mod=mod)
        b = factorial(k, mod=mod)
        c = factorial(n-k, mod=mod)
        result = (a * power(b, mod-2, mod=mod) * power(c, mod-2, mod=mod)) % mod
    return result

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

if k >= n:
  print(comb(2*n-1, n))
  quit()

def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


fl = [-1]*(k+1)
fl[0] = 1
def f(i):
  global fl
  if fl[i] > 0: return fl[i]
  else:
    res = f(i-1)*(n-i+1)*(n-i)
    t = power(i, MOD-2)
    res *= t
    res %= MOD
    res *= t
    res %= MOD
    fl[i] = res
    return res


ans = 0
for i in range(k+1):
  ans += f(i)
  ans %= MOD


print(ans % MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

class Bigint:
    def __init__(self,n,mod=10**9+7):
        self.n = n % mod
        self.mod = mod
        return


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


    def __add__(self,other):
        ot = type(other)
        if ot==Bigint:
            return Bigint(self.n+other.n,self.mod)
        elif ot==int:
            return Bigint(self.n+other,self.mod)
        else:
            raise ValueError("Invalid type")


    def __iadd__(self,other):
        return self.__add__(other)


    def __sub__(self,other):
        ot = type(other)
        if ot==Bigint:
            o = other.n
        elif ot==int:
            o = other
        else:
            raise ValueError("Invalid type")
        #
        return Bigint(self.n - o, self.mod)


    def __isub__(self,other):
        return self.__sub__(other)


    def __mul__(self,other):
        ot = type(other)
        if ot==Bigint:
            return Bigint(self.n*other.n,self.mod)
        elif ot==int:
            return Bigint(self.n*other,self.mod)
        else:
            raise ValueError("Invalid type")


    def __imul__(self,other):
        return self.__mul__(other)


    def __pow__(self,other):
        assert type(other)==int, "power should be integer"
        #
        if other<0: return self ** ( other % ( self.mod-1 ) )
        ret = Bigint(1,self.mod)
        now = Bigint(self.n,self.mod)
        while other>0:
            if other%2==0: pass
            else: ret *= now
            other//=2
            now*=now
        return ret


    def __truediv__(self,other):
        ot = type(other)
        if ot==Bigint:
            o = other
        elif ot==int:
            o = Bigint(other)
        else:
            raise ValueError("Invalid type")

        self *= ( o ** (o.mod-2) )
        return self


    def __itruediv__(self,other):
        return self.__truediv__(other)

def combination(n,k):
   kp = min(k,n-k)

   ne = Bigint(1)
   for i in range(n-kp+1, n+1): ne *= i
   de = Bigint(1)
   for i in range(1, kp+1): de *= i
   return ne / de

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

ret = Bigint(0)
for i in range(k+1):
   ret += combination(n-1, i) * combination(n, i)
print(ret)

Submission status: Time Limit Exceeded

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())
ans = combination(2*n-1, n)
for i in range(k+1, n):
    ans -= combination(n, i) * combination(n-1, i)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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
        for i in range(k+1):
            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: Time Limit Exceeded

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 combinations_with_replacement_count(n, r):
    return combinations_count(n + r - 1, r)

if n-1 <= k:
    print(combinations_count(2*n-1,n)%1000000007)
else:
    count = 0
    for i in range(k+1):
        count += combinations_count(n,i)*combinations_with_replacement_count(n-i,i)%1000000007
    print(count%1000000007)

Submission status: Time Limit Exceeded

Solution code:
def factorial(n, mod=10**9+7):
    a = 1
    for i in range(1,n+1):
        a = a * i % mod
    return a


def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


def comb(n, k, mod=10**9+7):
    if n < k or k < 0:
        result = 0
    else:
        a = factorial(n, mod=mod)
        b = factorial(k, mod=mod)
        c = factorial(n-k, mod=mod)
        result = (a * power(b, mod-2, mod=mod) * power(c, mod-2, mod=mod)) % mod
    return result

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

if k >= n:
  print(comb(2*n-1, n))
  quit()

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

p = {}
def power(n, r, mod=10**9+7):
    global p
    if r == 0: return 1
    if (n, r) in p: return p[(n, r)]
    if r%2 == 0:
        a = power(n*n % mod, r//2, mod) % mod
        p[(n, r)] = a
        return a
    if r%2 == 1:
        a = n * power(n, r-1, mod) % mod
        p[(n, r)] = a
        return a

def f(i):
  res = fact[n] * fact[n-1] % MOD
  res *= power(fact[n-i], MOD-2)
  res %= MOD
  res *= power(fact[n-i-1], MOD-2)
  res %= MOD
  t = power(fact[i], MOD-2)
  res *= t
  res %= MOD
  res *= t
  res %= MOD
  return res
  

ans = 0
for i in range(k+1):
  ans += f(i)
  ans %= MOD

print(ans % MOD)

Submission status: Time Limit Exceeded

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()
sm = 0
for j in range(n-k,n+1):
    sm = (sm+comb(n,j)*comb(n-1,j-1))%R
print(sm)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def inv(x):
    return pow(x, MOD-2, MOD)

def nPk(n,k):
    x=1
    for a in range(n-k+1, n+1):
        x = x * a % MOD
    return x

def nCk(n,k):
    return nPk(n,k) * inv(nPk(k,k))

MOD = 10**9+7

n,k = get_nums_l()

if k >= n-1:
    print(nCk(n+n-1, n) % MOD)
    exit()

# 0人の部屋=zがk以下であるような人数の並べ方の個数

# z=0 1
# z=1 nC1 * (n-1)**1
# z=2 nC2 * (n-2)**2
# z=3 nC3 * (n-3)**3

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

print(ans%MOD)

Submission status: Time Limit Exceeded

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

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

def mod_prod(a,b):
    return a * b % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n // 2
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret


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