Welcome to ZOJ
Select Problem
ZOJ Problem Set - 4011
Happy Sequence

Time Limit: 3 Seconds      Memory Limit: 65536 KB

A sequence of \(k\) integers \(b_1, b_2, \dots, b_k\) (\(1 \le b_1 \le b_2 \le ... \le b_k \le n\)) is called a happy sequence if each number divides (without a remainder) the next number in the sequence. More formally, we can say \(b_i | b_{i+1}\) for all \(1 \le i \le k-1\), or we can say \(b_{i+1} \text{ mod } b_i = 0\) for all \(1 \le i \le k-1\).

Given \(n\) and \(m\), find the number of happy sequences of length \(m\). Two sequences \(x_1, x_2, \dots, x_m\) and \(y_1, y_2, \dots, y_m\) are different, if and only if there exists an \(i\) such that \(1 \le i \le m\) and \(x_i \ne y_i\).

As the answer can be rather large print it modulo \(1000000007\) (\(10^9 + 7\)).


There are multiple test cases. The first line of the input contains an integer \(T\) (about 50), indicating the number of test cases. For each test case:

The first and only line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 2000\)), indicating the upper limit of the elements in the sequence and the length of the sequence.


For each case output a single integer, indicating the number of happy sequences of length \(m\) modulo \(10^9+7\)

Sample Input

3 2

Sample Output



In the sample test case, the happy sequences are: \([1, 1]\), \([2, 2]\), \([3, 3]\), \([1, 2]\), \([1, 3]\).

Author: WANG, Yucheng
Source: ZOJ Monthly, March 2018
Submit    Status