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:
n,k = map(int,input().split())

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


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

Submission status: Time Limit Exceeded

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

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

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

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

    return result

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

Submission status: Time Limit Exceeded

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

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


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

if k == 1:
    print(ans % mod)

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

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

print(t%m)

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n,k = mi()
#a^-1 (mod P)
mod = 10 ** 9 +7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

#  これは計算量rでncr mod p を求められる。
def combination(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

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

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def M(n): return ModInt(n)
def MI(): return M(I())

class ModInt():
    def __init__(self, n):
        self.n = n

    def __add__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n+x) % mod)

    def __sub__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n-x) % mod)

    def __mul__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n*x) % mod)

    def __truediv__(self, x):
        x = ModInt.xn(x)
        return ModInt(self.n * pow(x, mod-2, mod) % mod)

    @classmethod
    def xn(cls, x):
        if isinstance(x, ModInt):
            return x.n
        return x

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

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

cms = 10**6
cm = [0] * cms

def comb_init():
    cm[0] = 1
    for i in range(1, cms):
        cm[i] = cm[i-1] * i % mod

def comb(a, b):
    return (cm[a] * inv(cm[a-b]) % mod) * inv(cm[b]) % mod

def h(a,b):
    return comb(a+b-1, b)

def main():
    n,k = LI()
    comb_init()
    r = M(1)
    t = M(1)
    for i in range(1, min(n-1,k)+1):
        t *= n-i+1
        t /= i
        r += t * h(n-i,i)

    return r


print(main())

Submission status: Time Limit Exceeded

Solution code:

import numpy as np

MOD = int(1e9+7)

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

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

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

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

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

premax = int(200020)
mymodflag = False
f, rf = np.zeros(premax, dtype=ModInt), np.zeros(premax, dtype=ModInt)
def nCk(n, k) :
    global mymodflag, r, rf, premax
    if ( n == k ) : return ModInt(0)
    if ( not mymodflag ) : 
        f[0] = ModInt(1)
        for i in range(1,premax) : f[i] = f[i-1]*ModInt(i)
        rf[premax-1] = pow(f[premax-1], MOD-2)
        for i in range(premax-2, -1, -1) : rf[i] = rf[i+1]*ModInt(i+1)
        mymodflag = True
    return f[n]*rf[n-k]*rf[k]

def nPk(n, k) :
    global mymodflag, r, rf, premax
    if ( n == k ) : return ModInt(0)
    if ( not mymodflag ) : 
        f[0] = ModInt(1)
        for i in range(1,premax) : f[i] = f[i-1]*ModInt(i)
        rf[premax-1] = pow(f[premax-1], MOD-2)
        for i in range(premax-2, -1, -1) : rf[i] = rf[i+1]*ModInt(i+1)
        mymodflag = True
    return f[n]*rf[n-k]


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

ans = ModInt(0)
for m in range(0, min(n,k+1)) :
    ans += nCk(n,m)*nCk(n-1, n-m-1)

print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
mod = 7+10**9

def expo(x):
  ans = 1
  n = mod-2
  while n>0:
    if n%2 == 1:
      ans = ans*x%mod
    x = x*x%mod
    n = n >> 1
  return ans

#def combi(n,k):
#  return ((fac[n]*(expo_fac[k])%mod)*expo_fac[n-k]%mod)

n,k = map(int,input().split())
fac = [1]+[0]*n
for i in range(1,n+1):
  fac[i] = fac[i-1]*i%mod

expo_fac = [expo(fac[i]) for i in range(n+1)]

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

Submission status: Time Limit Exceeded

Solution code:
mod = 7+10**9

def expo(x):
  ans = 1
  n = mod-2
  while n>0:
    if n%2 == 1:
      ans = ans*x%mod
    x = x*x%mod
    n = n >> 1
  return ans

def combi(n,k):
  return (fac[n]*(expo_fac[k])%mod)*expo_fac[n-k]%mod

n,k = map(int,input().split())
fac = [1]+[0]*n
for i in range(1,n+1):
  fac[i] = fac[i-1]*i%mod

expo_fac = [expo(fac[i]) for i in range(n+1)]

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

Submission status: Time Limit Exceeded

Solution code:
mod = 7+10**9

def expo(x):
  ans = 1
  n = mod-2
  while n>0:
    if n%2 == 1:
      ans = ans*x%mod
    x = x*x%mod
    n = n >> 1
  return ans

def combi(n,k):
  return (fac[n]*(expo(fac[k]))%mod)*expo(fac[n-k])%mod

n,k = map(int,input().split())
fac = [1]+[0]*n
for i in range(1,n+1):
  fac[i] = fac[i-1]*i%mod

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

