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:
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)
    B = Comb2(N-1)
    for i in range(N):
        a = A.comb(i)
        b = B.comb(N-1-i)
        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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or 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):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

def solve():
  n,k = (int(i) for i in input().split())
  mod = 10**9+7
  if n-k <= 1:
    #任意の部屋に移動可能
    comba = 1
    inva = 1
    for i in range(1,n+1):
      comba *= (n+i-1)
      inva *= i
      comba %= mod
      inva %= mod
    comba *= pow(inva,10**9+5,mod)
    comba %= mod
    print(comba)
  else:
    #n <= 2**10^5
    #k <= 2**10^5
    ans = 0
    for i in range(0,k+1):
      ans += comb(n,i,mod)*comb(n-1,i,mod)
      ans %= mod
    
    print(ans)
  
solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce
mod=10**9+7
input=sys.stdin.readline
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)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def inv(a, mod):
    return pow(a, mod - 2, mod)


def C(F, a, b, mod):
    return F[a] * inv(F[a - b], mod) * inv(F[b], mod) % mod 


def main():
    N, K = read_values()
    mod = 10 ** 9 + 7
    F = functional(5 * 10 ** 5, mod)
    res = 0
    if N <= K:
        res = C(F, 2 * N - 1, N - 1, mod)
    else:
        for k in range(K + 1):
            res += C(F, N, k, mod) * C(F, N - 1 , k, mod) % mod
    
    print(res % mod)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
ans = 0
v = n
w = n - 1
memo = [0] * (10 ** 5 + 1)
memo[0] = 1
memo[1] = v * w

ans = 1 + v * w
mod = 10 ** 9 + 7
for i in range(2, min(n,k) + 1):
    v = (v * (n - i + 1)) // i
    w = (w * (n - i)) // i
    ans += v * w
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
def modinv(x):
    return pow(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)! )
    if k <= 0 or k >= n:
        return 1
    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+1):
        if j == 0:
            ans += 1
        else:
            ans += binomial_coefficients(n, j) * binomial_coefficients(n-1, j) 
            ans %= mod
    print(ans)

Submission status: Time Limit Exceeded

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

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)! )
    if k <= 0 or k >= n:
        return 1
    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+1):
        if j == 0:
            ans += 1
        else:
            ans += binomial_coefficients(n, j) * binomial_coefficients(n-1, j) 
            ans %= mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
k = min(k, n - 1)
p = 10 ** 9 + 7
size = n * 2
f_list = [1] * size
for i in range(1, size):
    f_list[i] = (f_list[i - 1] * i) % p

def cmb(n, r):
    return f_list[n] * pow(f_list[r], p-2, p) * pow(f_list[n - r], p-2, p) % p

# 初期値は0人の部屋が0個の場合
ans = 1
for i in range(1, k + 1):
    ans += cmb(n, i) * cmb(n - 1, i)
    ans = ans % p
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 1000000007


def init(fac, inv, finv, n):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, n + 1):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD


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


n, k = [int(x) for x in input().split()]
fac = np.zeros(200001, np.int64)
inv = np.zeros(200001, np.int64)
finv = np.zeros(200001, np.int64)
init(fac, inv, finv, n)

if k > n - 1:
    k = n - 1
ans = 0
for r in range(k + 1):
    ans = (ans + comb(n, r, fac, finv)*comb(n - 1, r, fac, finv))%MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
k=min(k,n-1)
mod=10000*100000+7
def mpow(a,b,m=100000*10000+7):#returns a**b%m
  ret=1
  while b>0:
    if b&1:
      ret=(ret*a)%m
    a=(a*a)%m
    b>>=1
  return ret
fact=[1]*(n+1)
for i in range(2,n+1):
  fact[i]=(fact[i-1] *i)%mod
def nCr(n,r):
  if r==0 or r==n:
    return 1
  val=((fact[n]*mpow(fact[r],mod-2))%mod*mpow(fact[n-r],mod-2))%mod
  return val
ans=0
for h in range(k+1):
  ans=(ans+(nCr(n,h)*nCr(n-1,n-h-1))%mod)%mod
print(ans)

Submission status: Time Limit Exceeded

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

