D :: Dreamy Sequence

Time Limit: 10 Seconds    Memory Limit: 65536 KB

A sequence of k integers b1, b2, …, bk (1 ≤ b1 ≤ b2 ≤ … ≤ bk ≤ n) is called a dreamy sequence if each number divides (without a remainder) the next number in the sequence. More formally, we can say bi | bi+1 for all 1 ≤ i ≤ k-1, or in another word, bi+1 mod bi = 0 for all 1 ≤ i ≤ k-1.

Given n and m, find the number of dreamy sequences of length m. Two sequences x1, x2, …, xm and y1, y2, …, ym are different, if and only if there exists an i such that 1 ≤ i ≤ m and xi != yi.

For example, for n=3, m=2, there are 5 different dreamy sequences:

[1, 1], [2, 2], [3, 3], [1, 2], [1, 3]

As the answer can be rather large print it modulo 1000000007 (109+7).

Input

The first line of the input contains an integer T ≤ 64, indicating the number of test cases. For each test case, the first and only line contains two integers n and m (1 ≤ n, m ≤ 2000), indicating the upper limit of the elements in the sequence and the length of the sequence.

Output

For each case output a single integer, indicating the number of dreamy sequences of length modulo 1000000007.

 

Sample Input

1
3 2

Sample Output

5

Submit