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-----
3 2

-----Sample Output-----
5

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

Difficulty: interview

Starter code:

Solutions:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N, K = lr()
M = int(N**.5)

# M+1以上で、Nを割るとxになるもの
upper_cnt = np.zeros(M+1, dtype=np.int64) # 1-indexed
A = np.arange(M+1, dtype=np.int64)
upper_cnt[1:] = N // A[1:] - np.maximum(M, N // (A[1:]+1)) # Mの時はlowerで数えるので0に

# 桁DP
lower = np.zeros(M+1, dtype=np.int64) # 1-indexed
upper = np.zeros(M+1, dtype=np.int64)
#最初は制限なしなので1を置いておく
lower[1] = 1
for i in range(K):
    prev_lower = lower.copy()
    prev_upper = upper.copy()
    lower_cum = prev_lower.cumsum() % MOD
    upper_cum = prev_upper.cumsum() % MOD
    # lower と upper から lower へ
    lower = np.zeros(M+1, dtype=np.int64)
    lower[1:] += (lower_cum[-1] + upper_cum[-1])
    lower[1:] -= upper_cum[:-1] # 大きすぎる値を引く
    # upper から upper はなし
    # lower から upper へ
    upper = lower_cum * upper_cnt
    lower %= MOD; upper %= MOD

answer = (lower[1:].sum() + upper[1:].sum()) % MOD
print(answer)


import numpy as np
N, K = tuple(map(int, input().split()))
mod = 1000000007

