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

Starter code:

Solutions:
# cook your dish here
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)



# cook your dish here
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)



# cook your dish he# cook your dish here
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)



# cook your dish here
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)


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)

 


# cook your dish here
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,(10**9+7))
     ans*= (26+25*len(S))
  
     ans = ans%(10**9 + 7)
    print(ans)
 
  


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,(10**9+7))
     ans*= (26+25*len(S))
  
     ans = ans%(10**9 + 7)
    print(ans)
  
    


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 , 10**9+7)
     ans*= (26+25*len(S))
     ans = ans%(10**9 + 7)
    print(ans)
  
    


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)
  
    


# cook your dish here
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

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)
  


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

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")


# cook your dish here
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")