Divide and Count

★★★★★

1 votes

Maths

Details

Problem

You are given a positive integer $N$ . Find out the total number of ways in which $N$ can be divided into some poitive integers.

If $N =x+x+y$ then $(x,x,y),\ ( x,y,x) \ and\ ( y,x,x)$ are counted as three different ways.

Since answer could be very large, print it modulo $10^9+7$ .

Input:
First line contians a single integer $t$ denoting the number of test cases.
First line of each test case contains a single integer $N.$

Output:
For each test case print a single line containig one integer, the number of ways in which $N$ can be divided modulo $10^9+7$ .

Constraints:
$1<=t<=10^5$
$1<=N<=10^9$

Sample Input

2
1
4

Sample Output

1
8

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For test case 2:

N=4

N can be divided in the following ways:

1 1 1 1

2 1 1

1 2 1

1 1 2

2 2

3 1

1 3

Total number of ways = 8.