A9405. Mashmokh and ACM
编程题
普及/提高-
知识点
题目描述
Mashmokh 的老板 Bimokh 不喜欢 Mashmokh，所以把他开除了。Mashmokh 决定去上大学，成为一名程序员而不是会计。为了进入大学，他需要通过信息学考试。考试内容包括以下任务：给你一个长度为 $k$ 的序列，其中每个元素都是不超过 $n$ 的正整数。此外，还有一个条件：对于所有从 $1$ 到 $k - 1$ 的 $i$，有 $b_{i + 1}$ 能被 $b_i$ 整除。
你的任务是帮助 Mashmokh 计算这样的序列有多少个。由于这个数字可能非常大，你需要输出答案对 $10^9 + 7$ 取模的结果。
你的任务是帮助 Mashmokh 计算这样的序列有多少个。由于这个数字可能非常大，你需要输出答案对 $10^9 + 7$ 取模的结果。
输入格式
输入的第一行包含两个用空格分隔的整数 $n$ 和 $k$（$1 \le n, k \le 2000$）。
输出格式
输出一个整数——满足条件的序列数对 $10^9 + 7$ 取模的结果。
输入输出样例
输入 #1
3 2
输出 #1
5
输入 #2
6 4
输出 #2
39
输入 #3
2 1
输出 #3
2
说明/提示
- 样例 1 枚举：$[1, 1]$，$[1, 2]$，$[1, 3]$，$[2, 2]$，$[3, 3]$，共 $5$ 种。
- 样例 3：序列有 $[1]$、$[2]$，共 $2$ 种。
- 注意是"后一个能被前一个整除"，所以下一个数是当前数的**倍数**。
- 样例 3：序列有 $[1]$、$[2]$，共 $2$ 种。
- 注意是"后一个能被前一个整除"，所以下一个数是当前数的**倍数**。