- All Contests
- ProjectEuler+
- Project Euler #106: Special subset sums: meta-testing

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

# 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**

```
3
3
4
7
```

**Sample Output**

```
0
1
70
```