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$