Given integer N (1 <= N <= 60), output the number of Rooted Unlabeled Trees which have an odd number of independent sets.

Rooted Unlabeled Tree: An Unlabeled Tree with a specified vertex as root and order amongst children does not matter. That is, two trees are considered equal if they are the same after some re-ordering of their non-root vertices. A rigorous definition is "two Rooted Unlabeled Trees T1 and T2 are equal if and only if there is a bijection f between T1 and T2 such that if root1 and root2 are the roots of T1 and T2 respectively, f(root1)=root2 and edge (u,v) is in T1 if and only if edge (f(u),f(v)) exists in T2"

Independent Set: A set of vertices (possibly empty) is called an Independent Set if no two vertices of the set have an edge between them.

Input

First line contains T, the number of test cases.

Next T lines contain one number each, N.

Output

Output T lines, one per test case. Each line should contain the number of rooted unlabeled trees which have an odd number of independent sets. Output the answer modulo 1000000007. That is, if the actual answer is A, output A % 1000000007. (This is just to keep computations within 64 bit integers.)

Example

Input:
6
1
2
3
4
5
40

Output:
0
1
2
2
5
632355321