6605: Counting Good Arrays
内存限制：128 MB
时间限制：6.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
We consider an array consisting of positive integers {a1,a2,…,an} of length n is good if and only if for each 1≤i<n, ai+1 is divisible by ai. Please note that we consider all the arrays with length 1 are good.
Given two integers n and m, please count the number of good arrays whose length is no greater than n and whose largest element is no greater than m. Since the answer may be large, you just need to output the answer modulo 109+7.
Given two integers n and m, please count the number of good arrays whose length is no greater than n and whose largest element is no greater than m. Since the answer may be large, you just need to output the answer modulo 109+7.
输入
The first line of the input contains a single integer T (1≤T≤103), denoting the number of test cases.
Each of the next T lines contains two integers n,m (1≤n,m≤109), denoting a test case.
It's guaranteed that the number of test cases satisfying max(n,m)>103 will not exceed 50, the number of test cases satisfying max(n,m)>106 will not exceed 10, and the number of test cases satisfying max(n,m)>108 will not exceed 1.
Each of the next T lines contains two integers n,m (1≤n,m≤109), denoting a test case.
It's guaranteed that the number of test cases satisfying max(n,m)>103 will not exceed 50, the number of test cases satisfying max(n,m)>106 will not exceed 10, and the number of test cases satisfying max(n,m)>108 will not exceed 1.
输出
For each test case, output the answer modulo 109+7 in a single line.
样例输入 复制
5
2 4
3 5
10 12
24 17
114514 1919810样例输出 复制
12
31
3915
190204
13530870提示
All the good arrays with n=2,m=4 are:
- {1},{2},{3},{4}
- {1,1},{1,2},{1,3},{1,4}
- {2,2},{2,4}
- {3,3}
- {4,4}