You are provided an integer \(N\) that denotes the number of nodes that are available in the tree. Every node contains a value that lies between \(1\) to \(N\) and no two nodes contain the same value.

You are required to count all the possible ways to construct a special binary tree of \(N\) nodes. A special binary tree is a binary tree that contains the following properties:

• All the levels are completely filled except possibly the last level
• Each even-valued node contains an even-valued node as its left child and an odd-valued node as its right child
• Each odd-valued node contains an odd-valued node as its left child and even-valued node as its right child.

Input format

• First line: \(T\) denoting the number of test cases
• Next \(T\) lines: A single integer \(N\) denoting the number of nodes that are available in the tree

Output format

For each test case, print the number of possible ways to create the special binary tree modulo \(10^9 + 7\). Print the output in a new line.

Constraints

\(1\leq T \leq 10^5\)

\(1\leq N \leq 10^6\)