Do you know that The Chef has a special interest in palindromes? Yes he does! Almost all of the dishes in his restaurant is named by a palindrome strings. The problem is that a name of a dish should not be too long, so The Chef has only limited choices when naming a new dish.

For the given positive integer N, your task is to calculate the number of palindrome strings of length not exceeding N, that contain only lowercase letters of English alphabet (letters from 'a' to 'z', inclusive). Recall that a palindrome is a string that reads the same left to right as right to left (as in "radar").

For example:

- For N = 1, we have 26 different palindromes of length not exceeding N:
"a", "b", ..., "z".
- For N = 2 we have 52 different palindromes of length not exceeding N:
"a", "b", ..., "z",
"aa", "bb", ..., "zz".
- For N = 3 we have 728 different palindromes of length not exceeding N:
"a", "b", ..., "z",
"aa", "bb", ..., "zz",
"aaa", "aba", ..., "aza",
"bab", "bbb", ..., "bzb",
...,
"zaz", "zbz", ..., "zzz".

Since the answer can be quite large you should output it modulo 1000000007 (109 + 7). Yes, we know, most of you already hate this modulo, but there is nothing we can do with it :)

-----Input-----

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The only line of each test case contains a single integer N.

-----Output-----

For each test case, output a single line containing the answer for the corresponding test case.

-----Constrains-----

- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 109

-----Example-----
Input:
5
1
2
3
4
100

Output:
26
52
728
1404
508533804

-----Explanation-----

The first three examples are explained in the problem statement above.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Number theory

Mathematics

Matrices

Data structures
Skill types: Data structures

Starter code:

Solutions:
import math

def abc(n):
	x = math.ceil(n / 2)
	e = 10 ** 9 + 7
	c = pow(25, e - 2, e)
	if n % 2 == 0:
		a = (pow(26, x, e) - 1) % e
		ans = 2 * a * 26 * c % e
	elif x == 1:
		ans = 26
	else:
		a = (pow(26, x - 1, e) - 1) % e
		ans = 2 * a * 26 * c % e
		ans = (ans + pow(26, x, e)) % e
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	print(abc(n))


MOD = 1000000007

def mult(A, B):
	R = []
	for i in range(len(A)):
		row = []
		for j in range(len(B[0])):
			result = 0
			for k in range(len(B)):
				result += A[i][k] * B[k][j] % MOD
				result %= MOD
			row.append(result)
		R.append(row)
	return R

def power(A, p):
	if p == 1:
		return A
	Anb2 = power(A, int(p / 2))
	R = mult(Anb2, Anb2)
	if p & 1:
		return mult(R, A)
	else:
		return R

def powerNum(A, p):
	if p == 1:
		return A
	Anb2 = powerNum(A, int(p / 2))
	R = Anb2 * Anb2 % MOD
	if p & 1:
		return R * A % MOD
	else:
		return R

def powerSum(n, p):
	A = [[n, 1], [0, 1]]
	M0 = [[0], [n]]
	Ap = power(A, p)
	R = mult(Ap, M0)
	return R[0][0]

def solution():
	n = int(input())
	if n == 1:
		print(26)
		return
	sum = powerSum(26, int(n / 2)) * 2 % MOD
	if n & 1:
		sum += powerNum(26, int((n + 1) / 2))
		sum %= MOD
	print(sum)
T = int(input())
while T > 0:
	T = T - 1
	solution()


