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: interview

Starter code:

Solutions:
# cook your dish here
def permutation(n,p):
    r=26
    if n==1:
        return 26
    elif n==2:
        return 52
    elif n==3:
        return 728
    else:
        if 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)))

def permutation(n,p):
    r = 26
    if n == 1:
        return 26
    elif n == 2:
        return 52
    elif n == 3:
        return 728
    else:
        if 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
for _ in range(int(input())):
    n = int(input())
    p = 1000000007
    print(int(permutation(n,p)))

def permutation(n,p):
    r = 26
    if n == 1:
        return 26
    elif n == 2:
        return 52
    elif n == 3:
        return 728
    else:
        if n%2 == 0:
            return ((2*(bin_expo(r,((n//2)+1),p)-r)%p*bin_expo(25,1000000005,p)%p)%p)%p
        else:
            n = n+1
            return ((2*((bin_expo(r,(n//2+1),p)-r)%p*bin_expo(r-1,1000000005,p)))%p- bin_expo(26,n//2,p)%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
for _ in range(int(input())):
    n = int(input())
    p = 1000000007
    print(int(permutation(n,p)))

inv = 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) * 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)

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)

# cook your dish here

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
    else:
        if 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))



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
    else:
        if 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 = 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))



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)





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)

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)


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)