Bob has a string  (S), which is initially empty. In one operation, he can select a lowercase character (a-z) uniformly at random and appends it to S. He then evaluates whether S is a palindrome or not; if it is, he gets 1 point.

Given that Bob performs N operations in total, find the expected no. of points Bob gets.

It is guaranteed that the answer can always be represented as a rational number $\frac{a}{b}$. You must print this number modulo 1000000007. By this we mean that you must print, $a \times b^{-1}$ modulo 1000000007 where $b^{-1}$ denotes the modulo inverse of $b$ with respect to 1000000007.
 
Also observe that 1000000007 is a prime number.

------ Input ------ 

First line of the input will contain T denoting the number of test-cases.For every test case, first line will contain N. 

------ Output ------ 

•	For every test case, print the required answer in a separate line  % 10^{9}+7.

------ Constraints ------ 

$1 ≤ T ≤ 30$
$1 ≤ N ≤ 1000000000$
 
------ Subtasks ------ 

Subtask #1 : (20 points)

1 ≤ T ≤ 3
1 ≤ N≤ 1000

Subtask 2 : (30 points) 

1 ≤ T ≤ 10
1 ≤ N≤ 1000

Subtask #3 : (50 points)

1 ≤ T ≤ 30
1 ≤ N≤ 1000000000

----- Sample Input 1 ------ 
3
2
3
4
----- Sample Output 1 ------ 
576923082
153846156
214497044
----- explanation 1 ------ 
For n = 2, the answer is 27/26 points.  
We have to print this number modulo 1000000007 which equals 27 * 26 $^{-1}$ % 1000000007 = 576923082.

Difficulty: HARD
Tags: Number theory

Probability

Starter code:

Solutions:
import sys
ip = sys.stdin
mod = pow(10, 9) + 7
modinv = lambda x: pow(x, mod - 2, mod)
t = int(ip.readline())

def solve(n):
	ans = 1
	a = pow(26, n, mod)
	d = a
	a = (a - 1) % mod
	a = a * 2 % mod
	mmi1 = modinv(d)
	mmi2 = modinv(25)
	a = a * mmi1 % mod
	a = a * mmi2 % mod
	ans = (a + ans) % mod
	return ans
