← 返回题目列表

Codeforces · 414/B

B. Mashmokh 和 ACM

中文机器翻译题面 查看原题

Mashmokh 的老板 Bimokh 不喜欢 Mashmokh。于是他解雇了他。 Mashmokh 决定去读大学并参加 ACM,而不是找一份新工作。他想成为巴莫克团队的一员。为了加入,他被分配了一些编程任务并需要一周的时间来解决这些任务。 Mashmokh 并不是一位经验丰富的程序员。事实上他根本不是一个程序员。所以他没能解决这些问题。这就是为什么他要求你帮助他完成这些任务。其中一项任务如下。

如果每个数字都除(没有余数)序列中的下一个数字,则 l 个整数 b1, b2, ..., bl (1 ≤ b1 ≤ b2 ≤ ... ≤ bl ≤ n) 的序列称为良好序列。更正式地说,$$b_{i} \mid b_{i+1}$$ 对于所有 i (1 ≤ i ≤ l - 1)。

给定 n 和 k,找出长度为 k 的好序列的数量。由于答案可能相当大,所以将其模 1000000007 (109 + 7)。

输入

输入的第一行包含两个空格分隔的整数 n, k (1 ≤ n, k ≤ 2000)。

输出

输出一个整数 — 长度为 k 模 1000000007 (109 + 7) 的良好序列的数量。

示例

输入 #1

3 2

输出 #1

5

输入 #2

6 4

输出 #2

39

输入 #3

2 1

输出 #3

2

注意

在第一个样本中,好的序列是:[1, 1]、[2, 2]、[3, 3]、[1, 2]、[1, 3]。