Submission status: Time Limit Exceeded

Solution code:
def pow_mod(a, b, p):
    res = 1
    mul = a
    for i in range(len(bin(b)) - 2):
        if (1 << i) & b:
            res = (res * mul) % p
        mul = (mul ** 2) % p
    return res


def perm_mod(n, r, p):
    res = 1
    for i in range(r):
        res = (res * (n - i)) % p
    return res


def comb_mod(n, r, p, factorial=None, invert_factorial=None):
    if factorial and invert_factorial:
        return (factorial[n] * invert_factorial[r] * invert_factorial[n - r]) % p

    r = min(r, n - r)
    return (perm_mod(n, r, p) * pow_mod(perm_mod(r, r, p), p - 2, p)) % p


def main():
    p = 10 ** 9 + 7
    n, k = map(int, input().split())

    factorial = [1] * (n + 1)
    for i in range(1, n + 1):
        factorial[i] = (factorial[i - 1] * i) % p

    invert_factorial = [pow_mod(x, p - 2, p) for x in factorial]

    res = 0
    for i in range(min(k + 1, n)):
        res = (res + comb_mod(n, i, p, factorial, invert_factorial)
               * comb_mod(n - 1, i, p, factorial, invert_factorial)) % p
    print(res)


main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
 
mod7 = 10 ** 9 + 7
 
 
def power(a, b, mod):
    p = 1
    q = a
    while b != 0:
        if b % 2 == 1:
            p = (p * q) % mod
        q = (q * q) % mod
        b = b // 2
    return p
 
 
def fact(n, mod):
    p = 1
    for i in range(1, n + 1):
        p = (p * i) % mod
    return p
 
 
def combi(n, a, mod):
    if a == 0:
        return 1
    else:
        inv_af = power(fact(a, mod), mod - 2, mod)
        p = 1
        for i in range(a):
            p = (p * (n - i)) % mod
        return inv_af * p % mod
 
 
def blank(n, b, mod):
    inv_n = power(n, mod - 2, mod)
    Ans = combi(n, b, mod) ** 2 % mod
    Ans = (Ans * (n-b) * inv_n) % mod
    return Ans
 
 
def solve(n, k):
    global mod7
    Answer = 0
    if k < n - 1:
        for i in range(k + 1):
            Answer = (Answer + blank(n, i, mod7)) % mod7
 
    else:
        Answer = combi(2 * n - 1, n - 1, mod7)
    return Answer
 
 
print(solve(n, k))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
 
mod7 = 10 ** 9 + 7
 
 
def power(a, b, mod):
    p = 1
    q = a
    while b != 0:
        if b % 2 == 1:
            p = (p * q) % mod
        q = (q * q) % mod
        b = b // 2
    return p
 
 
def fact(n, mod):
    p = 1
    for i in range(1, n + 1):
        p = (p * i) % mod
    return p
 
 
def combi(n, a, mod):
    if a == 0:
        return 1
    else:
        inv_af = power(fact(a, mod), mod - 2, mod)
        p = 1
        for i in range(a):
            p = (p * (n - i)) % mod
        return inv_af * p % mod
 
 
def blank(n, b, mod):
    Ans = combi(n, b, mod) * combi(n - 1, b, mod) % mod
    return Ans
 
 
def solve(n, k):
    global mod7
    Answer = 0
    if k < n - 1:
        for i in range(k + 1):
            Answer = (Answer + blank(n, i, mod7)) % mod7
 
    else:
        Answer = combi(2 * n - 1, n - 1, mod7)
    return Answer
 
 
print(solve(n, k))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
all_l = []
fir_l = []
for i in range(n):
    fir_l.append(1)
all_l.append(fir_l)
for i in range(k):
    bef_len = len(all_l)
    for j in range(bef_len):
        bef_ope = all_l.pop(0)
        for l in range(n):
            if bef_ope[l] > 0:
                ope1 = list(bef_ope).copy()
                ope1[l] = bef_ope[l] - 1
                for m in range(n):
                    if l == m:
                        continue
                    else:
                        ope2 = ope1.copy()
                        ope2[m] = ope1[m] + 1
                        all_l.append(ope2)
    all_l = list(set(list(map(tuple, all_l))))