# modify pow and inverse
# put inverse into val
class ModInt:
    def __init__(self, num, mod):
        self.num = num
        self.mod = mod

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

    def __repr__(self):
        return "ModInt(num: {}, mod: {}".format(self.num, self.mod)

    def __add__(self, other):
        ret = self.num + other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __sub__(self, other):
        ret = self.num - other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __mul__(self, other):
        ret = self.num * other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def pow(self, times):
        if times == 0:
            return ModInt(1, self.mod)

        x = self.pow(times // 2)
        x *= x
        if times % 2:
            x *= self

        return x

    def inverse(self):
        return self.pow(self.mod - 2)

    def __truediv__(self, other):
        num = self * other.inverse()
        return ModInt(num, self.mod)


class Combination:
    def __init__(self, n, mod):
        self.mod = mod
        self.fact = [ModInt(1, mod)]
        self.inverse = [ModInt(1, mod)]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * ModInt(i, mod))
            self.inverse.append(self.inverse[-1] * ModInt(i, mod).inverse())

    def comb(self, n, k):
        if k < 0 or n < k:
            return ModInt(0, self.mod)

        return self.fact[n] * self.inverse[k] * self.inverse[n-k]


mx = min(k, n - 1)
comb = Combination(n, mod)
ans = ModInt(0, mod)

for i in range(mx + 1):
    ans += comb.comb(n, i) * comb.comb(n - 1, i)

print(ans)

Submission status: Time Limit Exceeded

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


class ModInt:
    def __init__(self, num, mod):
        self.num = num
        self.mod = mod

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

    def __repr__(self):
        return "ModInt(num: {}, mod: {}".format(self.num, self.mod)

    def __add__(self, other):
        ret = self.num + other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __sub__(self, other):
        ret = self.num - other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __mul__(self, other):
        ret = self.num * other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def pow(self, times):
        pw = pow(self.num, times, self.mod)
        return ModInt(pw, self.mod)

    def inverse(self):
        return self.pow(self.mod - 2)

    def __truediv__(self, other):
        num = self * other.inverse()
        return ModInt(num, self.mod)


class Combination:
    def __init__(self, n, mod):
        self.mod = mod
        self.fact = [ModInt(1, mod)]
        self.inverse = [ModInt(1, mod)]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * ModInt(i, mod))
            self.inverse.append(self.inverse[-1] * ModInt(i, mod).inverse())

    def comb(self, n, k):
        if k < 0 or n < k:
            return ModInt(0, self.mod)

        return self.fact[n] * self.inverse[k] * self.inverse[n-k]


mx = min(k, n - 1)
comb = Combination(n, mod)
ans = ModInt(0, mod)

for i in range(mx + 1):
    ans += comb.comb(n, i) * comb.comb(n - 1, i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

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

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

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

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
    
    def __iadd__(self,other):
        self.x += other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self

    def __isub__(self,other):
        self.x += ModInt(MOD - other.x) if isinstance(other, ModInt) else ModInt(MOD - other)
        return self

    def __imul__(self, other):
        self.x *= other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self
    
    def factorical(self,n):
        tmp = ModInt(1)
        for i in range(n):
            tmp *= (i+1)
        return tmp
    
    #m:int MOD
    def modinv(self,a,m=MOD):
        b = m
        u = 1
        v = 0
        while(b):
            t = a//b
            a -= t * b
            a,b = b,a
            u -= t * v
            u,v = v,u
        return ModInt(u)

    def comb(self,n,r):
        n = int(n)
        r = int(r)
        if r > n or n < 0 or r < 0:
            return 0
        m = n+1
        nterms = min(r, n-r)
        numerator = ModInt(1)
        denominator = ModInt(1)
        for j in range(1, nterms + 1):
            numerator *= m - j
            denominator *= j
        return numerator * self.modinv(denominator.x)
        
if __name__ == "__main__":
    n,k = map(int,input().split())
    if n-1 <= k:
        x = ModInt(1)
        print(x.comb(n+n-1,n))
    else:
        ans = ModInt(0)
        for i in range(k+1):
            #print(ans)
            ans += ans.comb(n,i)*ans.comb(n-1,n-i-1)
        print(ans)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

def choose(n, r):
    x = 1
    y = 1
    for i in range(1, r+1):
        x = (x * (n-i+1)) % mod
        y = (y * i) % mod
    return (x * pow(y, mod-2, mod)) % mod

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

Submission status: Time Limit Exceeded

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

def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n):
    #0!からn!までの逆元を素数10**9+7で割ったあまりリストを作る関数
    powlist=find_power(n,10**9+7)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

mod = 10**9+7
a=find_power(4*10**5+100,mod)
b=find_inv_power(4*10**5+100)

