Partition

How many ways can the numbers 1 to 15 be added together to make 15? The technical term for what you are asking is the "number of partition" which is often called P(n). A partition of n is a collection of positive integers (not necessarily distinct) whose sum equals n.

Now, I will give you a number n, and please tell me P(n) mod 1000000007.

The first line contains a number T(1 ≤ T ≤ 100), which is the number of the case number. The next T lines, each line contains a number n(1 ≤ n ≤ 10⁵) you need to consider.

For each n, output P(n) in a single line.

4
5
11
15
19

7
56
176
490

2013 Multi-University Training Contest 5