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 numpy as np

n, k = 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)

Solution (Python):
from math import sqrt

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

m=int(sqrt(N))
if N//(m+1)==m:
    dp=[[[0  for i in range(0,2)] for j in range(0,int(sqrt(N)))] for k in range(0,K+1)]

    for i in range(0,int(sqrt(N))):
        dp[1][i][1]=1
        dp[1][i][0]=(N//(i+1)-N//(i+2))

    for k in range(2,K+1):
        s=0
        for i in range(0,int(sqrt(N))):
            s=(s+dp[k-1][i][1])%mod
            dp[k][i][0]=(s*(N//(i+1)-N//(i+2)))%mod

        for j in range(0,int(sqrt(N))):
            i=int(sqrt(N))-j-1
            s=(s+dp[k-1][i][0])%mod
            dp[k][i][1]=s

    ans=sum(dp[K][i][0]+dp[k][i][1] for i in range(0,int(sqrt(N))))%mod
    print(ans)

else:
    dp0=[[0 for i in range(0,int(sqrt(N))-1)] for k in range(0,K+1)]
    dp1=[[0 for i in range(0,int(sqrt(N)))] for k in range(0,K+1)]

    for i in range(0,int(sqrt(N))-1):
        dp0[1][i]=(N//(i+1)-N//(i+2))
        dp1[1][i]=1

    dp1[1][-1]=1

    for k in range(2,K+1):
        s=0
        for i in range(0,int(sqrt(N))-1):
            s=(s+dp1[k-1][i])%mod
            dp0[k][i]=(s*(N//(i+1)-N//(i+2)))%mod

        s=(s+dp1[k-1][int(sqrt(N))-1])%mod
        dp1[k][int(sqrt(N))-1]=s%mod
        for j in range(1,int(sqrt(N))):
            i=int(sqrt(N))-j-1
            s=(s+dp0[k-1][i])%mod
            dp1[k][i]=s

    ans=sum(dp0[K][i]+dp1[K][i] for i in range(0,int(sqrt(N))-1))%mod
    ans=(ans+dp1[K][-1])%mod

    print(ans)

Solution (Python):
import bisect
import heapq
import sys
import itertools
import queue


input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7


class V:
    def __init__(self, f):
        self.f = f
        self.v = None

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

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)

    def get(self):
        return self.v


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


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


def P(N):
    D = []
    for n in range(1, int(N ** 0.5) + 1):
        D.append(n)
        if N // n != n:
            D.append(N // n)
    D.sort()
    return D


def main():
    N, K = read_values()
    D = P(N)
    C = [(D[i] - D[i - 1]) % mod if i != 0 else D[i] for i, d in enumerate(D)]
    dp = [0] * len(D)
    S = [D] + [[0] * len(D) for k in range(K - 1)]
    I = [bisect.bisect_left(D, N // d) for d in D]

    for k in range(1, K):
        for i in range(len(D)):
            j = I[i]
            dp[i] = (S[k - 1][j] * C[i]) % mod
            S[k][i] = (S[k][i - 1] + dp[i]) % mod
    print(S[-1][-1] % mod)


if __name__ == "__main__":
    main()

Solution (Python):
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)


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 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 = np.zeros(M+1, dtype=np.int64)
    lower[1:] += (lower_cum[-1] + upper_cum[-1])
    lower[1:] -= upper_cum[:-1] 
    
    
    upper = lower_cum * upper_cnt
    lower %= MOD; upper %= MOD

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

Solution (Python):
def main():
    import sys
    from math import sqrt
    input = sys.stdin.readline

    mod = 1000000007
    N, K = map(int, input().split())
    n = int(sqrt(N))
    dp = [[0] * (2*n+1) for _ in range(K+1)]
    dp[0][1] = 1

    num = [0] * (n+1)
    for i in range(1, n):
        num[i] = N // i - N // (i+1)
    num[n] = N // n - n

    for i in range(K):
        cs = dp[i][:n+1]
        cs2 = dp[i][n+1:]
        for j in range(1, n+1):
            cs[j] = (cs[j] + cs[j-1])%mod
        for j in range(1, n):
            cs2[j] = (cs2[j] + cs2[j-1])%mod
        for j in range(1, n+1):
            dp[i+1][-j] = (cs[j] * num[j])%mod
            dp[i+1][j] = (cs2[-j] + cs[n])%mod
    ans = 0
    for a in dp[-1]:
        ans = (ans + a)%mod
    print(ans)


if __name__ == '__main__':
    main()

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

m = 1
a,b = [],[]
while m*m <= N:
    a.append(m)
    b.append(N//m)
    m += 1
if a[-1] == b[-1]:
    b.pop()
a += b[::-1]
w = [b-a for a,b in zip([0]+a, a)]

L = len(a)
dp = [1]*L
for _ in range(K-1):
    dp2 = [0]*L
    c = 0
    for i,v in enumerate(w):
        c += dp[i] * v
        dp2[L-1-i] += c
        dp2[L-1-i] %= MOD
    dp = dp2
ans = sum(a*b for a,b in zip(w,dp))
print(ans%MOD)

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
mod = 10 ** 9 + 7
h = 1
t = set()
while h * h <= N:
  t.add(N // h)
  t.add(h)
  h += 1
t = sorted(t)

tt = []
for x in t:
  tt.append(N // x)

dp = [[0] * len(t) for _ in range(K + 1)]
dp[0][0] = 1
for i in range(K):
  for j in range(len(t)):
    k = len(t) - j - 1
    dp[i + 1][k] += dp[i][j]
    dp[i + 1][k] %= mod
  
  for k in range(len(t) - 1, 0, -1):
    dp[i + 1][k - 1] += dp[i + 1][k]
    dp[i + 1][k - 1] %= mod
    rng = (t[k] - t[k - 1]) % mod
    dp[i + 1][k] *= rng
    dp[i + 1][k] %= mod

  
res = 0

for j in range(len(t)):
  res += dp[-1][j]
  res %= mod
print(res)

Solution (Python):
N, K = (int(i) for i in input().split())
N += 1
l1 = []
l2 = []
n_ma = 0
for i in range(1, N):
    j = (N-1)//(i+1) + 1
    if i > j:
        break
    elif i == j:
        l1.append(i)
        break
    l1.append(i)
    l2.append(j)
l2.reverse()
L = l1 + l2 + [N]
M = len(L) - 1
DP = [[0] * (M+1) for counter1 in range(K+1)]

def BIT_query(BIT, idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(BIT, idx, x):
    while idx <= M:
        BIT[idx] += x
        idx += idx&(-idx)
    return

def BIT_debug(BIT):
    return [BIT_query(BIT, i) - BIT_query(BIT, i-1) for i in range(1, M+1)]

MOD = 10**9 + 7
for i in range(M):
    BIT_update(DP[1], i+1, L[i+1]-L[i])
for i in range(1, K):
    for j in range(M):
        x = BIT_query(DP[i], M-j)
        x *= L[j+1]-L[j]
        x %= MOD
        BIT_update(DP[i+1], j+1, x)

print(BIT_query(DP[K], M)%MOD)

Solution (Python):
import math

n, k = map(int, input().split())
mod = 1000000007
n1 = int(math.sqrt(n))
if n1 * n1 == n:
    n2 = n1 - 1
else:
    n2 = n1

num = [n]
for i in range(1, n2):
    num.append(n // (i + 1))
    num[i - 1] -= num[i]
num[-1] -= n1

dp1 = [1      for i in range(n1)]
dp2 = [num[i] for i in range(n2)]
for _ in range(k - 1):
    l = sum(dp1) % mod
    newdp1 = [l for i in range(n1)]
    newdp2 = [0 for i in range(n2)]

    dp1sum = 0
    for j in range(0, n2):
        dp1sum = (dp1sum + dp1[j]) % mod
        newdp2[j] = (newdp2[j] + dp1sum * num[j]) % mod

    dp2sum = 0
    for j in range(n2 - 1, -1, -1):
        dp2sum = (dp2sum + dp2[j]) % mod
        newdp1[j] = (newdp1[j] + dp2sum) % mod
    dp1 = newdp1
    dp2 = newdp2
print((sum(dp1) + sum(dp2)) % mod)

Solution (Python):
from itertools import accumulate
n,k = map(int,input().split())
x = int(n**0.5)
mod = 10**9+7
if x*(x+1)<=n:
  flg = 1
else:
  flg = 0
t = 2*x+flg
dp = [[0 for i in range(t)] for j in range(2)]
for i in range(1,t):
  if i<=x:
    dp[0][i] = 1
    dp[1][i] = 1
  else:
    p = t-i
    dp[0][i] = n//p-n//(p+1)
    dp[1][i] = n//p-n//(p+1)
dp[1] = list(accumulate(dp[1]))
for i in range(2,k+1):
  dp[1][1:] = dp[1][t:0:-1]
  for j in range(1,t):
    dp[1][j] = dp[1][j]*dp[0][j]%mod
  for j in range(1,t):
    dp[1][j] = (dp[1][j]+dp[1][j-1])%mod
print(dp[1][t-1])

Solution (Python):
import numpy as np
N, K = 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)

Solution (Python):


import sys
from math import sqrt
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()

M = int(sqrt(N))
i = 1
x = N
li1 = []
li2 = []
mul = []
while i < x:
    li1.append(x)
    i += 1
    prev = x
    x = N // i
    li2.append((prev - x) * (i - 1))
    mul.append(prev - x)
li = []
if i == x:
    li += li1 + [x] + li2[::-1]
else:
    li += li1 + li2[::-1]

M = len(li)
mul = [1] * (M-len(li2)) + mul[::-1]
dp = list2d(K-1, M, 0)
for i in range(M):
    dp[0][i] = li[i]

for i in range(1, K-1):
    acc = list(accumulate(dp[i-1]))[::-1]
    for j in range(M):
        dp[i][j] = acc[j] * mul[j] % MOD
print(sum(dp[K-2]) % MOD)

Solution (Python):

"""
右におけるのが同じやつなら同一で扱う
普通なら√N * √Nになっちゃう


"""

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

lis = []
lis2 = []

i = 1
while i ** 2 <= N:

    if N // i != i:
        lis.append(i)
        lis2.append(N // i)
    else:
        lis.append(i)

    i += 1

lis2.reverse()
lis += lis2


dp = [0] * len(lis)

for i in range(len(lis)):
    if i == 0:
        dp[i] = 1
    else:
        dp[i] = lis[i]-lis[i-1]



for loop in range(K):

    ndp = [0] * len(lis)
    nsum = 0
    
    for i in range((len(lis))):

        nsum += dp[i]
        nsum %= mod

        if i != len(lis)-1:
            ndp[-1-i] += ((lis[-1-i] - lis[-2-i]) * nsum) % mod
        else:
            ndp[-1-i] += nsum % mod

    dp = ndp

print (dp[0])

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True


ans=0

n,k=LI()
b=[]

for i in range(1,int(n**0.5)+1):
    b+=[n//i]
    b+=[n//(n//i)]

b=sorted(set(b))
d=[i-j for i,j in zip(b,[0]+b)]
k+=1

m=len(b)
dp=[[0]*(m) for j in range(1+k)]
dp[0][0]=1

for i in range(k):
    sdp=[0]
    
    for j in range(m):
        sdp.append((sdp[-1]+dp[i][j]*d[j])%mo)
    sdp=sdp[::-1]
    
    for j in range(m):
        dp[i+1][j]=sdp[j]

print(sdp[0])

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

data=[i for i in range(1,int(n**.5)+1)]+[n//i for i in range(int(n**.5),0,-1)]

L=len(data)
dp=[1]*L
for i in range(1,L):
    dp[i]=data[i]-data[i-1]

for i in range(k-1):
    h=dp[:]
    for i in range(1,L):
        h[i]=(h[i]+h[i-1])%mod
    h=h[::-1]
    for i in range(1,L):
        h[i]=h[i]*(data[i]-data[i-1])%mod
    dp=h

ans=0
for u in dp:
    ans=(ans+u)%mod
print(ans)

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

MOD = 10 ** 9 + 7
p = int(n**0.5)


a = [i for i in range(1, p+1)]

for x in range(p, 0, -1):
    if n // x != p:
        a.append(n // x)

dp = [[0 for _ in range(len(a))] for _ in range(k)]

m = len(a)

temp = 0
b = [0] * m
for i, x in enumerate(a):
    b[i] = x - temp
    temp = x

for i in range(m):
    dp[0][i] = b[i]

for i in range(k-1):
    temp = 0
    for j in range(m-1, -1, -1):
        temp = (temp + dp[i][m-1-j]) % MOD
        dp[i+1][j] = temp * b[j] % MOD



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

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

n = 1
A = []
while True:
    A.append(N//n)
    if N//(n+1) < n+1: break
    n += 1
A.append(n)

L = 2*n
dp = [[0]*L for _ in range(K)]
for l in range(n):
    dp[0][l] = 1

i = 0
for l in reversed(range(n, L)):
    dp[0][l] = A[i] - A[i+1]
    i += 1

for k in range(1, K):
    s = 0
    for l in reversed(range(L)):
        s = (s+dp[k-1][L-l-1]) % mod
        dp[k][l] = s * dp[0][l] % mod

ans = 0
for l in range(L):
    ans = (ans + dp[K-1][l]) % mod

print(ans)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
sqrt = math.sqrt
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    s = S()
    b = list(set(s))
    a = len(list(set(s)))
    if a == 2 and s.count(b[0]) == s.count(b[1]) == 2:
        print("Yes")
    else:
        print("No")
    return


def B():
    n = II()
    p = LI()
    ans = 0
    for i in range(1,n-1):
        if (p[i - 1] < p[i] and p[i] < p[i + 1]) or (p[i + 1] < p[i] and p[i] < p[i - 1]):
            ans += 1
    print(ans)
    return


def C():
    n = II()
    d = LI()
    d.sort()
    ans = 0
    for i in range(10**5+1):
        if n // 2 == bisect_left(d, i):
            ans += 1
    print(ans)
    return


def combination_mod(n, k, mod):
    
    

    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) % mod
    b = factorial(k) % mod
    c = factorial(n - k) % mod
    return (a * power_func(b, mod - 2, mod) * power_func(c, mod - 2, mod)) % mod
    
def power_func(a, b, mod):
    
    

    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, mod)
        return d * d % mod
    if b % 2 == 1:
        return (a * power_func(a, b - 1, mod)) % mod


def D():
    n, k = LI()
    ans = 0
    for i in range(1,k+1):
        a = combination_mod(n - k + 1, i, mod)
        b = combination_mod(k - 1, i - 1, mod)
        print((a*b)%mod)
    return

def dijkstra(num, start, edge, g):

    dist = defaultdict(lambda: inf)
    dist[(start,0)] = 0
    q = [(dist[(start,0)], start, 0)]
    while q:
        du, u, t = heappop(q)
        for j in edge[u]:
            if t == 2:
                t = -1
            if dist[(j, t + 1)] > du + 1:
                dist[(j, t + 1)] = du + 1
                heappush(q, [dist[(j, t + 1)], j, t + 1])
    return dist

def E():
    n, m = LI()
    v = LIR_(m)
    s, t = LI_()
    edge = defaultdict(list)
    for x,y in v:
        edge[x].append(y)
    d = dijkstra(n, s, edge, t)
    if d[(t,0)] == inf:
        print(-1)
    else:
        print(d[(t,0)]//3)
    return










def F():
    n, k = LI()
    f = defaultdict(int)
    Range = int(sqrt(n))
    dp = [0] * (2 * Range)
    m = 0
    l = 0
    for i in range(Range, 0, -1):
        dp[i - 1] = 1
        f[i - 1] = 1
        if n // i == i:
            l = 1
            continue
        dp[Range + m] = n // i - n // (i + 1)
        f[Range + m] = n // i - n // (i + 1)
        m += 1
    R = 2 * Range - l
    for _ in range(k - 1):
        ndp = [0] * (2 * Range)
        for j in range(R):
            ndp[R - j - 1] = dp[j]
        ndp = list(itertools.accumulate(ndp[::-1]))[::-1]
        dp = [(d * f[num]) % mod for num,d in enumerate(ndp)]
    ans = sum(dp)%mod
    print(ans)
    return




if __name__ == '__main__':
    F()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter, defaultdict
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
import copy
import bisect
MOD = 10**9 + 7
from logging import getLogger, StreamHandler, DEBUG, WARNING
logger = getLogger(__name__)
handler = StreamHandler()
handler.setLevel(DEBUG)
logger.setLevel(DEBUG)


logger.addHandler(handler)
def main():
    n,k = getList()

    
    divisors = []
    tmp_div = n + 1
    for i in range(1, int(math.sqrt(n)) + 3):
        if tmp_div * i > n:
            other = n // i
            if i > other:
                break
            elif i == other:
                divisors.append(i)
                break
            else:
                divisors.append(i)
                divisors.append(other)

    divisors.sort()
    n_div = len(divisors)
    

    
    diff = [divisors[0]]
    for i, j in zip(divisors, divisors[1:]):
        diff.append(j - i)
    dp = copy.copy(diff)
    
    

    for iteration in range(k-1):
        dp_copy = []
        tmp = sum(dp) % MOD
        dp_copy.append((tmp * diff[0]) % MOD)
        for cid, dp_content in enumerate(range(n_div - 1)):
            tmp -= dp[n_div - dp_content - 1]
            dp_copy.append((tmp * diff[cid+1]) % MOD)

        dp = copy.copy(dp_copy)

        
    print(sum(dp) % MOD)
    
    
if __name__ == "__main__":
    main()

Solution (Python):
N, K = map(int, input().split())
mod = 10**9+7
n = int(N**0.5)
dp1 = [[0]*(n+1) for _ in range(K)]
dp2 = [[0]*(n+1) for _ in range(K)]
for i in range(1, n+1):
    dp1[0][i] = 1
dp2[0][n] = N//n-n
for i in range(1, n):
    dp2[0][i] = (N//i-N//(i+1))%mod
for i in range(1, K):
    cum = 0
    for j in range(1, n+1):
        dp2[i][j] = ((dp1[i-1][j]+cum)%mod*dp2[0][j])%mod
        cum+=dp1[i-1][j]
        cum%=mod
    for j in range(1, n+1)[::-1]:
        dp1[i][j] = (cum+dp2[i-1][j])%mod
        cum+=dp2[i-1][j]
        cum%=mod
print((sum(dp1[-1])%mod+sum(dp2[-1])%mod)%mod)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    s=set()
    for i in range(1,1+int(n**.5)):
        s.add(i)
        s.add(n//i)
    A=sorted(s)
    m=len(A)
    coef=[0]*m
    coef[0]=1
    for i in range(1,m):
        coef[i]=A[i]-A[i-1]
    dp=[0]*m
    dp[0]=1
    for i in range(k):
        for j in range(m-1):
            dp[j+1]+=dp[j]
            dp[j+1]%=MOD
        ndp=[0]*m
        for j in range(m):
            ndp[j]=dp[m-j-1]*coef[j]
            ndp[j]%=MOD
        dp=ndp
    print(sum(dp)%MOD)
resolve()

Solution (Python):

import sys
def input():
	return sys.stdin.readline().strip()

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

rootN = int(N**0.5)
num_list = [1]*rootN

now = rootN
for num in range(rootN, 0, -1):
	x = N//num
	num_list.append(x - now)
	now = x

dp = [[0]*len(num_list) for i in range(K)]
for i in range(len(num_list)):
	dp[0][i] = num_list[i]


mod = 10**9 + 7
for k in range(1, K):
	sum_before = [dp[k - 1][0]]
	for i in range(1, len(num_list)):
		sum_before.append(sum_before[-1]+dp[k - 1][i])
	for i in range(len(num_list)):
		dp[k][i] = (num_list[i]*sum_before[len(num_list) - 1 - i])%mod

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

Solution (Python):
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


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)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

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

M = int(N**.5)

lower = np.zeros(M+1,np.int64)
upper = np.zeros(M+1,np.int64)
size = np.zeros(M+1,np.int64)
x = N//np.arange(1,M+1)
size[1:] = x; size[1:-1] -= x[1:]; size[M] = N//M - M


lower[1] += 1
for _ in range(K):
    prev_lower = lower
    prev_upper = upper
    prev_lower_cum = lower.cumsum() % MOD
    prev_upper_cum = upper[::-1].cumsum()[::-1] % MOD 
    lower = np.zeros(M+1,np.int64)
    upper = np.zeros(M+1,np.int64)
    
    upper += prev_lower_cum * size
    
    lower[1:M+1] += prev_lower_cum[-1]
    
    lower[1:M+1] += prev_upper_cum[1:M+1]
    lower %= MOD
    upper %= MOD

answer = (lower.sum() + upper.sum()) % MOD
print(answer)

Solution (Python):
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])

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

LIM = int(N ** 0.5) * 2 + 1
dp = [[0] * LIM for i in range(K - 1)]

ts = set()
tsl = []
tsr = []
num = {}
for i in range(1, int(N ** 0.5) + 1):
    x = N // i
    y = N // (N // i)
    if not tsl or tsl[-1] > x:
        tsl.append(x)
    if x != y and (not tsr or tsr[-1] < y):
        tsr.append(y)
    if x not in num:
        num[x] = 0
    if y not in num:
        num[y] = 0
ts = tsl + tsr[::-1]

idx = {k: i for i, k in enumerate(ts)}
for j, t in enumerate(ts):
    num[t] = (N // t - N // ts[j-1]) if j > 0 else 1
    
    dp[0][idx[t]] = num[t] * t


MOD = 1000000007
for i in range(1, K - 1):
    pref = 0
    for j in reversed(range(len(ts))):
        
        R = len(ts) - j - 1
        pref += dp[i-1][R]
        dp[i][j] = pref * num[ts[j]] % MOD
        

        
        
        



    
ans = sum(dp[-1])
print(ans % 1000000007)

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
P = 110000
MOD = 10 ** 9 + 7
S = [0] * P
dp = [[0] * P for i in range(110)]
num = [0] * P
i = 1
t = 0
while i <= N:
    j = N // i
    if i <= j:
        num[t] = 1
        t += 1
        i += 1
    else:
        num[t] = N // j - i + 1
        i = N // j + 1
        t += 1


dp[0][0] = 1
for k in range(K):
    S = [0] * P
    for j in range(t + 1):
        S[j + 1] = S[j] + dp[k][j]
        S[j + 1] %= MOD
    for j in range(t):
        dp[k + 1][j] = S[t - j] * num[j]
        dp[k + 1][j] %= MOD

ans = 0
for i in range(t + 1):
    ans += dp[K][i]
    ans %= MOD
print(ans)

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



rN = int(N ** 0.5)
T = {N//x for x in range(1, rN+1)}
T |= {x for x in range(1, rN+1)}
T = [0,] + sorted(list(T))	


dp = []
dp.append([0,] + [T[i]-T[i-1] for i in range(1, len(T))])

for k in range(K-1):
	dp.append([0,] * len(T))
	dp[-1][-1] = dp[-2][1]
	for t in range(2, len(T)):
		dp[-1][-t] = (dp[-2][t] + dp[-1][-t+1]) % MOD
	for t in range(len(T)):
		dp[-1][t] = (dp[-1][t] * dp[0][t]) % MOD

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

Solution (Python):
from itertools import accumulate

MOD = 10**9 + 7

N, K = 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)

Solution (Python):
from math import sqrt
n, k = map(int, input().split())
MOD = 10**9 + 7
max1 = int(sqrt(n))
dp1 = [[0 for _ in range(max1+1)] for _ in range(k)]
for j in range(1, max1+1):
	dp1[0][j] = 1
max2 = int(n/(max1+1))
dp2 = [[0 for _ in range(max2+1)] for _ in range(k)]
for j in range(1, max2+1):
	dp2[0][j] = int(n/j) - int(n/(j+1))

for i in range(k-1):
	csum1 = (sum(dp1[i])+sum(dp2[i])) % MOD
	dp1[i+1][1] = csum1
	for j in range(2, max1+1):
		dp1[i+1][j] = (dp1[i+1][j-1] - dp2[i][j-1]) % MOD
	csum2 = sum(dp1[i][:max2+1]) % MOD
	dp2[i+1][max2] = (csum2*dp2[0][max2]) % MOD
	for j in range(max2-1, 0, -1):
		csum2 -= dp1[i][j+1]
		csum2 %= MOD
		dp2[i+1][j] = (csum2*dp2[0][j]) % MOD

print((sum(dp1[k-1])+sum(dp2[k-1]))%MOD)

Solution (Python):
from math import sqrt
from itertools import accumulate

def inpl(): return list(map(int, input().split()))

MOD = 10**9 + 7
N, K = inpl()

p = 0
X = []
for i in range(1, int(sqrt(N))+1):
    X.append(N//i)

A = [1]*len(X) 
B = [X[-2-i] - X[-1-i] for i in range(len(X)-1)]
if sum(A) + sum(B) < N:
    C = A + [N-sum(A)-sum(B)] + B
else:
    C = A + B

DP = [c%MOD for c in C]

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

    for i in range(len(C)):
        DP2[i] = (S[-1-i]*C[i])%MOD

    DP = DP2

print(sum(DP)%MOD)

Solution (Python):
import math
from itertools import chain

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

modulo = 10 ** 9 + 7
sqrtN  = int(math.sqrt(N))

P = [N // d for d in range(1, sqrtN + 1)]





M = {i: 1 for i in chain(P, range(1, P[-1]))}




for k in range(2, K + 2):
    M2 = {}
    M2[N] = M[1]
    for m, i in zip(P, P[1:]):
        M2[i]  = M2[m] + sum(M[j] for j in range(N // m + 1, N // i + 1))
        M2[i] %= modulo
    for i in range(P[-1] - 1, 0, -1):
        M2[i]  = M2[i + 1] + M[N // i] * (N // i - N // (i + 1))
        M2[i] %= modulo
    M = M2

print(M[1])

Solution (Python):
def f_small_products(N, K, MOD=10**9 + 7):
    
    sqrt_n = int(N**0.5)

    
    num = [0 for i in range(2 * sqrt_n + 1)]
    
    for i in range(1, sqrt_n + 1):
        num[i] = 1
    
    for i in range(1, sqrt_n + 1):
        lo = max(sqrt_n + 1, (N + i + 1) // (i + 1))
        hi = N // i
        num[2 * sqrt_n + 1 - i] = hi - lo + 1

    
    
    dp = [[0 for j in range(2 * sqrt_n + 2)] for i in range(K + 1)]
    dp[0][1] = 1  
    for i in range(K):
        
        for j in range(1, 2 * sqrt_n + 1):
            ways = (dp[i][j] * num[j]) % MOD
            dp[i + 1][1] += ways
            dp[i + 1][2 * sqrt_n + 2 - j] -= ways
        for j in range(1, 2 * sqrt_n + 1):
            dp[i + 1][j] += dp[i + 1][j - 1]

    return sum(a * b for a, b in zip(dp[K], num)) % MOD

N, K = [int(i) for i in input().split()]
print(f_small_products(N, K))

Solution (Python):
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)