
ZOJ Problem Set  4011
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 k1\), or we can say \(b_{i+1} \text{ mod } b_i = 0\) for all \(1 \le i \le k1\). 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\)). InputThere 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. OutputFor each case output a single integer, indicating the number of happy sequences of length \(m\) modulo \(10^9+7\) Sample Input1 3 2 Sample Output5 HintIn 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 