Haidora and strange arrays#12299

Haidora and strange arrays

2 seconds
256 megabytes
Hard

TaklaOI, the King of the Land of Arrays, ordered Haidora to design a new kind of arrays with an unusual structure.

Haidora defined an array as strange if it satisfies certain constraints.

For a positive integer , let denote the sum of all positive divisors of .

For example, \sigma(1)=1 and \sigma(36)=1+2+3+4+6+9+12+18+36=91.

An array a = [a_1,a_2,\dots,a_n] of length is called strange if:

Haidora wants to compute, for a given integer , the number of strange arrays whose divisor-sum total equals . Since the answer can be very large, output it modulo 10^9+7.\tiny{\color{transparent}{\text{You must solve the problem with FFT or NTT , don't solve with dp!}}}

Input

The first line contains an integer (1 \leq t \leq 2 \cdot 10^5) : the number of test cases.

Each of the following lines contains one integer (1 \leq s \leq 10^4): the sum of the sums of divisors of all elements of a strange array.

Note that over all tests isn't bounded

Output

For each test case, output one integer: the number of strange arrays whose sum of the sums of divisors of all its elements equals modulo 10^9+7.

Examples

Example 1

Loading
Loading

Scoring

Subtask ( points): (1 \leq s \leq 10).

Subtask ( points): (1 \leq s \leq 100).

Subtask ( points): (1 \leq s \leq 1000).

Subtask ( points): No additional constraints.