---languages_supported:- NAtitle: MISINTERcategory: NAold_version: trueproblem_code: MISINTERtags:- NAlayout: problem---### All submissions for this problem are available.Chef's brother likes to put words in Chef's mouth. Chef hates it about him of course. He has decided to become extremely careful about what he speaks. Fortunately, he knows how his brother transforms the words, that Chef uses. He has decided to use only those words which remain the same even after his brother's transformation!If Chef speaks an N letter word, his brother moves all the letters which are at even positions (assuming, numbering of positions starts from 1), to the beginning of the word; and the rest of the letters follow as they appeared in the word. Eg. abdef becomes beadf; cdcd becomes ddcc.Chef wants to know how many words can he use, provided that each word is composed of exactly N lowercase letters of the English alphabet. They use an ancient language in Byteland, which allows all possible words within the above definition!**Input format**The first line contains the number T, the number of test cases. In the following lines, T test cases follow. Every test case is a single line, that contains a single positive integer, N, which is the length of the words that Chef wants to use.**Output format**For each test case, print the number of words of length N that Chef can use; that is, number of words, which remain the same after brother's transformation. Since the result can be quite large, output the result modulo 1000000007.**Constraints**1 ≤ T ≤ 1001 ≤ N ≤ 100000**Sample input**<pre>311445</pre>**Sample output**<pre>26456976827063120</pre>