LQDOJ Contest #5 - Bài 4 - Dãy Chia Hết

Xem PDF

Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Dãy số gồm \(N\) số nguyên dương \(a_1,a_2,a_3,\ldots,a_N\) (thỏa mãn \(a_1 \le a_2 \le ... \le a_N\)) được gọi là một dãy chia hết nếu phần tử trong mảng là ước của phần tử kế tiếp, tức là \(a_i\vdots\ a_{i-1}\) với mọi \(1 \le i < N\).

Yêu cầu: Cho hai số nguyên dương \(N\)\(K\), tìm số dãy chia hết có độ dài là \(K\). Biết rằng các số trong dãy không vượt quá \(N\).

Input

  • Chứa hai số nguyên dương \(N\)\(K\) \((1 \le N,K \le 2000)\).

Output

  • In ra kết quả bài toán sau khi chia lấy dư cho \(10^9+7\).

Scoring

  • Subtask \(1\) (\(25\%\) số điểm): Có \(K = 2\).
  • Subtask \(2\) (\(25\%\) số điểm): Có \(K = 3\).
  • Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input
3 2
Output
5
Note

\(5\) dãy chia hết gồm: \((1,1);(1,2);(1,3);(2,2);(3,3)\).


Bình luận