Dustin, is the head of an Intelligence agency. He wants to send a secret message S$S$ to his colleague.The message is a single word consisting of only lowercase english letters but he decides to encrypt the message for security reasons. He makes a string M$M$ of length N$N$, such that after deleting a substring of non-zero length from M$M$, the remaining string is S$S$.
Calculate the number of all such possible strings he can form.

-----Input:-----
- First line will contain T$T$, number of testcases. Then the testcases follow.
- For each testcase the there is a single line which contains an integer, N$N$ and then a string S$S$.

-----Output:-----
For each testcase, output the number of possible strings modulo 109+7$10^9+7$.

-----Constraints-----
- 1≤T≤50$1 \leq T \leq 50$
- 1≤N≤1018$1 \leq N \leq 10^{18}$
- 1≤|S|≤105$1 \leq |S| \leq 10^5$
- S$S$ can contain only lowercase English letters.

-----Sample Input:-----
2

3 a

3 ab     

-----Sample Output:-----
1326

76

Difficulty: VERY_HARD
Tags: String algorithms

Combinatorics

Data structures

Mathematics
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(n, s) = input().split()
	N = int(n)
	r = N - len(s)
	count = 0
	if N > len(s):
		count = pow(26, r - 1, 10 ** 9 + 7)
		count *= 26 + 25 * len(s)
		count = count % (10 ** 9 + 7)
	print(count)


for _ in range(int(input())):
	(n, s) = input().split()
	n = int(n)
	l = len(s)
	m = 1000000007
	if n > l:
		ans = pow(26, n - l - 1, m)
		ans *= 26 + 25 * l
		print(ans % m)
	else:
		print('0')


for i in range(int(input())):
	L = input().split()
	N = int(L[0])
	S = L[1]
	Q = N - len(S)
	ans = 0
	if N > len(S):
		ans = pow(26, Q - 1, 1000000007)
		ans *= 26 + 25 * len(S)
		ans = ans % (10 ** 9 + 7)
	print(ans)


T = int(input())
for _ in range(T):
	(N, S) = input().split()
	N = int(N)
	M = len(S)
	mod = 10 ** 9 + 7
	if M >= N:
		print(0)
	else:
		f = pow(26, N - M, mod)
		g = M * 25 * pow(26, N - M - 1, mod)
		print((f + g) % mod)


mod = 10 ** 9 + 7

def binpow(a, b):
	b %= mod - 1
	ans = 1
	while b > 0:
		if b & 1:
			ans = ans * a % mod
		a = a * a % mod
		b >>= 1
	return ans
T = int(input())
for _ in range(T):
	(n, s) = map(str, input().split())
	n = int(n)
	dif = n - len(s)
	total = 0
	if dif > 0:
		total = (binpow(26, dif) * (len(s) + 1) % mod - binpow(26, dif - 1) * len(s) % mod + mod) % mod
	print(total)


t = int(input())
while t > 0:
	(n, s) = map(str, input().split())
	n = int(n)
	if n <= len(s):
		print('0')
	else:
		m = pow(26, n - len(s) - 1, 1000000007)
		m = m * (26 + 25 * len(s))
		print(m % 1000000007)
	t = t - 1


x = 7 + 10 ** 9
for i in range(int(input())):
	(n, s) = input().split()
	n = int(n)
	l = len(s)
	if n > l:
		p = pow(26, n - l - 1, x)
		p *= 25 * l + 26
		print(p % x)
	else:
		print('0')


def make_int(x):
	try:
		x = int(x)
	except:
		pass
	return x

def modular_pow(base, exponent, modulus):
	if modulus == 1:
		return 0
	result = 1
	base = base % modulus
	while exponent > 0:
		if exponent % 2 == 1:
			result = result * base % modulus
		exponent >>= 1
		base = base * base % modulus
	return result
mod = 7 + 10 ** 9
for t in range(int(input())):
	(n, s) = map(make_int, input().split())
	l = len(s)
	if n - l > 0:
		total = modular_pow(26, n - l, mod) * (l + 1) % mod % mod
		substraction = modular_pow(26, n - l - 1, mod) * (l % mod) % mod
		substraction = substraction % mod
		answer = (total - substraction) % mod
	else:
		answer = 0
	print(answer)