for _ in range(t):
	n = int(ip.readline())
	res = solve(n // 2)
	if n % 2 == 0:
		last = modinv(pow(26, n // 2, mod))
		res = (res - last) % mod
	print(res)


t = int(input())
e = 10 ** 9 + 7
for _ in range(t):
	n = int(input())
	if n == 1:
		print(1)
	else:
		c = n // 2
		x = 0
		k = pow(26, c * (e - 2), e)
		if n % 2 == 0:
			b = pow(25, e - 2, e)
			a = pow(26, c, e) * 27 % e
			a -= 27
			a = a * b % e
			a = a * k
			print(a % e)
		else:
			b = pow(25, e - 2, e)
			a = pow(26, c, e) * 27 % e
			a -= 2
			a = a * b % e
			a = a * k
			print(a % e)


from fractions import Fraction

def modInverse(a, m):
	g = gcd(a, m)
	if g != 1:
		return -1
	else:
		return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def new(m):
	fra = Fraction(1, 26)
	fra1 = Fraction(pow(fra.numerator, m, mod), pow(fra.denominator, m, mod))
	qs = 1 + 2 * (fra * (fra1 - 1) / (fra - 1))
	if n % 2 == 0:
		qs -= fra1
	temp = modInverse(qs.denominator, mod)
	qs = temp * qs.numerator % mod
	return qs

def calculate(m):
	qs = new(m)
	return qs

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(1)
	else:
		m = n // 2
		print(calculate(m))


import math

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def numerator(n, denom):
	num = int(denom)
	if n % 2 != 0:
		GpSum = (power(26, int(n / 2), 1000000007) + 2 * ((power(26, int(n // 2), 1000000007) - 1) % 1000000007 * power(25, 1000000005, 1000000007)) % 1000000007 % 1000000007) % 1000000007
	else:
		GpSum = ((power(26, int(n / 2), 1000000007) + 2 * 26 * ((power(26, int(n // 2) - 1, 1000000007) - 1) % 1000000007 * power(25, 1000000005, 1000000007)) % 1000000007 % 1000000007) % 1000000007 + 1) % 1000000007
	return int(GpSum)
t = int(input())
while t > 0:
	n = int(input())
	denom = power(26, int(n / 2), 1000000007)
	num = numerator(n, denom)
	print(num * power(denom, 1000000005, 1000000007) % 1000000007)
	t -= 1


m = pow(10, 9) + 7
t = int(input())
while t:
	t = t - 1
	n = int(input())
	n = n + 1
	x = pow(26, int(n / 2), m)
	u = 27 * (x - 1)
	d = pow(x * 25, m - 2, m)
	if n % 2 == 0:
		u = u - 25
	print(u % m * (d % m) % m)


t = int(input())
m = 1000000007
while t > 0:
	n = int(input())
	val = 0
	if n % 2 == 1:
		val = (25 * pow(26, int((n - 1) / 2), m) + (pow(26, int((n - 1) / 2), m) - 1) * 2) % m
		val = val * pow(25 * pow(26, int((n - 1) / 2), m), m - 2, m) % m
	else:
		val = ((25 * pow(26, int((n - 1) / 2), m) + (pow(26, int((n - 1) / 2), m) - 1) * 2) * 26 + 25) % m
		val = val * pow(25 * pow(26, int(n / 2), m), m - 2, m) % m
	print(val)
	t = t - 1


M = 1000000000 + 7

def power(a, n, m):
	res = 1
	a = a % m
	while n > 0:
		if n & 1 == 1:
			res = res * a % m
		n = n >> 1
		a = a * a % m
	return res

def MMI(a, n, m):
	k = power(a, n, m)
	return power(k, m - 2, m)
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print('1')
		continue
	p = 0
	if n % 2 == 0:
		p = (2 * 26 * (power(26, (n - 2) // 2, M) - 1) % M * MMI(25, 1, M) + 1) % M
	else:
		p = 2 * (power(26, (n - 1) // 2, M) - 1) * MMI(25, 1, M) % M
	p += power(26, n // 2, M)
	p = p % M
	x = MMI(26, n // 2, M)
	print(x * p % M)


m = 1000000007

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
for i in range(int(input())):
	n = int(input())
	k = power(26, n // 2, m)
	if n % 2 == 1:
		ans1 = (27 * k - 2) % m
	else:
		ans1 = 27 * (k % m - 1) % m
	ans2 = 25 * k % m
	c = modInverse(ans2, m)
	print(ans1 * c % m)


mod = 10 ** 9 + 7

def inv(num):
	return pow(num, mod - 2, mod)
for _ in range(int(input())):
	n = int(input())
	if n & 1:
		ans = (2 * pow(26, n // 2 + 1, mod) * (pow(26, n // 2, mod) - 1) * inv(25) + pow(26, n, mod)) % mod * inv(pow(26, n, mod))
	else:
		ans = pow(26, n // 2, mod) * 27 * (pow(26, n // 2, mod) - 1) * inv(25) % mod * inv(pow(26, n, mod))
	print(ans % mod)


n = int(input())
for _ in range(n):
	x = int(input())
	if x == 1:
		print(1)
	else:
		m = 1000000007
		if x % 2 == 1:
			offset = (x - 1) // 2
			a = (27 * pow(26, offset, m) % m - 2) % m
			b1 = 25 * pow(26, offset, m) % m
			print(a * (pow(b1, m - 2, m) % m) % m)
		else:
			offset = x // 2
			a = (27 * pow(26, offset, m) % m - 27) % m
			b1 = 25 * pow(26, offset, m) % m
			print(a * (pow(b1, m - 2, m) % m) % m)


import math
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	else:
		ans = 1
		p = n // 2
		k = (pow(26, p, mod) % mod - 1 + mod) % mod
		k = k * pow(25, mod - 2, mod) % mod
		k = k % mod * 2 % mod % mod
		if (n + 1) % 2 == 1:
			k = (k % mod - 1 + mod) % mod
		m = n
		m //= 2
		ans = ans % mod + k * pow(pow(26, m, mod), mod - 2, mod) % mod
		print(ans % mod)


import sys
import math
mod = 1000000007

def nospace(l):
	ans = ''.join((str(i) for i in l))
	return ans
t = int(input())
fixed = 1 + 2 * pow(25, mod - 2, mod)
f26or = pow(26, mod - 2, mod)
f25or = pow(25, mod - 2, mod)
for tt in range(t):
	n = int(input())
	ans = fixed
	if n % 2:
		k = n // 2
		invv = pow(f26or, k, mod)
		invv *= f25or
		invv %= mod
		invv *= 2
		invv *= -1
		invv %= mod
		ans += invv
		ans %= mod
		print(ans)
	else:
		k = n // 2
		invv = pow(f26or, k, mod)
		invv *= f25or
		invv %= mod
		invv *= 27
		invv *= -1
		invv %= mod
		ans += invv
		ans %= mod
		print(ans)


MOD = 1000000007
inv26 = pow(26, MOD - 2, MOD)
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		k = n // 2
		numer = 2 * pow(26, k, MOD) - 2
		numer %= MOD
		denom = 25 * pow(26, k - 1, MOD) % MOD
		frac = numer * pow(denom, MOD - 2, MOD) % MOD
		ans = frac - 1 + pow(inv26, k, MOD)
		ans %= MOD
		print(ans)
	else:
		k = n // 2
		numer = 2 * pow(26, k + 1, MOD) - 2
		numer %= MOD
		denom = 25 * pow(26, k, MOD) % MOD
		frac = numer * pow(denom, MOD - 2, MOD) % MOD
		ans = frac - 1
		ans %= MOD
		print(ans)


t = int(input())
p = int(1000000000.0 + 7)
for _ in range(t):
	n = int(input())
	m = n // 2
	ser_num = pow(26, m + 1, p) - 1
	ser_den = pow(25, p - 2, p)
	ser = 2 * (ser_num * ser_den) % p - pow(26, m, p)
	num = ser if n & 1 else ser - 1
	den = pow(26, m, p)
	den = pow(den, p - 2, p)
	print(num * den % p)


m = 1000000007

def extended_gcd(aa, bb):
	(lastremainder, remainder) = (abs(aa), abs(bb))
	(x, lastx, y, lasty) = (0, 1, 1, 0)
	while remainder:
		(lastremainder, (quotient, remainder)) = (remainder, divmod(lastremainder, remainder))
		(x, lastx) = (lastx - quotient * x, x)
		(y, lasty) = (lasty - quotient * y, y)
	return (lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1))

def modinv(a):
	(g, x, y) = extended_gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m

def point(n):
	if n % 2:
		return modinv(pow(26, (n - 1) // 2, m))
	else:
		return modinv(pow(26, n // 2, m))

def points(n):
	if n % 2:
		return (1 + 2 * modinv(25) * (pow(26, n // 2, m) - 1) * modinv(pow(26, n // 2, m)) % m) % m
	else:
		return (1 + 2 * modinv(25) * (pow(26, (n - 1) // 2, m) - 1) * modinv(pow(26, (n - 1) // 2, m)) % m + modinv(pow(26, n // 2, m))) % m
t = int(input())
while t:
	n = int(input())
	print(points(n) % m)
	t -= 1