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 ≤ 100

1 ≤ N ≤ 100000

----- Sample Input 1 ------ 
3
1
14
45
----- Sample Output 1 ------ 
26
456976
827063120

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics

Constructive algorithms

Starter code:

Solutions:
mod = 1000000007

def solve(n):
	visited = [False] * (n + 1)
	pos = []
	for i in range(0, n + 1, 2):
		pos.append(i)
	for i in range(1, n + 1, 2):
		pos.append(i)
	count = 0
	for i in range(1, n + 1):
		if not visited[i]:
			count += 1
			while not visited[i]:
				visited[i] = True
				i = pos[i]
	print(pow(26, count, mod))
for i in range(int(input())):
	n = int(input())
	solve(n)


def soln(n):
	visited = [False] * (n + 1)
	pos = []
	for i in range(0, n + 1, 2):
		pos.append(i)
	for i in range(1, n + 1, 2):
		pos.append(i)
	count = 0
	for i in range(1, n + 1):
		if not visited[i]:
			count += 1
			while not visited[i]:
				visited[i] = True
				i = pos[i]
	return pow(26, count, 1000000007)
for _ in range(int(input())):
	print(soln(int(input())))


from sys import *
import math

def solve():
	mod = 1000000007
	n = int(stdin.readline().rstrip())
	visited = [False] * (n + 1)
	count = 0
	eli = list()
	oli = list()
	for i in range(1, n + 1):
		if i % 2 == 0:
			eli.append(i)
		else:
			oli.append(i)
	res = eli + oli
	res.insert(0, 0)
	for i in range(1, n + 1):
		if not visited[i]:
			temp = i
			while not visited[temp]:
				visited[temp] = True
				temp = res[temp]
			count += 1
	print(pow(26, count, mod))
for _ in range(int(stdin.readline().rstrip())):
	solve()


from sys import *
import math

def solve():
	mod = 1000000007
	n = int(stdin.readline().rstrip())
	visited = [False] * (n + 1)
	count = 0
	res1 = [2 * x for x in range(n // 2 + 1)]
	res2 = [2 * x + 1 for x in range(n - n // 2)]
	res = res1 + res2
	for i in range(1, n + 1):
		if not visited[i]:
			temp = i
			while not visited[temp]:
				visited[temp] = True
				temp = res[temp]
			count += 1
	print(pow(26, count, mod))
for _ in range(int(stdin.readline().rstrip())):
	solve()


from sys import *
import math

def main():
	for _ in range(int(stdin.readline().rstrip())):
		n = int(stdin.readline().rstrip())
		visited = [False] * (n + 1)
		start = 1
		count = 0
		res = [0] * (n + 1)
		for i in range(1, n // 2 + 1):
			res[i] = i * 2
		for i in range(n // 2 + 1, n + 1):
			res[i] = start
			start += 2
		for i in range(1, n + 1):
			if not visited[i]:
				temp = i
				while not visited[temp]:
					visited[temp] = True
					temp = res[temp]
				count += 1
		print(pow(26, count, 1000000007))
main()


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def main():
	for _ in tr():
		n = nl()
		start = 1
		res = [0] * (n + 1)
		for i in range(1, n // 2 + 1):
			res[i] = i * 2
		for i in range(n // 2 + 1, n + 1):
			res[i] = start
			start += 2
		visited = [False] * (n + 1)
		count = 0
		for i in range(1, n + 1):
			if not visited[i]:
				temp = i
				while not visited[temp]:
					visited[temp] = True
					temp = res[temp]
				count += 1
		print(pow(26, count, 1000000007))
main()