Panda is preparing for a family get together. She decided to enjoy some traditions of her family. To impress everyone she decides to show her skills in the meeting.
A traditional array is an array in which all the adjacent elements are happy. Adjacent elements are happy if and only if one of them divides the other one. More formally, if Ai divides Ai+1 or Ai+1 divides Ai, then these are happy elements. All elements of the array should be integers in range [1, M].
Find out the number of traditional arrays of given length N. As the output can be very large, find answer modulo 109+7.
Input:
First line contains a single integer T, number of testcases.
Each test case has 2 elements N, length of array and M, the range of elements.
Output:
Single line for the answer of each testcase.
Constraints:
1 ≤ T ≤ 10
1 ≤ N,M ≤ 1000
For test case with N = 3 and M = 3
[1 1 1]
[1 1 2]
[1 1 3]
[1 2 1]
[1 2 2]
[1 3 1]
[1 3 3]
[2 1 1]
[2 1 2]
[2 1 3]
[2 2 1]
[2 2 2]
[3 1 1]
[3 1 2]
[3 1 3]
[3 3 1]
[3 3 3]
Hence answer = 17
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor