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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N, K = map(int, input().split())
MOD = 10**9 + 7

U = [0]; V = []
for x in range(1, int(N**.5)+1):
    U.append(x)
    if x < N//x:
        V.append(N//x)
V.reverse(); U.extend(V)

L = len(U)
S = [1]*L
S[0] = 0
for k in range(K-1, -1, -1):
    T = [0]*L
    r = 0
    for i in range(1, L):
        x = U[i-1]; y = U[i]
        T[i] = r = ((y - x) * S[L-i] + r) % MOD
    S = T
print(S[-1])

Solution (Python):

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


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


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


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


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


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


def F():
    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])
    return



if __name__ == "__main__":
    F()

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


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, 0, -1):
    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):
        S = (S + DP_S[i]) % LARGE
        DP_S[i] = (L + SS) % LARGE
        L = (L - DP_L[i]) % LARGE
        DP_L[i] = (S * N_L[i]) % LARGE

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

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

Solution (Python):


MOD = 10**9+7

from math import sqrt, floor

n,k = [int(i) for i in input().split()]
sn = floor(sqrt(n))+1

pre = [0]*sn
pre[1] = 1

cur = [1]*(sn)
cur[0] = 0



for _ in range(k-1):

    new = [sum(cur)%MOD]*(sn); new[0] = 0
    s = sum(pre)%MOD
    b=0
    res=0
    for j in range(sn-1,0,-1):
        a = n//j - (sn-1) 
        res += (a-b)*s
        res %=MOD
        new[j] += res
        if new[j] > MOD: new[j] -= MOD
        s -= pre[j]
        b=a
        
    pre,cur = cur,new



ans =0
for j in range(sn-1,0,-1):
    ans += pre[j]*(n//j - (sn-1))
    ans %=MOD


print((sum(cur)+ans)%MOD)

Solution (Python):
import math

from itertools import accumulate

def cumsum(a):
    return list(accumulate(a))

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

Solution (Python):
from math import sqrt
inpl = lambda: list(map(int,input().split()))
MOD = 10**9 + 7
N, K = inpl()
sqN = int(sqrt(N))
bound = [0]*(sqN+2)
for i in range(1,sqN+2):
    bound[i] = N//i
bound[sqN+1] = sqN
group_size = [0]*(sqN+1)
for i in range(1,sqN+1):
    group_size[i] = bound[i]-bound[i+1]

cur_small = [1] * (sqN+1)
cur_small[0] = 0
cur_large = [ s for s in group_size ]
for k in range(K-1):
    prev_small = cur_small
    cur_small = [0] * (sqN+2)
    prev_large = cur_large
    cur_small = [0] * (sqN+2)
    cur_small[sqN+1] = sum(prev_small[:sqN+1])
    for n in range(sqN,0,-1):
        cur_small[n] = (prev_large[n] + cur_small[n+1]) % MOD
    acc_prev_small = 0
    for n in range(1,sqN+1):
        acc_prev_small += prev_small[n]
        cur_large[n] = acc_prev_small*group_size[n] % MOD

print((sum(cur_small[:sqN+1])+sum(cur_large[:sqN+1]))%MOD)

Solution (Python):
import math
N, K = map(int, (input().split()))

mod = 10**9 + 7

ans_array = []
divide_max = N
divide_count = []

for i in range(2, math.floor(math.sqrt(N)) + 2):
    divide = math.floor(N / i)
    ans_array.append(divide_max - divide)
    divide_count.append(divide_max - divide)
    divide_max = divide

for i in range(divide):
    ans_array.append(1)
ans_array = ans_array[::-1]

ans_length = len(ans_array)
ans_acc = [0] * ans_length

for k in range(2, K + 1):
    ans_acc[0] = ans_array[0]
    for i in range(1, ans_length):
        ans_acc[i] = (ans_acc[i - 1] + ans_array[i]) % mod
    
    
    for i in range(divide):
        ans_array[i] = ans_acc[ans_length - i - 1]
    for i in range(divide, ans_length):
        ans_array[i] = ans_acc[ans_length - i - 1] * divide_count[
            ans_length - 1 - i] % mod

ans_acc[0] = ans_array[0]
for i in range(1, ans_length):
    ans_acc[i] = (ans_acc[i - 1] + ans_array[i]) % mod

print(ans_acc[-1])

Solution (Python):
n,k=map(int,input().split())
a=int(n**0.5)
mod=10**9+7
l=[0]*(a+1)
for i in range(a,0,-1):
    l[i]=i
    l.append(n//i)
for i in range(1,2*a+1):
    l[-i]=l[-i]-l[-i-1]
dp=[l]+[[0]*(2*a+1) for i in range(k-1)]
for i in range(1,k):
    t=0
    for j in range(1,2*a+1):
        t+=dp[i-1][j]
        t%=mod
        dp[i][-j]=t*l[-j]%mod
ans=0
for i in dp[-1][1:]:
    ans+=i
    ans%=mod
print(ans)

Solution (Python):
import sys
import math

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n, k = na()
mod = 1000000007

s = int(math.sqrt(n))
dp = [1] * (n//s+1)
ep = [0] * s
dp[0] = 0

for i in range(1,s):
    ep[i] = 1 

for z in range(k-1):
    ndp = [0] * (n//s+1)
    nep = [0] * s

    for i in range(1,n//s+1):
        if i < s:
            nep[i] += dp[i]
        else:
            ndp[n//i] += dp[i]
    for i in range(1,s):
        ndp[i] += ep[i] * (n//i-n//(i+1))
        ndp[i] %= mod
    for i in range(2, s):
        nep[i] += nep[i-1]
        if nep[i] >= mod:
            nep[i] -= mod
    ndp[n//s] += nep[-1]
    ndp[n//s] %= mod
    for i in range(n//s-1, 0, -1):
        ndp[i] += ndp[i+1]
        if ndp[i] >= mod:
            ndp[i] -= mod
    dp, ep = ndp, nep

ans = sum(dp)
for i in range(1, s):
    ans += ep[i] * (n//i-n//(i+1))
print(ans%mod)

Solution (Python):
import numpy as np
N,K = map(int,input().split())
MOD = 10 ** 9 + 7
M = int(N**.5)


upper_cnt = np.zeros(M+1, dtype=np.int64)
a = np.arange(M+1, dtype=np.int64)
upper_cnt[1:] = N // a[1:] - np.maximum(M, N // (a[1:]+1))



lower = np.zeros(M+1, dtype=np.int64)
upper = np.zeros(M+1, dtype=np.int64)

lower[1] = 1
for k in range(1,K+1):
    prev_lower = lower
    prev_upper = upper
    cum_lower = prev_lower.cumsum() % MOD
    cum_upper = prev_upper.cumsum() % MOD
    
    lower = np.zeros(M+1, dtype=np.int64)
    lower += (cum_lower[-1] + cum_upper[-1])
    lower[1:] -= cum_upper[:-1] 
    lower[0] = 0
    
    
    upper = cum_lower * upper_cnt
    lower %= MOD
    upper %= MOD
    
answer = (lower.sum() + upper.sum()) % MOD
print(answer)