m = N ** 0.5
cnt = [N // i - N // (i + 1) for i in range(1, int(m) + 1)] 
cnt = np.array((cnt + [1 for _ in range(N - sum(cnt))])[::-1])
nxt = cnt[:]
for _ in range(K - 1):
    cnt = nxt * np.cumsum(cnt)[::-1] % mod

print((sum(cnt) % mod))


from itertools import accumulate

N,K = map(int, input().split())
mod = 10**9+7
sqt = int(N**0.5)
cnt = [N // i-N // (i+1) for i in range(1, N//sqt)] + [1]*sqt
x = cnt
for _ in range(K):
    x = [(i*j)%mod for i, j in zip(accumulate(reversed(x)), cnt)]
    

print(x[-1])

from numpy import int_

mod = 10 ** 9 + 7

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

M = int(N ** 0.5)

T = [N // i - N // (i + 1) for i in range(1, M + 1)]
A = int_([1] * (N - sum(T)) + T[::-1])

dp = A[:]
for _ in range(K - 1):
    dp = A * dp.cumsum()[::-1] % mod

print(dp.sum() % mod)

from itertools import accumulate
N,K=map(int,input().split())
N_s=int(N**0.5)
list_a=[1]*N_s
list_b=[N//j-N_s for j in range(1,N_s+1)]
list_p=[N//j-N_s for j in range(1,N_s+1)]
for p in range(1,len(list_p)):
        list_p[p-1]=list_p[p-1]-list_p[p]
        
for p in range(1,len(list_b)):
    list_b[p-1]=list_b[p-1]-list_b[p]

list_bb=list(reversed(list(accumulate(reversed(list_b)))))
list_aa=list(accumulate(list_a))

mod=10**9+7

for i in range(K-1):
    temp=sum(list_a)
    list_an=[(temp+list_bb[j])%mod for j in range(N_s)]
    list_bn=[(list_p[j-1]*list_aa[j-1])%mod for j in range(1,N_s+1)]

    list_bbn=list(reversed(list(accumulate(reversed(list_bn)))))
    list_aa=list(accumulate(list_an))
    list_a=list_an
    list_b=list_bn
    list_bb=list_bbn
    
print((sum(list_a)+sum(list_b))%mod)

def f(n,k):
    lim = int((n + 0.1) ** 0.5) + 1
    ws = []
    s = 0
    for i in range(1, lim):
        w = n // i - n // (i + 1)
        ws.append(w)
        s += w
    ws += [1] * (n - s)
    m = len(ws)
    dp0 = ws[::-1]
    dp1 = [0] * m
    for _ in range(k - 1):
        s = 0
        for j in range(m):
            s += dp0[j]
            dp1[m - j - 1] = (s * ws[j]) % md
        dp0 = dp1[:]
    print((sum(dp0) % md))
md=10**9+7
n,k=list(map(int,input().split()))
f(n,k)


import numpy as np

n, k = list(map(int, input().split()))
MOD = 10 ** 9 + 7
l = int(n ** 0.5)
coe = []
for i in range(l, 0, -1):
    coe.append(n // i - l)
coe.append(0)
coe.reverse()
coe = np.array(coe, dtype=np.int64)

dp1 = np.ones(l + 1, dtype=np.int64)
dp2 = coe.copy()
dp1[0] = 0
for i in range(k - 1):
    dp1acc = np.add.accumulate(dp1) % MOD
    dp12acc = np.add.accumulate((dp1 * coe % MOD)[::-1])[::-1]
    s = dp1acc[-1]
    dp1acc = np.roll(dp1acc, 1)
    dp1acc[0] = 0
    dp12acc[0] = 0
    dp1[1:] = (s + dp2[1:]) % MOD
    dp2 = dp12acc + dp1acc * coe % MOD
ans = (dp1.sum() + dp2[1]) % MOD
print(ans)


# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 桁dp、√Nまでをlower、それ以降をup_range、Nをlowerで割ったものでまとめる
MOD = 10 ** 9 + 7
N, K = lr()
M = int(N ** .5)
A = np.arange(M+1, dtype=np.int64)
high_range = np.zeros(M+1, dtype=np.int64)
high_range[1:] = N // A[1:] - np.maximum(M, N // (A[1:] + 1))  # Mはlowerに入れるので0
low = np.zeros(M+1, dtype=np.int64)
high = np.zeros(M+1, dtype=np.int64)
low[1] = 1
for _ in range(K):
    prev_low = low.copy()
    prev_high = high.copy()
    prev_low_cum = prev_low.cumsum() % MOD
    prev_high_cum = prev_high.cumsum() % MOD
    low = np.zeros(M+1, dtype=np.int64)
    low[1:] += (prev_low_cum[-1] + prev_high_cum[-1])
    low[1:] -= prev_high_cum[:-1]
    high = prev_low_cum * high_range
    low %= MOD; high %= MOD

answer = (low[1:].sum() + high[1:].sum()) % MOD
print((answer % MOD))


from itertools import accumulate
def BC132_F():
    n, k = list(map(int, input().split(' ')))
    mod = 10**9 + 7
    sqt = int(n**0.5)
    cnt = [n // i - n // (i + 1) for i in range(1, n // sqt)] + [1] * sqt
    x = cnt
    for _ in range(k):
        x = [(i * j) % mod for i, j in zip(accumulate(reversed(x)), cnt)]
    return x[-1]


print(BC132_F())

def solve():
    N, K = map(int, input().split())

    U = []; 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)
    prv = 0
    R = []
    for x in U:
        R.append(x-prv)
        prv = x
    def gen(it):
        MOD = 10**9 + 7
        r = 0
        for p, s in it:
            r = (p * s + r) % MOD
            yield r

    S = [1]*(L+1)
    S[-1] = 0
    for k in range(K):
        S[L-1::-1] = gen(zip(R, S))
    print(S[0])
solve()

import sys
input = sys.stdin.readline
import numpy as np
MOD = 10**9+7
  
n, k = map(int, input().split())
S = set()
i = 1
while i * i <= n:
  S.add(i)
  S.add(n//i)
  i += 1
L = np.array([0] + sorted(S), dtype=np.int64)
l = len(L) - 1
num = np.diff(L)
dp = np.zeros(l, dtype=np.int64)
dp[0] = 1
for _ in range(k):
  A = np.cumsum(dp)
  dp = A[::-1] * num
  dp %= MOD
ans = dp.sum() % MOD
print(ans)

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

m = n ** 0.5
cnt = [n // i - n // (i + 1) for i in range(1, int(m) + 1)] 
cnt = np.array((cnt + [1 for _ in range(n - sum(cnt))])[::-1])
nxt = cnt[:]
for _ in range(k - 1):
	cnt = nxt * np.cumsum(cnt)[::-1] % mod

print((sum(cnt) % mod))


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

# M+1以上で、商がぢょうとxになるやつ
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))

# 数列の末端ごとの個数
# upperについては、個数にわたって合計をとる
lower = np.zeros(M+1, dtype=np.int64)
upper = np.zeros(M+1, dtype=np.int64)
# 0項目に1を置いておくとする
lower[1] = 1
for k in range(1,K+1):
    prev_lower = lower
    prev_upper = upper
    np.cumsum(prev_lower, out = prev_lower)
    np.cumsum(prev_upper, out = prev_upper)
    prev_lower %= MOD
    prev_upper %= MOD
    # 下側 to 下側
    lower = np.zeros(M+1, dtype=np.int64)
    lower += (prev_lower[-1] + prev_upper[-1])
    lower[1:] -= prev_upper[:-1] # 商がn-1以下だと受け付けない
    lower[0] = 0
    # 上側 to 上側：ないはず
    # 下側 to 上側：
    upper = prev_lower * upper_cnt
    lower %= MOD
    upper %= MOD
    
answer = (lower.sum() + upper.sum()) % MOD
print(answer)


import numpy as np
N, K = list(map(int, input().split()))
mod = 1000000007

m = N ** 0.5
cnt = [N // i - N // (i + 1) for i in range(1, int(m) + 1)] 
cnt = np.array((cnt + [1 for _ in range(N - sum(cnt))])[::-1])
nxt = cnt[:]
for _ in range(K - 1):
    cnt = nxt * np.cumsum(cnt)[::-1] % mod

print((sum(cnt) % mod))


from itertools import accumulate

MOD = 10**9 + 7

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

def N2sqrtN(N):
    M = int(N**0.5)
    As = list(range(1, M+1))
    Bs = [N//A for A in reversed(As)]
    if As[-1] == Bs[0]:
        return As + Bs[1:]
    else:
        return As + Bs

Bs = N2sqrtN(N)
lenB = len(Bs)

nums = [1]
for i in range(lenB-1):
    nums.append(Bs[i+1]-Bs[i])

dp = [0] * lenB
dp[0] = 1
for i in range(1, K+1):
    dp = list(accumulate(dp))
    dp = [dpi*num%MOD for dpi, num in zip(reversed(dp), nums)]

print((sum(dp) % MOD))


MOD = 10 ** 9 + 7


def main(N, K):
  W = []
  i = 1
  while i <= N:
    v = N // i
    j = N // v
    # keys.append((v, j - i + 1))
    W.append(j - i + 1)
    i += j - i + 1

  l = len(W)
  dp = [0] * l

  total = 0
  for i, w in enumerate(W):
    total += w
    dp[l - i - 1] = total

  for i in range(2, K + 1):
    tmp = [0] * l
    total = 0
    for j, w in enumerate(W):
      v = dp[j] * w
      total += v
      total %= MOD
      tmp[l - j - 1] = total

    dp = tmp

  return dp[0]


def __starting_point():
  N, K = list(map(int, input().strip().split()))
  # import time
  # t = time.time()
  print((main(N, K)))
  # print(time.time() - t)

__starting_point()

#無理ぞ
n,k=map(int, input().split())
a,b=[],[]
i=1

while i*i<=n:
    a.append(i)
    b.append(n//i)
    i+=1
    
if a[-1]==b[-1]:
    b.pop()
a+=b[::-1]
import numpy as np
dp=np.array(a)
dp[1:]-=dp[:-1]
ini=np.copy(dp)
del a
del b
mod=10**9+7
for _ in range(k-1):
    pre=np.cumsum(dp)
    dp=ini*pre[::-1]
    dp%=mod
print(sum(dp)%mod)

from numpy import int_

mod = 10 ** 9 + 7

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

M = int(N ** 0.5)

T = [N // i - N // (i + 1) for i in range(1, M + 1)]
A = int_([1] * (N - sum(T)) + T[::-1])

dp = A[:]
for _ in range(K - 1):
    dp = A * dp.cumsum()[::-1] % mod

print(sum(dp) % mod)

from itertools import accumulate
N, K = map(int, input().split())
mod = 10 ** 9 + 7
sqrt = int(N**(1/2))
count = [N//i - N//(i+1) for i in range(1, N//sqrt)] + [1] * sqrt
ansList = count
for _ in range(K):
    ansList = [(i * j) % mod for i, j in zip(accumulate(reversed(ansList)), count)]

print(ansList[-1])

import sys
def solve():
    N, K = map(int, input().split())
    MOD = 10**9 + 7

    U = []; 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)
    prv = 0
    R = []
    for x in U:
        R.append(x-prv)
        prv = x
    def gen(R, S):
        r = 0
        for p, s in zip(R, S):
            r = (p * s + r) % MOD
            yield r

    S = [1]*(L+1)
    S[-1] = 0
    for k in range(K):
        S[L-1::-1] = gen(R, S)
    print(S[0])
solve()

import numpy as np

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

mx = np.sqrt(n).astype(int)

dp_u = np.ones(mx, np.int64)

N = np.full(mx, n, np.int64)
L = N // np.arange(1, mx + 1)
R = np.maximum(N // np.arange(2, mx + 2), mx)
coef = L - R
dp_d = coef

for _ in range(2, k + 1):
    acc_u = np.cumsum(dp_u) % mod
    acc_d = np.cumsum(dp_d[::-1])[::-1] % mod
    dp_u = (dp_u.sum() + acc_d) % mod
    dp_d = coef * acc_u % mod

ans = (dp_u.sum() + dp_d.sum()) % mod
print(ans)


import numpy as np

n, k = list(map(int, input().split()))
MOD = 10 ** 9 + 7
l = int(n ** 0.5)
coe = [n // i - l for i in range(l, 0, -1)]
coe.append(0)
coe.reverse()
coe = np.array(coe, dtype=np.int64)

dp1 = np.ones(l + 1, dtype=np.int64)
dp2 = coe.copy()
dp1[0] = 0
for i in range(k - 1):
    dp1acc_f = np.add.accumulate(dp1) % MOD
    dp1acc_b = np.add.accumulate((dp1 * coe % MOD)[::-1])[::-1] % MOD
    s = dp1acc_f[-1]
    dp1acc_f = np.roll(dp1acc_f, 1)
    dp1[1:] = (s + dp2[1:]) % MOD
    dp2[1:] = (dp1acc_b + dp1acc_f * coe)[1:] % MOD
ans = (dp1.sum() + dp2[1]) % MOD
print(ans)


import numpy as np

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

mx = 1
while (mx + 1) ** 2 <= n:
    mx += 1

dp_u = np.ones(mx, np.int64)
N = np.full(mx, n, np.int64)
L = N // np.arange(1, mx + 1)
R = np.maximum(N // np.arange(2, mx + 2), mx)
coef = L - R
dp_d = coef

for _ in range(2, k + 1):
    acc_u = np.cumsum(dp_u) % mod
    acc_d = np.cumsum(dp_d[::-1]) % mod
    dp_u = (dp_u.sum() + acc_d[::-1]) % mod
    dp_d = coef * acc_u % mod

ans = (dp_u.sum() + dp_d.sum()) % mod
print(ans)


from itertools import accumulate

def f(n,k):
    lim = int((n + 0.1) ** 0.5) + 1
    ws = []
    s = 0
    for i in range(1, lim):
        w = n // i - n // (i + 1)
        ws.append(w)
        s += w
    ws += [1] * (n - s)
    dp=ws
    m = len(ws)
    for _ in range(k - 1):
        dp=[s*w%md for s,w in zip(accumulate(dp[::-1]),ws)]
    print((sum(dp) % md))
md=10**9+7
n,k=list(map(int,input().split()))
f(n,k)


import numpy as np
N, K = list(map(int, input().split()))
mod = 1000000007

m = N ** 0.5
cnt = [N // i - N // (i + 1) for i in range(1, int(m) + 1)] 
cnt = np.array((cnt + [1 for _ in range(N - sum(cnt))])[::-1])
nxt = cnt[:]
for _ in range(K - 1):
    cnt = nxt * np.cumsum(cnt)[::-1] % mod

print((sum(cnt) % mod))


import sys
input = sys.stdin.readline
from itertools import accumulate
MOD = 10**9+7

def main():
  n, k = map(int, input().split())
  S = set()
  i = 1
  while i * i <= n:
    S.add(i)
    S.add(n//i)
    i += 1
  L = [0] + sorted(S)
  l = len(L) - 1
  num = [0]*l
  for i in range(l):
    num[i] = L[i+1] - L[i]
  dp = [0]*l
  dp[0] = 1
  for _ in range(k):
    A = list(accumulate(dp))
    for i in range(l):
      dp[i] = A[l-1-i] * num[i]
      dp[i] %= MOD
  ans = sum(dp) % MOD
  print(ans)

def __starting_point():
  main()
__starting_point()

import numpy as np
N, K = list(map(int,input().split()))
MOD = 10**9+7
div = list(range(1, int(np.sqrt(N))+1))
L1 = len(div)
div2 = [N//val for val in div]
div2.sort()
if div[-1] == div2[0]:
    div2.remove(div2[0])
L2 = len(div2)
L = L1+L2
ls = [1]*L1 + [0]*L2
tmp = div[-1]
for i,val in enumerate(div2):
    ls[i+L1] = val-tmp
    tmp = val
dp = [0]*L
dp = np.zeros((L), dtype='int64')
ls = np.array(ls, dtype='int64')
dp[:] = ls
r = np.zeros(L+1, dtype='int64')
r[:-1] = np.cumsum(dp, dtype='int64')[::-1]
for i in range(K-1):
    dp = (r[:-1]*ls)%MOD
    r[:-1] = np.cumsum(dp, dtype='int64')[::-1]
print((r[0]%MOD))


import numpy as np

MOD = 10**9+7

def divisor(x):
    div = [0]
    for i in range(1,int(x**0.5)+1):
        div.append(i)
        if x != i**2: div.append(x//i)
    return div

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

div = np.array(divisor(N))
div = np.sort(div)
div_dif = np.diff(div)
div_num = div.size -1 

dp = np.ones((K+1,div_num),np.int64)

for i in range(K):
    dp[i+1] = dp[i][::-1] * div_dif % MOD
    dp[i+1] = dp[i+1].cumsum() % MOD
    
    
print(dp[-1][-1])

from numpy import int_

mod = 10 ** 9 + 7

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

M = int(N ** 0.5)
T = [N // i - N // (i + 1) for i in range(1, M + 1)]
dp = int_([1] * (N - sum(T)) + T[::-1])

A = dp[:]
for _ in range(K - 1):
    dp = A * dp.cumsum()[::-1] % mod

print(sum(dp) % mod)

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)]+[(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)

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

# M+1以上で、商がぢょうとxになるやつ
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))

# 数列の末端ごとの個数
# upperについては、個数にわたって合計をとる
lower = np.zeros(M+1, dtype=np.int64)
upper = np.zeros(M+1, dtype=np.int64)
# 0項目に1を置いておくとする
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
    # 下側 to 下側
    lower = np.zeros(M+1, dtype=np.int64)
    lower += (cum_lower[-1] + cum_upper[-1])
    lower[1:] -= cum_upper[:-1] # 商がn-1以下だと受け付けない
    lower[0] = 0
    # 上側 to 上側：ないはず
    # 下側 to 上側：
    upper = cum_lower * upper_cnt
    lower %= MOD
    upper %= MOD
    
answer = (lower.sum() + upper.sum()) % MOD
print(answer)

import numpy as np

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

mx = np.sqrt(n).astype(int)

dp_u = np.ones(mx, np.int64)

N = np.full(mx, n, np.int64)
RNG = np.arange(1, mx + 2)
L = N // RNG[:-1]
R = N // RNG[1:]
R[-1] = np.maximum(R[-1], mx)
coef = L - R
dp_d = coef

for _ in range(2, k + 1):
    acc_u = np.cumsum(dp_u) % mod
    acc_d = np.cumsum(dp_d[::-1])[::-1] % mod
    dp_u = (dp_u.sum() + acc_d) % mod
    dp_d = coef * acc_u % mod

ans = (dp_u.sum() + dp_d.sum()) % mod
print(ans)