Counting Good Arrays

We consider an array consisting of positive integers $\{a_1, a_2, \ldots, a_n\}$ of length $n$ is good if and only if for each $1 \leq i < n$, $a_{i+1}$ is divisible by $a_i$. 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 $10^9+7$.

The first line of the input contains a single integer $T$ ($1 \leq T \leq 10^3$), denoting the number of test cases.

Each of the next $T$ lines contains two integers $n,m$ ($1 \leq n,m \leq 10^9$), denoting a test case.

It's guaranteed that the number of test cases satisfying $\max(n,m) > 10^3$ will not exceed $50$, the number of test cases satisfying $\max(n,m) > 10^6$ will not exceed $10$, and the number of test cases satisfying $\max(n,m) > 10^8$ will not exceed $1$.

For each test case, output the answer modulo $10^9+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\}$

2022“杭电杯”中国大学生算法设计超级联赛（7）