Sum of Distinct Numbers#6960
A positive integer can be represented as a sum of distinct positive integers in several ways. For example:
for n = 5, there are ways: , 2 + 3, 1 + 4;
for n = 6, there are ways: , 1 + 5, 1 + 2 + 3, 2 + 4.
Here, different permutations of the same set of summands are considered the same. For example, 1 + 2 + 3, 2 + 1 + 3, and 3 + 1 + 2 all count as the same way.
The first line contains the number of test cases (1 \le t \le 20).
Each of the following lines contains a single integer (1 \le n \le 2000).
For each number , print on a separate line the number of different ways to represent it as a sum of distinct positive integers, as described above.
Since the answer may be very large, print it modulo .
Example 1