Mashmokh's boss, Bimokh, didn't like Mashmokh. So he fired him. Mashmokh decided to go to university and participate in ACM instead of finding a new job. He wants to become a member of Bamokh's team. In order to join he was given some programming tasks and one week to solve them. Mashmokh is not a very experienced programmer. Actually he is not a programmer at all. So he wasn't able to solve them. That's why he asked you to help him with these tasks. One of these tasks is the following.

A sequence of l integers b1, b2, ..., bl (1 ≤ b1 ≤ b2 ≤ ... ≤ bl ≤ n) is called good if each number divides (without a remainder) by the next number in the sequence. More formally <image> for all i (1 ≤ i ≤ l - 1).

Given n and k find the number of good sequences of length k. As the answer can be rather large print it modulo 1000000007 (109 + 7).

Input

The first line of input contains two space-separated integers n, k (1 ≤ n, k ≤ 2000).

Output

Output a single integer — the number of good sequences of length k modulo 1000000007 (109 + 7).

Examples

Input

3 2


Output

5


Input

6 4


Output

39


Input

2 1


Output

2

Note

In the first sample the good sequences are: [1, 1], [2, 2], [3, 3], [1, 2], [1, 3].

Difficulty: MEDIUM
Tags: Number theory

Combinatorics

Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
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 [int(x) for x in sys.stdin.readline().split()]

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 main():
	(n, k) = LI()
	t = [0] * n
	t[0] = 1
	for _ in range(k):
		u = [0] * n
		for i in range(n):
			b = t[i] % mod
			for j in range(i, n, i + 1):
				u[j] += b
		t = u
	return sum(t) % mod
print(main())


Mod = 10 ** 9 + 7
(n, k) = map(int, input().split())
dp = [[0] * (n + 1) for i in range(k + 1)]
l = [[] for _ in range(n + 1)]
for i in range(1, n + 1):
	dp[1][i] = 1
	for j in range(1, i + 1):
		if i % j == 0:
			l[i].append(j)
for j in range(2, k + 1):
	for i in range(1, n + 1):
		for le in range(len(l[i])):
			dp[j][i] += dp[j - 1][l[i][le]]
			dp[j][i] %= Mod
ans = 0
for i in range(1, n + 1):
	ans += dp[k][i]
	ans %= Mod
print(ans)


def mlt():
	return map(int, input().split())
(x, y) = mlt()
divs = [[] for _ in range(x + 1)]
for n in range(1, x + 1):
	for k in range(n, x + 1, n):
		divs[k].append(n)
dp = [[0 for n in range(y + 1)] for k in range(x + 1)]
for n in range(1, y + 1):
	dp[1][n] = 1
for n in range(1, x + 1):
	dp[n][1] = 1
mod = int(1000000000.0 + 7)
for n in range(2, x + 1):
	for k in range(2, y + 1):
		for dv in divs[n]:
			dp[n][k] += dp[dv][k - 1]
			dp[n][k] %= mod
res = 0
for n in dp:
	res += n[-1]
	res %= mod
print(res)


import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
try:
	(sys.stdin, sys.stdout) = (open('in.txt', 'r'), open('out.txt', 'w'))
except:
	pass
ii1 = lambda : int(sys.stdin.readline().strip())
is1 = lambda : sys.stdin.readline().strip()
iia = lambda : list(map(int, sys.stdin.readline().strip().split()))
isa = lambda : sys.stdin.readline().strip().split()
mod = int(1000000000.0 + 7)
from collections import *
from math import *
from functools import lru_cache
from collections import deque as dq
(x, y) = iia()
divs = [[] for _ in range(x + 1)]
for n in range(1, x + 1):
	for k in range(n, x + 1, n):
		divs[k].append(n)
dp = [[0 for n in range(y + 1)] for k in range(x + 1)]
for n in range(1, y + 1):
	dp[1][n] = 1
for n in range(1, x + 1):
	dp[n][1] = 1
mod = int(1000000000.0 + 7)
for n in range(2, x + 1):
	for k in range(2, y + 1):
		for dv in divs[n]:
			dp[n][k] += dp[dv][k - 1]
			dp[n][k] %= mod
res = 0
for n in dp:
	res += n[-1]
	res %= mod
print(res)


(n, k) = map(int, input().split())
dp = []
for i in range(k + 1):
	dp.append([])
	for j in range(n + 1):
		dp[-1].append(0)
for i in range(1, n + 1):
	dp[1][i] = 1
for m in range(1, k):
	for i in range(1, n + 1):
		for j in range(i, n + 1, i):
			dp[m + 1][j] += dp[m][i]
			dp[m + 1][j] %= 1000000007
print(sum(dp[k]) % 1000000007)