T = int(input())
for t in range(T):
	N = int(input())
	if N % 2 == 0:
		print(int(560000006 * (pow(26, N // 2, 1000000007) - 1)) % 1000000007)
	else:
		print((int(560000006 * (pow(26, N // 2, 1000000007) - 1)) + pow(26, N // 2 + 1, 1000000007)) % 1000000007)


mod = 10 ** 9 + 7
inv = pow(25, mod - 2, mod)
for i in range(int(input())):
	N = int(input())
	if N % 2 == 0:
		r = 2 * 26 * (pow(26, N // 2, mod) - 1) % mod * inv % mod
	else:
		r = (27 * pow(26, N // 2 + 1, mod) - 52) % mod * inv % mod
	print(r)


def main():
	modulo = 1000000007
	for T in range(int(input())):
		N = int(input())
		t = N // 2
		ans = 560000006 * (pow(26, t, modulo) - 1) % modulo
		if N % 2:
			ans = (ans + pow(26, t + 1, modulo)) % modulo
		print(ans)
main()


mod = 10 ** 9 + 7

def f(n):
	k = n + 1 >> 1
	ans = 26 * (pow(26, k, mod) - 1) * pow(25, mod - 2, mod) * 2
	if n % 2:
		ans -= pow(26, k, mod)
	ans %= mod
	return ans
for _ in range(int(eval(input()))):
	n = int(eval(input()))
	print(f(n))


import math

def a(n):
	x = math.ceil(n / 2)
	e = 1000000007
	c = pow(25, e - 2, e)
	if n % 2 == 0:
		a = (pow(26, x, e) - 1) % e
		ans = 2 * a * 26 * c % e
	elif x == 1:
		ans = 26
	else:
		a = (pow(26, x - 1, e) - 1) % e
		ans = 2 * a * 26 * c % e
		ans = (ans + pow(26, x, e)) % e
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	print(a(n))


def permutation(n, p):
	r = 26
	if n == 1:
		return 26
	elif n == 2:
		return 52
	elif n == 3:
		return 728
	elif n % 2 == 0:
		return 2 * (bin_expo(r, n // 2 + 1, p) - r) * bin_expo(25, 1000000005, p) % p
	else:
		n = n + 1
		return (2 * ((bin_expo(r, n // 2 + 1, p) - r) * bin_expo(r - 1, 1000000005, p)) - bin_expo(26, n // 2, p)) % p

def bin_expo(x, n, p):
	if n == 0:
		return 1
	elif n == 1:
		return x % p
	else:
		temp = bin_expo(x, n // 2, p)
		temp = temp * temp % p
		if n % 2 == 0:
			return temp
		else:
			return x % p * temp % p
test = int(input())
for _ in range(test):
	n = int(input())
	p = 1000000007
	print(int(permutation(n, p)))


T = int(input())
inv = 280000002
mod = 1000000007
for i in range(T):
	n = int(input())
	if n % 2 == 0:
		n = n // 2 + 1
		a = 2 * ((pow(26, n, mod) - 1) * inv - 1) % mod
		print(a)
	else:
		n = n // 2 + 2
		a = 2 * ((pow(26, n, mod) - 1) * inv - 1) % mod
		a = (a - pow(26, n - 1, mod)) % mod
		print(a)


(mod, i) = (1000000007, 280000002)
for _ in range(int(input())):
	n = int(input())
	t = (2 * 26 * (pow(26, n // 2, mod) - 1) * i % mod + (n & 1) * pow(26, (n + 1) // 2, mod)) % mod
	print(t)


M = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	ans = 52 * (pow(26, n // 2, M) - 1) * pow(25, M - 2, M)
	if n % 2 == 1:
		ans += pow(26, n // 2 + 1, M)
	print(ans % M)


inverse = 280000002
mod = 1000000007
for _ in range(int(input())):
	N = int(input())
	if N % 2 == 0:
		N = N // 2 + 1
		a = 2 * ((pow(26, N, mod) - 1) * inverse - 1) % mod
		print(a)
	else:
		N = N // 2 + 2
		a = 2 * ((pow(26, N, mod) - 1) * inverse - 1) % mod
		a = (a - pow(26, N - 1, mod)) % mod
		print(a)


MOD = 1000000007

def power(a, b):
	if b == 0:
		return 1
	else:
		temp = power(a, b // 2)
		if b % 2 == 0:
			return temp * temp % MOD
		else:
			return temp * temp * a % MOD

def InverseEuler(t):
	return power(t, MOD - 2)

def aml(n):
	p = n // 2
	temp = 52 * (power(26, p) + MOD - 1) * InverseEuler(25) % MOD
	return temp
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	if n % 2 == 0:
		print(aml(n))
	else:
		l = (n + 1) // 2
		q = (power(26, l) + aml(n)) % MOD
		print(q)


import sys
import math
from queue import Queue
import heapq

def powermod(a, b, n):
	if b == 0:
		return 1 % n
	if b == 1:
		return a % n
	r = powermod(a, b // 2, n)
	r = r * r % n
	if b & 1 == 1:
		r = r * a % n
	return r

def main(n):
	exp = None
	mult = 0
	mod = 10 ** 9 + 7
	if n & 1 == 1:
		exp = (n - 1) // 2
		s = powermod(26, (n + 1) // 2, mod)
		mult = int(s)
	else:
		exp = n // 2
	a = 52 * powermod(25, 1000000005, mod) % mod
	b = (powermod(26, exp, mod) - 1) % mod
	c = mult
	return (a * b % mod + c % mod) % mod
t = int(input())
for i in range(t):
	n = int(input())
	print(main(n))


inv = 280000002
mod = 1000000007

def solve():
	n = int(input())
	if n % 2 == 0:
		print(2 * ((pow(26, n // 2 + 1, mod) - 1) * inv - 1) % mod)
	else:
		print((2 * ((pow(26, n // 2 + 2, mod) - 1) * inv - 1) - pow(26, n // 2 + 1, mod)) % mod)
for i in range(int(input())):
	solve()


from math import ceil
t = int(input())
for i in range(t):
	n = int(input())
	m = 10 ** 9 + 7
	z = 26 * (pow(26, ceil(n / 2), m) % m - 1) * 280000002
	if n % 2 == 0:
		z *= 2
	else:
		c = n - 1
		f = 26 * (pow(26, ceil(c / 2), m) % m - 1 % m) * 280000002
		z += f
	print(z % m)


def get_power(a, N, m, D):
	if N == 0:
		return 1
	elif N == 1:
		return a
	elif N in D:
		return D[N]
	else:
		D[N] = get_power(a, N // 2, m, D) % m * (get_power(a, N - N // 2, m, D) % m) % m
		return D[N]
T = int(input())
ans = []
m = 10 ** 9 + 7
for _ in range(T):
	N = int(input())
	if N % 2 == 0:
		num = 52 % m * ((get_power(26, N // 2, m, {}) - 1) % m) % m
		deno = get_power(25, m - 2, m, {})
		t = num * deno % m
	else:
		N += 1
		num = 52 % m * ((get_power(26, N // 2, m, {}) - 1) % m) % m
		deno = get_power(25, m - 2, m, {})
		t = (num * deno % m - get_power(26, N // 2, m, {})) % m
	ans.append(t)
for i in ans:
	print(i)


t = int(input())
m = 7 + 10 ** 9
den = pow(25, 1000000005, 1000000007)
for i in range(0, t):
	n = int(input())
	t = (n + 1) // 2
	s = 52 * ((pow(26, t, 1000000007) - 1) % m) % m
	s = s * den % m
	if n % 2 == 0:
		print(str(s))
	else:
		print(str((s - pow(26, t, 1000000007)) % 1000000007))


import sys, math, heapq, bisect, random, itertools
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
ints = lambda : list(map(int, input().split()))
p = 10 ** 9 + 7
inf = 10 ** 20 + 7
ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alpha = 'abcdefghijklmnopqrstuvwxyz'
for t in range(int(input())):
	N = int(input())
	n = N // 2
	a = 26
	r = 26
	num = a * (pow(r, n, p) - 1)
	den = pow(r - 1, p - 2, p)
	ans = 2 * num * den % p
	if N % 2:
		ans = (ans + pow(26, n + 1, p)) % p
	print(ans)


mbase = 10 ** 9 + 7
inv_25 = 280000002
t = int(input())
for it in range(t):
	n = int(input())
	m = n // 2
	pow26mp1 = pow(26, m + 1, mbase)
	res = 2 * (pow26mp1 - 26) * inv_25
	if n % 2 == 1:
		res += pow26mp1
	res %= mbase
	print(res)


import math
m = 1000000007
mm = 280000002
a = []
a.append(26)
for i in range(1, 35):
	val = a[i - 1] * a[i - 1] % m
	a.append(val)

def getbin(value):
	s = []
	for i in range(30):
		s.append(str(value % 2))
		value //= 2
	s = s[::-1]
	return ''.join(s)

def getval(index):
	b = getbin(index)
	s = 1
	for i in range(30):
		if b[29 - i] == '1':
			s = s * a[i] % m
	return s
for t in range(int(input())):
	n = int(input())
	x = math.ceil(n / 2)
	if n % 2 == 0:
		val = getval(x)
		val -= 1
		val *= 52
		val *= mm
		val = val % m
		print(val)
	else:
		val = getval(x - 1)
		val -= 1
		val *= 52
		val *= mm
		val = val % m
		val += getval(x)
		val = val % m
		print(val)


mod = 1000000007
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(26)
	elif n == 2:
		print(52)
	else:
		k = -(-n // 2)
		if n % 2 == 0:
			ans = 26 * (1 + 26 * (pow(26, k - 1, mod) - 1) * pow(26 - 1, mod - 2, mod)) + 26 * (1 + 26 * (pow(26, k - 1, mod) - 1) * pow(26 - 1, mod - 2, mod))
		else:
			ans = 26 * (1 + 26 * (pow(26, k - 1, mod) - 1) * pow(26 - 1, mod - 2, mod)) + 26 * (1 + 26 * (pow(26, k - 2, mod) - 1) * pow(26 - 1, mod - 2, mod))
		print(ans % mod)


def topowermod(v, e, m):
	op = 1
	v %= m
	be = bin(e)
	for c in be[2:]:
		op = op * op % m
		if '1' == c:
			op = op * v % m
	return op

def modinv(v, m):
	v %= m
	tb = [(m, 1, 0), (v, 0, 1)]
	while tb[-1][0] > 0:
		q = tb[-2][0] // tb[-1][0]
		nr = list(tb[-2])
		for e in range(3):
			nr[e] -= q * tb[-1][e]
		tb.append(tuple(nr))
	if tb[-2][0] == 1:
		a = tb[-2][2]
		while a < 0:
			a += m
		return a % m
mdl = 1000000007
i25 = modinv(25, mdl)
for _ in range(int(input())):
	n = int(input())
	k = n // 2
	ke = topowermod(26, k + 1, mdl)
	ko = ke
	if 1 == n % 2:
		ko = 26 * ke % mdl
	ans = ((ko - 1 + ke - 1) * i25 + mdl - 2) % mdl
	print(ans)


mdl = 1000000007
i25 = pow(25, mdl - 2, mdl)
for _ in range(int(input())):
	n = int(input())
	k = n // 2 + 1
	ko = ke = pow(26, k, mdl) - 1
	if 1 == n % 2:
		ko = ((ko + 1) * 26 - 1) % mdl
	tot = ((ko + ke) * i25 - 2) % mdl
	if tot < 0:
		tot += mdl
	print(tot)


def exp(a, n):
	if n == 1:
		return a
	elif n % 2:
		temp = exp(a, n // 2)
		return temp % 1000000007 * temp % 1000000007 * a % 1000000007
	else:
		temp = exp(a, n // 2)
		return temp % 1000000007 * temp % 1000000007 % 1000000007

def ans(n):
	if n == 1:
		return 26
	elif n == 2:
		return 52
	if n % 2 == 0:
		temp = exp(26, n / 2)
		return (temp - 1) * 560000006 % 1000000007
	else:
		temp = exp(26, (n + 1) / 2)
		return ((temp - 1) * 560000006 - temp) % 1000000007
t = int(input())
for index in range(0, t):
	n = int(input())
	print(ans(n))


import sys
import math
from time import time
from itertools import permutations, combinations
import collections
import functools
from fractions import gcd, Fraction
import string
import operator
import bisect

class timed(object):

	def __init__(self, func):
		self.func = func

	def __call__(self, *args):
		t1 = time()
		ret = self.func(*args)
		dif_time = time() - t1
		print('%s: returned %s in %f seconds' % (self.func.__name__, ret, dif_time))
		return ret

def comp(f1, f2, *args):
	t1 = time()
	r1 = f1(*args) if f1 is not None else None
	t2 = time()
	r2 = f2(*args) if f2 is not None else None
	t3 = time()
	res = '%5s: %s in %f\n%5s: %s in %f' % (f1.__name__ if f1 is not None else None, r1, t2 - t1, f2.__name__ if f2 is not None else None, r2, t3 - t2)
	if r1 != r2:
		dr = '!! DIFFERENT RESULTS !!'
		res = dr + '\n' + res + '\n' + dr
	print(res)

def alg(i):
	MODULO = 1000000007
	res = 0
	for n in range(1, i + 1):
		K = (n + 1) // 2
		res += pow(26, K, MODULO)
		res %= MODULO
	return res

def alg2(i):
	MODULO = 1000000007
	res = 0
	pow_total = 1
	for n in range(1, i + 1):
		if n % 2 == 1:
			pow_total *= 26
			pow_total %= MODULO
		res += pow_total
		res %= MODULO
	return res
MODULO = 1000000007

def mat_mul(m1, m2):
	x = len(m2[0])
	y = len(m1)
	result = [list([0] * x) for i in range(y)]
	for i in range(len(m1)):
		for j in range(len(m2[0])):
			for k in range(len(m2)):
				result[i][j] += m1[i][k] * m2[k][j]
			result[i][j] %= MODULO
	return result

def mat_exp(m, e):
	assert e > 0
	if e == 1:
		return m
	msq = mat_mul(m, m)
	if e % 2 == 0:
		return mat_exp(msq, e // 2)
	else:
		return mat_mul(m, mat_exp(msq, (e - 1) // 2))

def alg3(i):
	res = 0
	if i == 1:
		return 26
	matrix = [[26, 26], [0, 1]]
	m = [[26], [1]]
	if i % 2 == 0:
		T = (i + 1) // 2
	else:
		T = i // 2
	if T > 1:
		m = mat_mul(mat_exp(matrix, T - 1), [[26], [1]])
	if i % 2 == 1:
		res = 2 * m[0][0] + pow(26, (i + 1) // 2, MODULO)
	else:
		res = 2 * m[0][0]
	return res % MODULO

def main():
	data = sys.stdin
	nb = int(data.readline())
	for icase in range(nb):
		i = int(data.readline().strip())
		res = alg3(i)
		print(res)
main()


import sys
m = 1000000007
mi26 = pow(25, m - 2, m)
sys.stdin.readline()
for line in sys.stdin.read().splitlines(0):
	n = int(line)
	ans = 1
	if n & 1:
		k = n // 2
		ans = (2 * (26 * ((pow(26, k, m) - 1) % m) * mi26) % m % m + pow(26, (n + 1) // 2, m)) % m
	else:
		k = (n + 1) // 2
		ans = 2 * (26 * ((pow(26, k, m) - 1) % m) * mi26) % m % m
	print(ans)


def power(n):
	if n == 0:
		return 1
	else:
		tmp = power(n // 2) % 1000000007 % 1000000007
		if n % 2 == 1:
			return 26 * tmp * tmp % 1000000007
		else:
			return tmp * tmp % 1000000007

def powernext(n):
	if n == 0:
		return 1
	else:
		tmp = powernext(n // 2) % 1000000007 % 1000000007
		if n % 2 == 1:
			return 25 * tmp * tmp % 1000000007
		else:
			return tmp * tmp % 1000000007
a = powernext(1000000005) % 1000000007
t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 1:
		print((power(n // 2 + 1) + 52 * (power(n // 2) - 1) * a) % 1000000007)
	else:
		print(52 * (power(n // 2) - 1) * a % 1000000007)


'__author__' == 'deepak Singh Mehta(learning to code)) '
mod = 1000000007

def pow(n):
	if n == 0:
		return 1
	if n % 2 == 1:
		return 26 * pow(n - 1) % mod
	tmp = pow(n // 2)
	return tmp * tmp % mod
tests = int(input())
for _ in range(tests):
	n = int(input())
	curr = 26 * (pow(n // 2) - 1)
	while curr % 25 != 0:
		curr += mod
	curr //= 25
	curr *= 2
	if n % 2 == 1:
		curr += pow(n // 2 + 1)
	print(curr % mod)