print(len(all_l)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
var_n,var_k = map(int,input().split())
all_list = []
first_inner_list = []
for i in range(var_n):
    first_inner_list.append(1)
all_list.append(first_inner_list)
for h in range(var_k):
    before_len = len(all_list)
    for i in range(before_len):
        before_ope = all_list.pop(0)
        for j in range(var_n):
            if before_ope[j] > 0:
                ope1 = before_ope.copy()
                ope1[j] = before_ope[j] - 1
                for k in range(var_n):
                    if j == k:
                        continue
                    else:
                        ope2 = ope1.copy()
                        ope2[k] = ope1[k] + 1
                        all_list.append(ope2)
    all_list = list(set(list(map(tuple, all_list))))
    for i in range(len(all_list)):
        element = list(all_list.pop(i))
        all_list.insert(i, element)
print(len(all_list)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7

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

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

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

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

print(len(all_list) % mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7

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

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

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

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

#print(len(all_list))
print(len(all_list) % mod)

Submission status: Time Limit Exceeded

Solution code:
MAX = 10 ** 5 * 2
mod = 10 ** 9 + 7
frac = [1]
for i in range(1,MAX + 1 ):
    frac.append( (frac[-1] * i) % mod )
def pow(a, n):
    if n == 0 : return  1
    elif n == 1 : return a
    tmp = pow(a, n//2)
    tmp = (tmp * tmp) % mod
    if n % 2 == 1 :
        tmp = (tmp * a) % mod
    return tmp
def inv(x):
    return pow(x, mod - 2 )
def comb(n, k):
    if k >= n or k < 0 : return 1
    return (frac[n] * inv(frac[n-k]) * inv(frac[k]))%mod
n,k = map(int,input().split())
count=0
for i in range(min(n,k+1)):
    count=(count+comb(n,i)*comb(n-1,n-1-i))%mod
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
MOD = 10 ** 9 + 7
from functools import reduce
def Comb(N, A):
    num = reduce(lambda x, y: x * y % MOD, range(N, N-A, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, A+1))
    return num * pow(den, MOD-2, MOD) % MOD
def resolve():
    n, k = lr()
    ans = Comb(2*n-1, n)
    if n-1 > k:
        for i in range(1, n-k):
            ans -= Comb(n, i)*Comb(n-1, n-i)
            ans %= MOD
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python


# @pysnooper.snoop()
def pow(n, m):
    # print(m)
    if m == 0:
        return 1
    if m % 2 == 0:
        return pow(n, int(m / 2))**2 % mod
    else:
        return pow(n, int((m - 1) / 2))**2 * n % mod


def conb(n, m):
    ret = factorial[n] * factorial_i[n - m] % mod
    ret = ret * factorial_i[m] % mod
    return ret


n, k = (int(val) for val in input().split())
mod = int(1e9 + 7)
factorial = [1]
factorial_i = [1]
fac = 1
fac_i = 1
for i in range(1, n + 1):
    fac = fac * i % mod
    # fac %= mod
    # fac_i = fac_i * pow(i, mod - 2) % mod
    factorial.append(fac)
    # factorial_i.append(fac_i)
    factorial_i.append(pow(fac, mod - 2))
print()
ans = 0
for i in range(min(k, n - 1) + 1):
    add = conb(n - 1, i) * conb(n, i) % mod
    ans += add
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python


# @pysnooper.snoop()
def pow(n, m):
    # print(m)
    if m == 0:
        return 1
    if m % 2 == 0:
        return pow(n, int(m / 2))**2 % mod
    else:
        return pow(n, int((m - 1) / 2))**2 * n % mod


def conb(n, m):
    ret = factorial[n] * factorial_i[n - m] % mod
    ret = ret * factorial_i[m] % mod
    return ret


n, k = (int(val) for val in input().split())
mod = int(1e9 + 7)
factorial = [1 for i in range(n + 1)]
factorial_i = [1 for i in range(n + 1)]
fac = 1
fac_i = 1
for i in range(n + 1):
    if i == 0:
        continue
    fac = fac * i % mod
    # fac %= mod
    fac_i = fac_i * pow(i, mod - 2) % mod
    factorial[i] = fac
    factorial_i[i] = fac_i
    # factorial.append(fac)
    # factorial_i.append(fac_i)
# print(factorial)
ans = 0
for i in range(min(k, n - 1) + 1):
    add = conb(n - 1, i) * conb(n, i) % mod
    ans += add
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python


# @pysnooper.snoop()
def pow(n, m):
    # print(m)
    if m == 0:
        return 1
    if m % 2 == 0:
        return pow(n, int(m / 2))**2 % mod
    else:
        return pow(n, int((m - 1) / 2))**2 * n % mod


def conb(n, m):
    ret = factorial[n] * factorial_i[n - m] % mod
    ret = ret * factorial_i[m] % mod
    return ret


n, k = (int(val) for val in input().split())
mod = int(1e9 + 7)
factorial = [1]
factorial_i = [1]
fac = 1
fac_i = 1
for i in range(1, n + 1):
    fac *= i
    fac %= mod
    fac_i *= pow(i, mod - 2)
    fac_i %= mod
    factorial.append(fac)
    factorial_i.append(fac_i)

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
import numpy as np
MOD = 10 ** 9 + 7


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


def make_fact_and_inv(U, mod=MOD):
    """
    0~Nまでのサイズ(N+1)の階乗およびその逆元の配列を返す
    """
    tmp = np.arange(U, dtype=np.int64)
    tmp[0] = 1
    fact = cumprod(tmp, mod)
    tmp = np.arange(U, 0, -1, dtype=np.int64)
    tmp[0] = pow(int(fact[-1]), mod - 2, mod)
    inv = cumprod(tmp, mod)[::-1]
    return fact, inv


fact, inv = make_fact_and_inv(2 * 10 ** 6)


def nCr(n, r, mod=MOD):
    if r < 0 or r > n or n < 0:
        return 0
    return fact[n] * inv[r] % mod * inv[n - r] % mod


if __name__ == "__main__":
    N, K = map(int, input().split())

    ans = []
    for i in range(min(N - 1, K) + 1):
        val = nCr(N, i) * nCr(N - 1, i) % MOD
        ans.append(val)

    answer = 0
    while ans:
        answer = (answer + ans.pop()) % MOD
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
x=input().split()
n=int(x[0])
k=int(x[1])
def fast_expo(b,n,p):
    if n==0:
        return 1
    if n==1:
        return b%p
    if n%2==0:
        return fast_expo(((b%p)*(b%p))%p,n//2,p)
    else:
        return (b*fast_expo(((b%p)*(b%p))%p,n//2,p))%p
def combi(n,p):
    X=1
    Y=1
    Z=[1]*(n+1)
    for i in range(n):
        X=(X*(n-i))%p
        Y=(Y*(i+1))%p
        Z[i+1]=(X*fast_expo(Y,p-2,p))%p
    return Z 

p=10**9+7
s=0
L=min(n,k+1)
Z1=combi(n,p)
Z2=combi(n-1,p)
for i in range(L):
  s=(s+(Z1[i]*Z2[i])%p)%p
print(s)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD=1000000007

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

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

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

print(ret)

Submission status: Time Limit Exceeded

Solution code:
def nCa(n,a,mod=10**9+7):
  p=q=1
  for i in range(a):
    p = p*(n-i)%mod
    q = q*(i+1)%mod
  return p*pow(q,mod-2,mod) %mod

def main():
  mod = 10**9+7
  n,k = map(int,input().split())
  
  ans = 1
  for i in range(1,min(k+1,n)):
    ans = (ans + nCa(n,i)*nCa(n-1,n-i-1)) % mod 
  
  print(ans)

if __name__ == '__main__':
  main()

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(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:
n, k =map(int, input().split())
mod = 10**9 + 7
def power(a,r,z):

    if r == 0:
        return 1
    c = power(a,r//2,z)
    c = (c*c) %z
    if r%2 ==1:
        c = c *a
    
    return c

def Con(n,r,z):
    x = 1
    y = 1
    for i in range(min(n-r,r)):
        x = (x *(n-i)) %z
        y = (y *(min(n-r,r)-i)) %z
    return (x * power(y,z-2,z)) %z

def H(n,m,z):
    return Con(n+m-1,n-1,z)

if k >=n:
    print(H(n,n,mod))
else:
    ans = 0
    for i in range(0,k+1): # i =　０の部屋の数
        ans += Con(n,i,mod)*H(n-i,i,mod) %mod
    ans %= mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
x=input().split()
n=int(x[0])
k=int(x[1])

def fast_expo(b,n,p):
    if n==0:
        return 1
    if n==1:
        return b%p
    if n%2==0:
        return fast_expo(((b%p)*(b%p))%p,n//2,p)
    else:
        return (b*fast_expo(((b%p)*(b%p))%p,n//2,p))%p
def combi(n,k,p):
    X=1
    Y=1
    for i in range(k):
        X=(X*(n-i))%p
        Y=(Y*(k-i))%p
    Z=fast_expo(Y,p-2,p)
    return (X*Z)%p

p=10**9+7
s=0
L=min(n,k+1)
for i in range(L):
  s=(s+(combi(n,i,p)*combi(n-1,i,p))%p)%p
print(s)

Submission status: Time Limit Exceeded

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

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

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

if n <= k-1:
    print(cmb(2*n-1, n))
else:
    answer = 0
    for m in range(k+1):
        answer += cmb(n, m)*cmb(n-1, m) % mod
        answer %= mod
    print(answer)