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 |