Problem:


Score : 600 points

Problem Statement

Find the number of sequences of length K consisting of positive integers such that the product of any two adjacent elements is at most N, modulo 10^9+7.

Constraints

1\leq N\leq 10^9

1 2\leq K\leq 100 (fixed at 21:33 JST)

N and K are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

Print the number of sequences, modulo 10^9+7.

Sample Input 1

3 2

Sample Output 1

5

(1,1), (1,2), (1,3), (2,1), and (3,1) satisfy the condition.

Sample Input 2

10 3

Sample Output 2

147

Sample Input 3

314159265 35

Sample Output 3

457397712



Sample input:
3 2


Sample output:
5

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


import numpy as np

n, k = LI()
sqt = int(n ** 0.5)
dp_mul_num = [1] * sqt + [n // i - n // (i + 1) for i in range(1, n // sqt)][::-1]
group_num = len(dp_mul_num)
dp = [[0] * group_num for _ in range(k)]
dp[0] = dp_mul_num





for i in range(k - 1):
    ret = 0
    for j in range(group_num):
        ret = (ret + dp[i][j]) % mod
        dp[i + 1][group_num - j - 1] = ret * dp_mul_num[group_num - j - 1] % mod











print(sum(dp[-1]) % mod)

Submission status: Runtime Error

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

L = [N]
c = 2
while c < N**0.5:
    if L[-1] != N//c:
        L.append(N//c)
    c += 1
if c > N**0.5:
    c -= 1
    L.append(c)
else:
    L.append(c)


L.reverse()
dp = [[0 for j in range(c+len(L))] for i in range(K+1)]

for j in range(1, c+1):
    dp[2][j] = N//j
for j in range(1, len(L)):
    dp[2][j+c] = N//L[j]*(L[j]-L[j-1])

for i in range(2, K):
    dp[i+1][1] = sum(dp[i])
    for j in range(2, c+len(L)):
        dp[i+1][j] = dp[i+1][j-1]-dp[i][len(dp[0])+1-j]
        if j > c:
            dp[i+1][j] *= (L[j]-L[j-1])
#    for j in range(1, len(L)):
#        dp[i+1][j+c] *= (L[j]-L[j-1])
        

print(sum(dp[K])%(10**9+7))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
md=10**9+7
a=[0]*n
for i in range(1,n+1):
    a[i-1]=n//i
#print(a)
ans=a[:]
for _ in range(k-2):
    ans=[sum(ans[:ak])%md for ak in a]
#    print(ans)
print(sum(ans)%md)

Submission status: Runtime Error

Solution code:
# using main() makes code faster from the point of view of "access to variables in global name-space"
# def main():

""" convenient functions
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
# accumulate() returns iterator! to get list: list(accumulate())
from math import factorial, ceil, floor
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    # TODO: How should I do when n - r is negative?
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    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
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from operator import itemgetter
# ex1: List.sort(key=itemgetter(1))
# ex2: sorted(tuples, key=itemgetter(1,2))
from functools import reduce
def chmin(x, y):
    """change minimum
    if x > y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current minimum value
        y (long): potential minimum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x > y:
        x = y
        return (x, True)
    else:
        return (x, False)
def chmax(x, y):
    """change maximum
    if x < y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current maximum value
        y (long): potential maximum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x < y:
        x = y
        return (x, True)
    else:
        return (x, False)

from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

""" initialize variables and set inputs
# initialize variables
    # to initialize list, use [0] * n
    # to initialize two dimentional array, use [[0] * N for _ in range(N)]
# set inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
# preprocessing
    # transpose = [x for x in zip(*data)]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
    # flat = [flatten for inner in data for flatten in inner]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
# calculate and output
    # output pattern
    # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
"""

# functions used
r = lambda: sys.stdin.readline().strip()
r_int = lambda: int(r())
R = lambda: list(map(int, r().split()))
Rfloat = lambda: list(map(float, r().split()))
Rtuple = lambda: tuple(map(int, r().split()))
Rmap = lambda: map(int, r().split())

""" how to treat input
# single int: int(r())
# single string: r()
# single float: float(r())
# line int: R()
# line string: r().split()
# line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
# lines int: [R() for _ in range(n)]
"""

# for test
# sys.stdin = open('sample.txt') 

# ----------------------------------
# main
N, K = R()

dvd = [0] * N
dvd_cnt = [0] * N
count = -1
# define group
for i in range(1, N+1):
    if dvd[count] != N // i:
        count += 1
        dvd[count] = N // i        
    dvd_cnt[count] += 1
else:
    dvd = dvd[:count+1]
    dvd_cnt = dvd_cnt[:count+1]
    acc_cnt = list(accumulate(dvd_cnt))
    dvdlen = count+1
    dvd_prod = [0] * dvdlen

for i in range(dvdlen):
    count = 0
    target = dvd[i]
    for j in range(dvdlen):
        if target * dvd[dvdlen-1-j] <= N:
            count += 1
        else:
            dvd_prod[i] = count
            break
    else:
        dvd_prod[i] = count

dp = [[0] * K for _ in range(dvdlen)]
for j in range(dvdlen):
    dp[j][0] = dvd_cnt[j]
    
for j in range(1, K):
    for i in range(dvdlen):
        for k in range(dvd_prod[dvdlen-1-i]):
            dp[i][j] += dp[k][j-1]
        else:
            dp[i][j] *= dvd_cnt[i]
            dp[i][j] %= MOD
print(sum([dp[i][K-1] for i in range(dvdlen)]) % MOD)

# end of main
# ----------------------------------

"""memo: how to use defaultdict of list
# initialize
Dic = defaultdict(list)
# append / extend
Dic[x].append(y)
# for
for k, v in Dic.items():
"""

# if __name__ == '__main__':
#     main()

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7


def main():
  N, K = map(int, input().strip().split())
  dp1 = {}
  dp2 = {}

  counter = {}
  i = 1
  while i < N:
    v = N // i
    j = N // v
    counter[v] = j - i + 1
    i += j - i + 1

  keys = sorted(counter.items(), reverse=True)

  total = 0
  for nj, v in keys:
    total += v
    dp1[nj] = total

  for i in range(2, K + 1):
    dp2 = {}
    # dp[i] = {}
    total = 0
    for nj, w in keys:
      j = N // nj
      v = dp1[j] * w
      total += v
      total %= MOD
      dp2[nj] = total

    dp1 = dp2

  return dp2[1]
  # for k, v in dp.items():
  #   print(k, sorted(v.items(), reverse=True))

  # return dp[K][1]


if __name__ == '__main__':
  print(main())

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  # type: int

def solve(N: int, K: int):
    ns = []
    for i in range(1, N):
        if N < i * i:
            break
        ns.append(i)
        ns.append(N // i)
    ns = sorted(list(set(ns)))

    m = {n: i for i, n in enumerate(ns)}
    l = [1] * len(ns)
    for i, (s, b) in enumerate(zip(ns, ns[1:])):
        l[i] = (N // s) - (N // b)
    l[len(ns) - 1] = 1

    dp = [[0] * len(ns) for _ in range(K+1)]
    dp[0][m[N]] = 1

    for i in range(K):
        for j in range(len(ns) - 2, -1, -1):
            dp[i][j] += dp[i][j + 1]
        for j, nn in enumerate(ns):
            nj = m[N // nn]
            dp[i+1][j] = (dp[i+1][j] + dp[i][nj] * l[j]) % MOD

    return sum(dp[-1]) % MOD


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    result = solve(N, K)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def hersCode(l, r, n, N):
  ok = l
  ng = r + 1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if mid * n <= N:
      ok = mid
    else:
      ng = mid
  return ng


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

L = []
t = 1
n = N
while t < N:
  L.append(t)
  t = hersCode(t, N, N // t ,N)

D = [0] * len(L)
L.append(N + 1)
for i in range(len(L) - 1):
  D[i] = (L[i + 1] - L[i]) % MOD

DP = [[0] * (len(D)) for _ in range(K)]
for i in range(len(D)):
  DP[0][i] = D[i]

for i in range(1, K):
  S = [0] * len(D)
  S[0] = DP[i - 1][0]
  for j in range(1, len(D)):
    S[j] = S[j - 1] + DP[i - 1][j]
  for j in range(len(D)):
    DP[i][j] = S[-1 -j] * D[j] % MOD

print(sum(DP[K - 1]) % MOD)

Submission status: Runtime Error

Solution code:
Q = 10**9+7
from collections import deque
from itertools import accumulate
#import sys
#input = sys.stdin.readline
def main():
    N, K = map( int, input().split())
    ans = 0
    d = deque()
    e = deque()
    M = int(N**(1/2))*2
    for i in range(1, int(N**(1/2))+1):
        if i**2 == N:
            d.append(i)
            M -= 1
            continue
        d.append(i)
        e.appendleft(N//i)
    T = list(d+e)
    CT = [1]*M
    for i in range(1,M):
        CT[i] = T[i] - T[i-1]
    accT = list( map(lambda x:x%Q, accumulate(CT) ))
    dp = [[0]*M for _ in range(K)]
    for i in range(M):
        dp[1][i] = accT[-i-1]*CT[i]%Q
    for k in range(1, K-1):
        accT[0] = dp[k][0]
        for i in range(M-1):
            accT[i+1] = (accT[i]+dp[k][i+1])%Q
        for i in range(M):
            dp[k+1][i] = accT[-i-1]*CT[i]%Q
    print(sum(dp[K-1])%Q)
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

# guchoku case

# dp = [[0 for _ in range(N+1)] for _ in range(K+1)]

# for i in range(N+1):
#     dp[1][i] = 1
# for i in range(K):
#     for j in range(1,N+1):
#         for k in range(1, N // j + 1):
#             dp[i+1][j] += dp[i][k]
#             dp[i+1][j] %= MOD

JN = [0]  # N//j table
j = 1
while j*j<N:
    if j not in JN:
        JN.append(j)
    if N//j not in JN:
        JN.append(N//j)
    j += 1

JN.sort()
PJN = {JN[i]: JN[i-1] for i in range(1, len(JN))}  # prev jn

dp = [{0: 0} for _ in range(K)]
cdp = [{0: 0} for _ in range(K)]
w = dict()

# init dp
prv = 0
for i, jn in enumerate(JN):
    dp[0][jn] = 1
    w[jn] = jn - prv
    cdp[0][jn] = jn
    prv = JN[i]

for i in range(K-1):
    for jn in JN[1:]:
        dp[i+1][jn] = cdp[i][N//jn]
        dp[i+1][jn] %= MOD
        cdp[i+1][jn] = cdp[i+1][PJN[jn]] + dp[i+1][jn] * w[jn]
        cdp[i+1][jn] %= MOD

print(cdp[-1][N])

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define N 32768
#define M 0x3B9ACA07LL
long long a[N]={},b[N],c[N]={},d[N];
#define REP(i,n)for(int i=0;i<n;i++)
int main(){
int n,k; std::cin>>n>>k;
for(int i=1;i<N;i++)a[i]=std::min(i,n),b[i]=n/i;
REP(j,k-1){
for(int i=1;i<N;i++)c[i]=(c[i-1]+b[i])%M;
d[N-1]=c[n/(N-1)];
for(int i=N-2;i>=1;i--)d[i]=(d[i+1]+a[i]*(n/i-n/(i+1)))%M;
std::swap(a,c);
std::swap(b,d);
}
std::cout<<b[1];
}

Submission status: Runtime Error

Solution code:
from itertools import accumulate as ac
N,K=map(int,input().split())
n=int(N**0.5)
mod=10**9+7
list_a=[1]*n
list_b=[N//j-N//(j+1) for j in range(1,N_s)]+[(N//n-n)]
list_p=[p for p in list_b]
list_aa=list(ac(list_a))
list_bb=list(reversed(list(ac(reversed(list_b)))))

for i in range(K-1):
    temp=sum(list_a)
    list_a=[(temp+list_bb[j])%mod for j in range(n)]
    list_b=[(list_p[j]*list_aa[j])%mod for j in range(n)]
    list_aa=list(ac(list_a))
    list_bb=list(reversed(list(ac(reversed(list_b)))))
    
print((sum(list_a+list_b))%mod)

Submission status: Runtime Error

Solution code:
from itertools import accumulate as ac
N,K=map(int,input().split())
n=int(N**0.5)
mod=10**9+7
list_a=[1]*N_s
list_b=[N//j-N//(j+1) for j in range(1,N_s)]+[(N//n-n)]
list_p=[p for p in list_b]
list_aa=list(ac(list_a))
list_bb=list(reversed(list(ac(reversed(list_b)))))

for i in range(K-1):
    temp=sum(list_a)
    list_a=[(temp+list_bb[j])%mod for j in range(n)]
    list_b=[(list_p[j]*list_aa[j])%mod for j in range(n)]
    list_aa=list(ac(list_a))
    list_bb=list(reversed(list(ac(reversed(list_b)))))
    
print((sum(list_a+list_b))%mod)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
mod=10**9+7
Layer=[]
a=1
b=1
while(b<N):
    a=b
    b=N//(N//a)+1
    Layer.append((a,b))
#print(Layer)
L=[N//x[0] for x in Layer]
num=[x[1]-x[0] for x in Layer]
M=len(Layer)
#print(num)
dp=[[0 for j in range(M)] for i in range(K+1)]
dp[0][0]=1
sdp=[0 for i in range(M+1)]
for i in range(K):
    for j in range(M):
        sdp[j+1]=(dp[i][j]+sdp[j])%mod
    for j in range(M):
        dp[i+1][j]=(sdp[M-j]*num[j])%mod
ans=0
for j in range(M):
    ans+=dp[K][j]
    ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
n,k = [int(x) for x in input().split()]
if n == 1:
    print(1)
    quit()
f = [0,n]
i = 1
while f[i] >= i:
    i += 1
    f.append(n//i)
s = [0]*len(f)
for i in range(1,len(f)):
    s[i] = 1
for i in range(2,len(f))[::-1]:
    if f[i] <= i:
        s[-1] = f[i-1]-f[i]
    else:
        s.append(f[i-1]-f[i])
MA = len(s)
dp = [[0]*MA for i in range(k)]
dp[0] = [s[i] for i in range(MA)]
for i in range(MA-1):
    dp[0][i+1] += dp[0][i]
    dp[0][i+1] %= mod
for l in range(k-1):
    for i in range(1,MA):
        j = MA-i
        dp[l+1][i] += dp[l][j]*s[i]
        dp[l+1][i] %= mod
        dp[l+1][i] += dp[l+1][i-1]
        dp[l+1][i] %= mod
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
n,k = LI()
if n == 1:
    print(1)
    quit()
f = [0,n]
i = 1
while f[i] >= i:
    i += 1
    f.append(n//i)
s = [0]*len(f)
for i in range(1,len(f)):
    s[i] = 1
for i in range(2,len(f))[::-1]:
    if f[i] <= i:
        s[-1] = f[i-1]-f[i]
    else:
        s.append(f[i-1]-f[i])
MA = len(s)
dp = [[0]*MA for i in range(k)]
dp[0] = [s[i] for i in range(MA)]
for i in range(MA-1):
    dp[0][i+1] += dp[0][i]
    dp[0][i+1] %= mod
for l in range(k-1):
    for i in range(1,MA):
        j = MA-i
        dp[l+1][i] += dp[l][j]*s[i]
        dp[l+1][i] %= mod
        dp[l+1][i] += dp[l+1][i-1]
        dp[l+1][i] %= mod
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

N, K = map(int, input().strip().split(' '))
div = 1000000000 + 7

coefficients = [1] * N
nums = [N // i for i in range(1, N + 1)]
for i in range(1, K - 1):
    mirror = coefficients[:]
    for index in range(N):
        coefficients[index] = sum(e for e in mirror[:N//(index+1)])
print(sum(c * n for c, n in zip(coefficients, nums)))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
N, K = list(map(int, input().split()))
max_i = min(K, N - K + 1)

MAX = max_i * 2
PRIME = 10 ** 9 + 7

fac = [0] * MAX
finv = [0] * MAX


def invMod(a, m):
    a %= m
    b, x, y = m, 1, 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        x -= t * y
        x, y = y, x
    return x % m


def binomInit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, MAX):
        fac[i] = (fac[i - 1] * i) % PRIME
        finv[i] = (finv[i - 1] * invMod(i, PRIME)) % PRIME
        

def binom(n, k):
    if n < 0 or k < 0 or n < k:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % PRIME


binomInit()
    

for i in range(1, max_i + 1):
    blue_part = binom(K - 1, i - 1)
    red_part = binom(N - K + 1, i)
    print((blue_part * red_part) % PRIME)

Submission status: Runtime Error

Solution code:
if n == 1:
    print(1)
    exit()
mod = 10 ** 9 + 7
now = n
big = []
for i in range(2,int(math.sqrt(n)+2)):
    d = n // i
    big.append(now - d)
    now = d
big.reverse()
l = [1] * d + big
l2 = [1] * d + big
for i in range(k-1):
    a = cumsum(l)
    a.reverse()
    count = 0
    for i,j in zip(a,l2):
        l[count] = (i * j) % mod
        count += 1
l = cumsum(l)
ans = l[-1] % mod
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    N, K = map(int, input().split())
    def r(C, D):
        newD = {}
        for key in D.keys():
            for n in range(1, N + 1):
                if int(key) * n <= N:
                    if key in newD:
                        newD[key] = D[key]
                    else:
                        newD[key] = newD[key] + D[key]
        if C == K:
            return newD
        else:
            r(C + 1, D)
    C, D = 1, {} # count, dict
    for n in range(1, N + 1):
        D[str(n)] = 1
    newD = r(C, D)
    return sum(newD.values()) % (10 ** 9 + 7)

print(main())

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
p = 10**9 +7
dp = [[0]*(n+1) for _ in range(3)]
for i in range(1,k+1):
  for j in range(1,n+1):
    if i == 1:
      dp[1][j] = j
    else:
      dp[2][j] = dp[2][j-1] + dp[1][n//j]
      dp[2][j] %= p
  if i != 1:
    for _ in range(1,n+1):
      dp[1][_] = dp[2][_]
    
#print(dp)
print(dp[2][n] % p)

Submission status: Runtime Error

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

def num(N, K, i):
    if K == 2:
        return (N // i) % (10**9 + 7)
    else:
        ans = 0
        for j in range(1, N//i):
            ans += num(N, K-1, j)
        return ans % (10**9 + 7)

ans = 0
for i in range(N):
    ans += num(N, K, i)

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

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
Const = []
pc = N
for i in range(1, 3200):
    c = N//i
    if pc>i-1:
        Const.append(pc - c)
    if i*i>N:
        sqrtN = i-1
        break
    pc = c
#if sqrtN*sqrtN!=N:
#    Const[-1] -= 1

len_dp = sqrtN + len(Const)
dp = [[0]*(len_dp) for _ in range(K)]
dp0 = dp[0]


for i in range(1, sqrtN+1):
    dp0[i] = 1
    if i<len(Const):
        dp0[-i] = Const[i]

cum_dp0 = []
c = 0
for v in dp0:
    c += v
    cum_dp0.append(c)
mod = 10**9+7
dp_old = cum_dp0
for _ in range(K-1):
    print(dp_old)
    dp = [0]*(2*sqrtN+2)
    for i in range(1,len_dp):
        dp[i] = dp_old[-i] + dp[i-1] % mod
        if i > sqrtN:
            dp[i] *= Const[-(i-sqrtN)]
            print(Const[-(i-sqrtN)])
            dp[i] %= mod
    dp_old = dp
print(dp)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

N, K = map(int, input().strip().split(' '))
div = 1000000000 + 7

coefficients = [1] * N
nums = [N // i for i in range(1, N+1)]
for i in range(1, K - 1):
    mirror = [c for c in coefficients][::-1]
    for index in range(N):
        coefficients[index] += sum(e for e in mirror[index:-1])
print(sum(c * n for c, n in zip(coefficients, nums)))

Submission status: Runtime Error

Solution code:
import copy
n,k=map(int,input().split())
mod=10**9+7
def f(i):
  return n//i
ans=[1]*n
ans_c=[1]*n
for _ in range(k-1):
  for i in range(1,n+1):
    for j in range(1,f(i)+1):
      ans_c[j-1]+=ans[i-1]*f(i)
  ans=copy.copy(ans)
      
print(sum(ans)%mod)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
P = 10**9+7
X = [0] + [1] * N
for i in range(1, K+1):
    NX = [0] * (N+1)
    for j in range(1, N+1):
        NX[j] = (NX[j-1] + X[N//j]) % P
    X = NX
print(X[-1])

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
LARGE = 10 ** 9 + 7

# SQRT
R = 1
while (R + 1) ** 2 < N:
    R += 1

square = False
if (R + 1) ** 2 == N:
    square = True


DP_S = [1] * R
DP_L = [1] * R
N_L = [1] * R
DP_M = 0
L = R
if square:
    DP_M = 1
    L += 1


for i in range(R, -1, 0):
    Q = N // i
    DP_L[i - 1] = Q - L
    N_L[i - 1] = Q - L
    L = Q

for _ in range(K - 1):
    S = 0
    L = sum(DP_L) + DP_M
    SS = sum(DP_S)
    for i in range(R):
        DP_L[i] = S * N_L[i] % LARGE
        DP_S[i] = L + SS % LARGE
        S = (S + DP_S[i]) % LARGE
        L = (L - DP_L[i]) % LARGE

        if square:
            DP_M = (DP_M + SS) % LARGE

print((sum(DP_L) + sum(DP_S) + DP_M) % LARGE)

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
    S=input()
    T=input()

def inputList():
    a=list(map(int,input().split()))
    return a

def multisort(li,index):
    return sorted(li,key=lambda x: x[index])

if(__name__=='__main__'):
    main()

Submission status: Runtime Error

Solution code:
def main():
    N, K = map(int, input().split())
    def r(C, D):
        newD = {}
        for key in D.keys():
            for n in range(1, N + 1):
                if int(key) * n <= N:
                    if key in newD:
                        newD[key] = D[key]
                    else:
                        newD[key] = newD[key] + D[key]
        if C == 10:
            return newD
        else:
            r(C + 1, D)
    C, D = 1, {} # count, dict
    for n in range(1, N + 1):
        D[str(n)] = 1
    newD = r(C, D)
    return sum(newD.values()) % (10 ** 9 + 7)

print(main())

Submission status: Runtime Error

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

X = [0] + [1] * N
for i in range(1, K+1):
    NX = [0] * (N+1)
    for j in range(1, N+1):
        NX[j] = NX[j-1] + X[N//j]
    X = NX
print(X[-1])

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = S()
    d = defaultdict(int)
    for i in s:
        d[i] += 1
    for i in d.keys():
        if d[i] != 2:
            print("No")
            quit()
    print("Yes")
    return

#B
def B():
    n = I()
    p = LI()
    ans = 0
    for i in range(1,n-1):
        k = p[i-1:i+2]
        k.sort()
        if k[1] == p[i]:
            ans += 1
    print(ans)
    return

#C
def C():
    n = I()
    d = LI()
    d.sort()
    print(d[n//2]-d[n//2-1])
    return

#D
def D():
    n,k = LI()
    fact = [1]*100001
    for i in range(1,100001):
        fact[i] = fact[i-1]*i%mod
    inv = [1]*100001
    inv[-1] = pow(fact[-1],mod-2,mod)
    for i in range(1,100001)[::-1]:
        inv[i-1] = inv[i]*i%mod

    for i in range(1,k+1):
        if n-k+1 < i:
            print(0)
        else:
            ans = fact[n-k+1]*inv[i]*inv[n-k+1-i]%mod
            ans *= fact[k-1]*inv[k-i]*inv[i-1]%mod
            ans %= mod
            print(ans)
    return

#E
def E():
    ma = 100000000
    def dijkstra(s):
        d = defaultdict(lambda : ma)
        q = [(0,s,0)]
        d[(s,0)] = 0
        while q:
            dx,x,t = heappop(q)
            t = (t+1)%3
            k = t == 1
            for y in v[x]:
                if dx+k < d[(y,t)]:
                    d[(y,t)] = dx+k
                    heappush(q,(d[(y,t)],y,t))
        res = d[(g,0)]
        if res == ma:
            res = -1
        return res

    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
    s,g = LI()
    s -= 1
    g -= 1
    print(dijkstra(s))
    return

#F
def F():
    n,k = LI()
    MA = math.ceil(n**0.5)
    MA2 = 2*MA
    f = [n//i if i > 0 else 0 for i in range(MA+1)]
    if f[MA] <= MA:
        MA2 -= 1
    if f[MA-1] <= MA-1:
        MA2 -= 1
    dp = [[0]*(MA2) for i in range(k)]
    for i in range(MA+1):
        dp[0][i] = 1
    j = MA2-1
    for i in range(1,MA):
        dp[0][j] = f[i]-f[i+1]
        j -= 1
    dp[0][0] = 0
    if f[MA] <= MA:
        MA -= 1
    if f[MA] <= MA:
        MA -= 1
    s = [dp[0][i] for i in range(MA2)]
    for i in range(MA2-1):
        dp[0][i+1] += dp[0][i]
        dp[0][i+1] %= mod
    for l in range(k-1):
        for i in range(1,MA2):
            j = MA2-i
            dp[l+1][i] = dp[l][j]*s[i]
            dp[l+1][i] %= mod
            dp[l+1][i] += dp[l+1][i-1]
            dp[l+1][i] %= mod
    print(dp[-1][-1])
    return


#Solve
if __name__ == "__main__":
    F()