AKVLKO02 - Changing Words

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

Added by:Ankit Kumar Vats
Date:2013-08-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.