def comb(n,r,mod=10**9+7):
    if n<r:
        return 0
    elif n>=r:
        return (a[n]*b[r]*b[n-r])%(mod)

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

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

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a = 1
  b = 1
  c = 1
  for i in range(1,n+1):
    a = (a*i)%p
  for i in range(1,k+1):
    b = (b*i)%p
  for i in range(1,n-k+1):
    c = (c*i)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
mod = 10**9 + 7
zeronum = min(n-1,k)
ans = 1
for zero in range(1,zeronum+1):
    count = comb(n,zero,mod)
    one = n-zero
    count = (count*comb(one+zero-1,zero,mod))%mod
    ans = (ans+count)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
 
n,k = map(int, input().split())
 
################
p = 10**9 + 7
comb_memo = {}
def comb(n,k,p):
  if (n,k) in comb_memo:
    return comb_memo[(n,k)]
  else:
    ans = 1
    for i in range(1,k+1):
      ans = ans * (n - (i-1)) % p
      ans = ans * pow(i, p-2, p)
    comb_memo[(n,k)] = ans
    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
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def modInverse(a, p):
    return pow(a, p - 2, p)


@lru_cache(maxsize=None)
def modBinomial(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % p

    denominator = 1
    for i in range(1, k + 1):
        denominator = (denominator * i) % p

    return (numerator * modInverse(denominator, p)) % p


def main():
    N, K = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7

    a = min(N - 1, K)

    ans = 1
    for i in range(1, a + 1):
        ans += (modBinomial(N, i, MOD) * modBinomial(N - 1,  N - i - 1, MOD)) % MOD

    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def modInverse(a, p):
    return pow(a, p - 2, p)


@lru_cache(maxsize=None)
def modBinomial(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % p

    denominator = 1
    for i in range(1, k + 1):
        denominator = (denominator * i) % p

    return (numerator * modInverse(denominator, p)) % p


def main():
    N, K = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7

    a = min(N - 1, K)

    ans = 1
    for i in range(1, a + 1):
        ans += modBinomial(N, i, MOD) * modBinomial(N - 1,  N - i - 1, MOD)

    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def calc(n, a, m):
    x = 1
    y = 1
    if a > n//2:
        a = n-a
    for i in range(a):
        x = (x*(n-i))%m
        y = (y*(i+1))%m
    return (x*pow(y, m-2, m))%m

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

Submission status: Time Limit Exceeded

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

def calc(n, a, m):
    x = 1
    y = 1
    for i in range(a):
        x = (x*(n-i))%m
        y = (y*(i+1))%m
    return (x*pow(y, m-2, m))%m

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from functools import reduce

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

MOD = 10 ** 9 + 7

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

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

def div(a, b):
  return mul(a, power(b, MOD - 2))

def dict1():
  return {0: 1}

numer_cache = defaultdict(dict1)
denom_inv_cache = dict1()

def combinations_count(n, r):
  r = min(r, n - r)
  numer_cache_n = numer_cache[n]
  if r not in numer_cache_n:
    numer_cache_n[r] = mul(numer_cache_n[r - 1], n - r + 1)
  if r not in denom_inv_cache:
    denom_inv_cache[r] = div(denom_inv_cache[r - 1], r)
  return mul(numer_cache_n[r], denom_inv_cache[r])

print(sum(mul(combinations_count(n, i), combinations_count(n - 1, i)) for i in range(min(n, k + 1))) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


CHECK = False

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)


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


def nCr(n, r, p=MOD):
    # Modulo binomial coefficients
    return (fact[n] * modInverse(fact[r], p) * modInverse(fact[n - r], 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
    comb1 = 1
    comb2 = 1
    for numEmpty in range(K + 1):
        way3 = comb1 * comb2
        if CHECK:
            numNonEmpty = N - numEmpty
            stars = numEmpty  # Everyone moving into an occupied room
            bars = numNonEmpty - 1  # Number of dividers
            way1 = nCr(stars + bars, bars) * nCr(N, numEmpty)

            way2 = nCr(N, numEmpty) * nCr(N - 1, numEmpty)

            assert way1 % MOD == way2 % MOD == way3 % MOD
        tot += way3

        j = numEmpty + 1
        comb1 = (N + 1 - j) * comb1 * modInverse(j, MOD) % MOD
        comb2 = (N - j) * comb2 * modInverse(j, MOD) % MOD
    print(tot % MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from functools import reduce

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

MOD = 10 ** 9 + 7

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

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

def div(a, b):
  return mul(a, power(b, MOD - 2))

numer_cache = defaultdict(dict)
denom_inv_cache = {}

def numer(n, r):
  if r == 0:
    return 1
  numer_cache_n = numer_cache[n]
  if r not in numer_cache_n:
    numer_cache_n[r] = mul(numer(n, r - 1), n - r + 1)
  return numer_cache_n[r]

def denom_inv(r):
  if r == 0:
    return 1
  if r not in denom_inv_cache:
    denom_inv_cache[r] = div(denom_inv(r - 1), r)
  return denom_inv_cache[r]

def combinations_count(n, r):
  r = min(r, n - r)
  return mul(numer(n, r), denom_inv(r))

print(sum(mul(combinations_count(n, i), combinations_count(n - 1, i)) for i in range(min(n, k + 1))) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from functools import reduce

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

MOD = 10 ** 9 + 7

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

def power(x, y):
  if y == 0:
    return 1
  elif y == 1:
    return x % MOD
  elif y % 2 == 0:
    return power(x, y // 2) ** 2 % MOD
  else:
    return mul(power(x, y // 2) ** 2, x)

def div(a, b):
  return mul(a, power(b, MOD - 2))

numer_cache = defaultdict(dict)
denom_inv_cache = {}

def numer(n, r):
  if r == 0:
    return 1
  numer_cache_n = numer_cache[n]
  if r not in numer_cache_n:
    numer_cache_n[r] = mul(numer(n, r - 1), n - r + 1)
  return numer_cache_n[r]

def denom_inv(r):
  if r == 0:
    return 1
  if r not in denom_inv_cache:
    denom_inv_cache[r] = div(denom_inv(r - 1), r)
  return denom_inv_cache[r]

def combinations_count(n, r):
  r = min(r, n - r)
  return mul(numer(n, r), denom_inv(r))

print(sum(mul(combinations_count(n, i), combinations_count(n - 1, i)) for i in range(min(n, k + 1))) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from functools import reduce

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

MOD = 10 ** 9 + 7

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

def power(x, y):
  if y == 0:
    return 1
  elif y == 1:
    return x % MOD
  elif y % 2 == 0:
    return power(x, y // 2) ** 2 % MOD
  else:
    return mul(power(x, y // 2) ** 2, x)

def div(a, b):
  return mul(a, power(b, MOD - 2))

numer_cache = defaultdict(dict)
denom_inv_cache = {}

def numer(n, r):
  if r == 0:
    return 1
  if r not in numer_cache[n]:
    numer_cache[n][r] = mul(numer(n, r - 1), n - r + 1)
  return numer_cache[n][r]

def denom_inv(r):
  if r == 0:
    return 1
  if r not in denom_inv_cache:
    denom_inv_cache[r] = div(denom_inv(r - 1), r)
  return denom_inv_cache[r]

def combinations_count(n, r):
  r = min(r, n - r)
  return mul(numer(n, r), denom_inv(r))

print(sum(mul(combinations_count(n, i), combinations_count(n - 1, i)) for i in range(min(n, k + 1))) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


CHECK = False

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)


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


def nCr(n, r, p=MOD):
    # Modulo binomial coefficients
    numerator = fact[n]
    d1 = fact[r]
    d2 = fact[n - r]
    return (numerator * modInverse(d1, p) * modInverse(d2, 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):
        way2 = nCr(N, numEmpty) * nCr(N - 1, numEmpty)
        if CHECK:
            numNonEmpty = N - numEmpty
            stars = numEmpty  # Everyone moving into an occupied room
            bars = numNonEmpty - 1
            way1 = nCr(stars + bars, bars) * nCr(N, numEmpty)
            assert way1 == way2
        tot += way2
    print(tot % MOD)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


CHECK = False

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)


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


@lru_cache(maxsize=None)
def nCr(n, r, p=MOD):
    # Modulo binomial coefficients
    numerator = fact[n]
    d1 = fact[r]
    d2 = fact[n - r]
    return (numerator * modInverse(d1, p) * modInverse(d2, 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):
        way2 = nCr(N, numEmpty) * nCr(N - 1, numEmpty)
        if CHECK:

            numNonEmpty = N - numEmpty
            stars = numEmpty  # Everyone moving into an occupied room
            bars = numNonEmpty - 1
            way1 = nCr(stars + bars, bars) * nCr(N, numEmpty)
            assert way1 == way2

        tot += way2
    print(tot % MOD)