Project Euler #106: Special subset sums: meta-testing

_{This problem is a programming version of Problem 106 from projecteuler.net}

Let represent the sum of elements in set of size . We shall call it a special sum set if for any two non-empty disjoint subsets, and , the following properties are true:

; that is, sums of subsets cannot be equal.
If contains more elements than then .

For this problem we shall assume that a given set contains strictly increasing elements and it already satisfies the second rule.

Surprisingly, out of the possible subset pairs that can be obtained from a set for which , only of these pairs need to be tested for equality (first rule). Similarly, when , only out of the subset pairs need to be tested.

For a given set size , how many subset pairs need to be tested for equality?

Input Format

First line contains an integer denoting the number of test cases.
Each of the following lines contain one integer - the size of set.

Constraints

Output Format

For each of test cases print one line containing a single integer - the number of subset pairs that need to be tested for equality. As this number can be extremely large, output it modulo .

Sample Input

Sample Output

0
1
70