Joey's Computer got a bug. Whenever there is a word, it changes itself such that all the letters at the even position comes to the beginning of the word. For example, "computer" will become "optrcmue", "who" will change to "hwo" etc. But he found out that there will be some words, that will remain same even after this change, for example, "aab" will remain "aab". Now, if we use only lower case English letters, Joey wants to know how many "N" letters words are there that remain same after this change. As the answer can be quite large, print in modulo 1000000007.

Input

The first line will contain "T", the number of test cases. Each of the next "T" lines will have an integer "N".

Output

For each test case, print the number of "N" letters words that will remain same after this change modulo 1000000007.

Constraints

1 <= T <= 100

1 <= N <= 10^5

Example

Input:
3
1
14
49

Output:
26
456976
11881376