Problem:
 Score: 600 points    Problem Statement  How many strings can be obtained by applying the following operation on a string S exactly K times: "choose one lowercase English letter and insert it somewhere"?  The answer can be enormous, so print it modulo (10^9+7) .      Constraints   K is an integer between 1 and 10^6 (inclusive).  S is a string of length between 1 and 10^6 (inclusive) consisting of lowercase English letters.         Input  Input is given from Standard Input in the following format:  K  S       Output  Print the number of strings satisfying the condition, modulo (10^9+7) .        Sample Input 1 5
oof      Sample Output 1 575111451  For example, we can obtain proofend , moonwolf , and onionpuf , while we cannot obtain oofsix , oofelevennn , voxafolt , or fooooooo .       Sample Input 2 37564
whydidyoudesertme      Sample Output 2 318008117

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))



def fast_pow(num, kata, mod):
    if kata == 0:
        return 1

    res = 1
    while kata > 0:
        if kata & 1 == 1:
            res = res * num % mod
        num = num * num % mod

        kata >>= 1
    return res


def choose(n, r, MOD):
    res = 1
    fac = 1
    for i in range(r):
        res *= n - i
        res %= MOD
        fac *= i + 1
        fac %= MOD
    return res * fast_pow(fac, MOD - 2, MOD) % MOD



def prepare(n, MOD):
    
    f = 1
    factorials = [1]  
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    
    inv = pow(f, MOD - 2, MOD)
    
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def main():
    k = ni()
    s = input()
    l = len(s)

    
    facts, invs = prepare(k + l, MOD)

    ans = 0
    for ki in range(k + 1):
        tmpa = fast_pow(25, k - ki, MOD)
        tmpb = fast_pow(26, ki, MOD)
        tmpc = facts[k - ki + l - 1] * invs[l - 1] * invs[k - ki + l - 1 - (l - 1)] % MOD
        tmpd = (tmpa * tmpb * tmpc) % MOD
        ans += tmpd
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class Comb:
    def __init__(self, N):
        F = [1] * (N + 1)
        for i in range(N):
            F[i + 1] = (i + 1) * F[i] % mod

        self.d_inv = {}
        self.d_comb = {}
        self.F = F

    def inv(self, a):
        if a not in self.d_inv:
            self.d_inv[a] = pow(a, mod - 2, mod)
        return self.d_inv[a]

    def comb(self, a, b):
        if (a, b) not in self.d_comb:
            self.d_comb[(a, b)] = (self.F[a] * self.inv(self.F[a - b]) * self.inv(self.F[b])) % mod
            self.d_comb[(a, a - b)] = self.d_comb[(a, b)]
        return self.d_comb[(a, b)] 


def main():
    K = int(input())
    S = input().strip()

    F25 = [1] * (K + 2)
    F26 = [1] * (K + 2)
    T = [1] * (K + 2)
    for i in range(K + 1):
        F25[i + 1] = (25 * F25[i]) % mod
        F26[i + 1] = (26 * F26[i]) % mod
        if i != 0:
            T[i] = pow(i, mod - 2, mod)

    r = 1
    res = 0
    for k in range(K + 1):
        res += ((F25[k] * F26[K - k]) % mod * r) % mod
        r *= (len(S) - 1 + k + 1)
        r %= mod
        r *= T[k + 1]
        r %= mod
        res %= mod
     
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    mod=1000000007
    inv=lambda x: pow(x,mod-2,mod)
    k=int(input())
    s=input().strip()
    l=len(s)
    
    n=k+l
    Fact=[1] 
    for i in range(1,n+1):
        Fact.append(Fact[i-1]*i%mod)
    Finv=[0]*(n+1) 
    Finv[-1]=inv(Fact[-1])
    for i in range(n-1,-1,-1):
        Finv[i]=Finv[i+1]*(i+1)%mod
    def comb(n,r):
        if n<r:
            return 0
        return Fact[n]*Finv[r]*Finv[n-r]%mod

    ans=0
    p=1
    for i in range(l,l+k+1)[::-1]:
        ans+=comb(l+k,i)*p
        ans%=mod
        p*=25
        p%=mod
    print(ans)
    
if __name__=='__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

K=int(input())
S=input()

def COMinit(n,MOD):
    fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,n+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,(n+1)):
        fac[i]=fac[i-1]*i%MOD
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i]=finv[i-1]*inv[i]%MOD
    return fac,finv,inv

fac,finv,inv=COMinit(3*10**6,MOD)

def COM(n, k, MOD=MOD):
    if n<k or n<0 or k<0:
        return 0
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD

dp=[[0]*(K+len(S)+1) for _ in range(2)]
for i in range(len(S)-1,K+len(S)+1):
    dp[0][i]=COM(i,i-len(S)+1)*pow(25,i-len(S)+1,MOD)
dp[1][len(S)]
for i in range(K+len(S)):
    dp[1][i+1]=dp[1][i]*26+dp[0][i]
    dp[1][i+1]%=MOD
print(dp[1][-1])

Solution (Python):
n=int(input())
s=input()

mod=10**9+7
ruijo_5=[1]
ruijo_6=[1]

lim=n+len(s)+10

for i in range(n):
    ruijo_5.append(ruijo_5[i]*25%mod)
    ruijo_6.append(ruijo_6[i]*26%mod)




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


factorial = [1]
for i in range(1, lim):
    factorial.append(factorial[i-1]*i%mod)

inverseFactorial = [0] * lim
inverseFactorial[lim-1] = power(factorial[lim-1], mod-2)
for i in range(lim-2, -1, -1):
    inverseFactorial[i] = inverseFactorial[i+1] * (i+1) % mod

def combi(i, j):
    return factorial[i] * inverseFactorial[j] * inverseFactorial[i-j] % mod





kai=len(s)-1

s=0

for i in range(n+1):
    
    tasu=combi(kai+i,i)*ruijo_5[i]%mod
    tasu*=ruijo_6[n-i]
    tasu%=mod
    s+=tasu
    s%=mod

print(s)

Solution (Python):
def cmb(n, r, mod):
  if ( r<0 or r>n ):
    return 0
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % mod
mod = 10**9+7 
N = 2*10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 
for i in range( 2, N + 1 ):
  g1.append( ( g1[-1] * i ) % mod )
  inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
  g2.append( (g2[-1] * inverse[-1]) % mod )
k = int(input())
s = str(input())
l = len(s)
ans = 0
def power(a,n):
  ans = 1
  while n:
    if n%2:
      ans = (ans*a)%mod
    a = (a*a)%mod
    n >>= 1
  return ans%mod  
y = 1
for i in range(l,l+k+1):
  x = power(26,l+k-i)
  ans = (ans+ x*y*cmb(i-1,l-1,mod))%mod
  y = (y*25)%mod
print(ans)

Solution (Python):


K = int(input())
S = len(input())

mod = 10**9+7
N = K+S


inverse = [0, 1]
for i in range(2, N+1):
    inverse.append((-inverse[mod%i]*(mod//i))%mod)


factorial = [1, 1]
factorial_inv = [1, 1]
for i in range(2, N+1):
    factorial.append((factorial[-1]*i)%mod)
    factorial_inv.append((factorial_inv[-1]*inverse[i])%mod)

answer = 0
pow = -1
for i in range(K+1):
    if pow == -1:
        pow = 1
    else:
        pow = (pow*25)%mod
    answer = (answer+pow*factorial[N]*factorial_inv[i]*factorial_inv[N-i])%mod
print(answer)

Solution (Python):
class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


mod = 10 ** 9 + 7
comb = Combination(2 * 10 ** 6 + 10, mod)

K = int(input())
S = input()
N = len(S)

ans = 0
for i in range(K + 1):
    res = K - i
    right = pow(26, res, mod)
    pos = comb(N - 1 + i, i)
    cnt = pow(25, i, mod)
    tmp = right * pos % mod * cnt % mod
    ans = (ans + tmp) % mod
print(ans)

Solution (Python):
mod = 10**9 + 7  


def table():
    k = 2 * 10**6 + 5  
    fac = [1] * k
    finv = [1] * k
    inv = [0] * k
    inv[1] = 1
    for i in range(2, k):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv


fac, finv = table()


def comb(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


k = int(input())
s = input()
n = len(s) - 1
ans = 1
for i in range(k + 1):
    x = pow(26, k - i, mod) * pow(25, i, mod) % mod
    ans += (comb(n + i, i) * x)
    ans %= mod
print((ans - 1) % mod)

Solution (Python):
def cmb(n, r, mod):
  if ( r<0 or r>n ):
    return 0
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % mod
mod = 10**9+7 
N = 2*10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 
for i in range( 2, N + 1 ):
  g1.append( ( g1[-1] * i ) % mod )
  inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
  g2.append( (g2[-1] * inverse[-1]) % mod )
k = int(input())
s = str(input())
l = len(s)
ans = 0
def power(a,n):
  ans = 1
  while n:
    if n%2:
      ans = (ans*a)%mod
    a = (a*a)%mod
    n >>= 1
  return ans%mod  
y = 1
for i in range(l,l+k+1):
  x = power(26,l+k-i)
  ans = (ans+ x*y*cmb(i-1,l-1,mod))%mod
  y = (y*25)%mod
print(ans)

Solution (Python):
k = int(input())
s = input()
n = len(s)

mod = 10**9 + 7



max = 2 * 10**6 + 100
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,max):
      fac[i] = fac[i-1]* i% mod
      inv[i] = mod - inv[mod%i] * (mod // i) % mod
      finv[i] = finv[i-1] * inv[i] % mod

comInit(max)


def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 0
ex25 = [1] * (k+1)
ex26 = [1] * (k+1)
for i in range(1,k+1):
    ex25[i] = (ex25[i-1] * 25)%mod
    ex26[i] = (ex26[i-1] * 26)%mod

for i in range(k+1):
    j = k-i
    tmp = pow(25,i,mod) * com(n+i-1,i) * pow(26,j,mod)
    tmp = ex25[i] * com(n+i-1,i) * ex26[j]
    ans = (ans+tmp)%mod

print(ans)

Solution (Python):
k=int(input())
s=input()
l=len(s)

n=k+l
mod=10**9+7
fac = [1, 1]  
finv = [1, 1]  
inv = [0, 1]  

for i in range(2, n + 1):
    fac.append((fac[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    finv.append((finv[-1] * inv[-1]) % mod)


def comb(n, r, mod):
    if n < r or r < 0:
        return 0
    elif r==0 or r==n:
        return 1
    else:
        return fac[n] * finv[r] * finv[n - r] % mod
print( sum( (comb(k+l,m,mod) * pow(25,m,mod))%mod for m in range(k+1) )%mod )

Solution (Python):
class Combination:
    def __init__(self, n, mod):
        self.mod = mod

        
        l = [1]
        num = 1
        for i in range(1, n+1):
            num *= i
            num %= mod
            l.append(num)
        self.fac = l.copy()

        
        num = pow(num, mod-2, mod)
        l = [1 for i in range(n+1)]
        l[n] = num
        for i in range(n-1, 0, -1):
            num *= i + 1
            num %= mod
            l[i] = num
        self.rec = l.copy()

    
    def comb(self, n, r):
        return self.fac[n] * self.rec[r] * self.rec[n - r] % self.mod

mod = 10**9 + 7

k = int(input())
s = input()
n = len(s)

c = Combination(k + n, mod)

pow25 = [1]
pow26 = [1]
for _ in range(k):
    pow25.append(25 * pow25[-1] % mod)
    pow26.append(26 * pow26[-1] % mod)

ans = 0
for i in range(k+1):
    ans += c.comb(n+i-1, i) * pow25[i] * pow26[k-i]
    ans %= mod

print(ans)

Solution (Python):
n = int(input())
s = input()
l = len(s)
mod = 10**9 + 7

now = 1
for _ in range(n+l):
  now *= 25
  now %= mod

def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    x -= mod % x
  return y
ans = 0

for i in range(n+l):
  now *= (n+l-i)
  now *= inv(i+1)
  now *= inv(25)
  now %= mod
  if i+1 >= l:
    ans += now
    ans %= mod
  
print(ans)

Solution (Python):
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math


MOD = 10 ** 9 + 7




class Combination:
    def __init__(self, mod=10**9+7, n=202020):
        self.f = [0] * n
        self.rf = [0] * n
        self.inv = [0] * n
        self.f[0], self.f[1] = 1, 1
        self.rf[0], self.rf[1] = 1, 1
        self.inv[1] = 1
        self.MOD = mod
        for i in range(2, n):
            self.f[i] = (self.f[i - 1] * i) % self.MOD
            self.inv[i] = (-self.inv[self.MOD % i] * (self.MOD // i)) % self.MOD
            self.rf[i] = (self.rf[i - 1] * self.inv[i]) % self.MOD

    def __call__(self, n, r):
        return (self.f[n] * self.rf[r] * self.rf[n - r]) % self.MOD


C = Combination(mod=MOD, n=2020202)

k = int(input())
s = input()

ans = 1
p = 1
for i in range(len(s), len(s)+k):
    ans = (ans*26 + C(i, len(s)-1)*pow(25, p, MOD)) % MOD
    p += 1

print(ans)

Solution (Python):
K=int(input())
S=input()
M=len(S)
N=K+M
mod=10**9+7
ans=pow(26,N,mod)
class Data():
    def __init__(self):
        self.power=1
        self.rev=1     
class Combi():
    def __init__(self,N,mod):
        self.lists=[Data() for _ in range(N+1)]
        self.mod=mod  
        for i in range(2,N+1):
            self.lists[i].power=((self.lists[i-1].power)*i)%self.mod
        self.lists[N].rev=pow(self.lists[N].power,self.mod-2,self.mod)
        for j in range(N,0,-1):
            self.lists[j-1].rev=((self.lists[j].rev)*j)%self.mod

    def combi(self,K,R):
        if K<R:
            return 0
        else:
            return ((self.lists[K].power)*(self.lists[K-R].rev)*(self.lists[R].rev))%self.mod
        
c=Combi(2*10**6,mod)
for i in range(M):
    ans-=c.combi(N,i)*pow(25,N-i,mod)
    ans%=mod
print(ans%mod)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

k=int(input())
s=input()
n=len(s)


def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 10**6*2+10
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )




ans=0
for i in range(n):
    ans+=cmb(n+k,i)*pow(25,n+k-i,mod)
print((pow(26,n+k,mod)-ans)%mod)

Solution (Python):
K = int(input())
S = input()
N = len(S)
mod = 7 + 10 ** 9
fact = [1] * (N + K + 1)
for i in range(1, N + K + 1): fact[i] = (fact[i-1] * i) % mod
revfact = [1] * (N + K + 1)
revfact[N + K] = pow(fact[N + K], mod - 2, mod)
for i in reversed(range(1, N + K)):
    revfact[i] = ((i + 1) * revfact[i + 1]) % mod

def comb(n, r):
    return (fact[n] * revfact[n-r] * revfact[r]) % mod

def solve():
    ans = 0
    for k in range(K + 1):
        leftMost = pow(26, k, mod) 
        right = (pow(25, K - k, mod) * comb(N + K - k - 1, N - 1)) % mod
        ans += (leftMost * right) % mod
        ans %= mod
    print(ans)


    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
from collections import defaultdict, deque
import math








input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7

def divide(k):
    return pow(k, MOD-2, MOD)


def make_nck(n):
    ret = [1]
    for i in range(1, n+1):
        ret.append((ret[-1] * (n + 1 - i) * divide(i)) % MOD)

    
    return ret

def make_nigojyo(n):
    ret = [1]

    for i in range(1, n+1):
        ret.append((ret[-1] * 25) % MOD)

    
    return ret


def solve():
    K = getN()
    S = getS()
    l = len(S)
    nck = make_nck(K + len(S))
    nigojyo = make_nigojyo(K + l)
    
    
    
    
    
    
    ans = 0

    for i in range(l + K - l + 1):
        ans += (nigojyo[i]) * nck[i]
        ans %= MOD
        

    print(ans)



def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    
    solve()

Solution (Python):
class Combination:
    def __init__(self, n, mod):
        self.mod = mod

        
        l = [1]
        num = 1
        for i in range(1, n+1):
            num *= i
            num %= mod
            l.append(num)
        self.fac = l.copy()

        
        num = pow(num, mod-2, mod)
        l = [1 for i in range(n+1)]
        l[n] = num
        for i in range(n-1, 0, -1):
            num *= i + 1
            num %= mod
            l[i] = num
        self.rec = l.copy()

    
    def comb(self, n, r):
        return self.fac[n] * self.rec[r] * self.rec[n - r] % self.mod

mod = 10**9 + 7

k = int(input())
s = input()
n = len(s)

c = Combination(k + n, mod)

ans = 0
for i in range(k+1):
    ans += c.comb(n + i - 1, i) * pow(25, i, mod) * pow(26, k-i, mod)
    ans %= mod

print(ans)

Solution (Python):
K = int(input())
S = input()
L = len(S)
MOD = 10 ** 9 + 7

factorials = [1]
fact_invs = [1]
for i in range(1, L+K+1):
    factorials.append((factorials[-1]*i) % MOD)
    fact_invs.append(pow(factorials[-1], MOD-2, MOD))

ans = 1
for i in range(K):
    b = L + i
    a = L - 1
    nans = factorials[b]
    nans *= fact_invs[a]
    nans %= MOD
    nans *= fact_invs[b-a]
    nans %= MOD
    nans *= pow(25, b-a, MOD)
    nans %= MOD
    nans += ans * 26
    nans %= MOD
    ans = nans
print(ans)

Solution (Python):
k=int(input())
s=len(input())
mod=10**9+7
fact=[1]*(k+s+1)
inv=[1]*(k+s+1)
for i in range(2,k+s+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(k+s,1,-1):
    inv[i-1]=inv[i]*i%mod
def comb(x,y):return fact[x]*inv[y]%mod*inv[x-y]%mod if x>=y>=0 else 0
ans=pow(26,k+s,mod)
for i in range(s):
    ans=(ans-pow(25,k+s-i,mod)*comb(k+s,i)%mod)%mod
print(ans)

Solution (Python):
def examA():
    S = SI()
    if S in alphabet:
        ans = "a"
    else:
        ans = "A"
    print(ans)
    return

def examB():
    N, K = LI()
    P = LI()
    P.sort()
    ans = sum(P[:K])
    print(ans)
    return

def examC():
    N = I()
    ans = ""
    while(N>0):
        N -= 1
        ans += alphabet[N%26]
        N //= 26
        if N==0:
            break
    print(ans[::-1])
    return

def examD():
    N = I()
    A = LI()
    D = defaultdict(int)
    for a in A:
        D[a] += 1
    S = sum(A)
    q = I()
    ans = [0]*q
    for i in range(q):
        a, b = LI()
        if not a in D:
            ans[i] = S
            continue
        S += (b-a)*D[a]
        D[b] += D[a]
        D[a] = 0
        ans[i] = S

    for v in ans:
        print(v)
    return

def examE():
    N = I()
    A = LI()
    S = 0
    for a in A:
        S ^= a
    
    ans = [0]*N
    for i in range(N):
        ans[i] = S^A[i]
    print(" ".join(map(str,ans)))
    return

def examF():
    class combination():
        
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod

    K = I()
    S = SI()
    N = len(S) + K
    C = combination(N,mod)
    P = [1]*(K+1)
    for i in range(K):
        P[i+1] = P[i]*26%mod
    v = 0
    prev = S[0]
    for s in S[1:]:
        if prev!=s:
            v += 1
            prev = s
    v = len(S)-1
    cnt = 0
    
    for i in range(K+1):
        if i%2==0:
            cnt += C.comb(N,N-K+i)*P[K-i]*C.comb(v+i,v)
            cnt %= mod
        else:
            cnt -= C.comb(N,N-K+i)*P[K-i]*C.comb(v+i,v)
            cnt += mod**3
            cnt %= mod
        
        
        
        
            

    ans = cnt
    print(ans)
    return

def examF2():
    class combination():
        
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod

    K = I()
    S = SI()
    N = len(S) + K
    C = combination(N,mod)
    P = [1]*(K+1)
    for i in range(K):
        P[i+1] = P[i]*25%mod
    v = 0
    prev = S[0]
    for s in S[1:]:
        if prev!=s:
            v += 1
            prev = s
    cnt = 0
    cnt = P[K]*C.comb(N,K)
    
    ans = cnt
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
"""

部分文字列にSを含む長さ|S|+Kの文字列の数
dp[i][j] = i文字目まで見てj文字目まで含んでる文字列の数
dp[i][j] = dp[i-1][j] * 25 + dp[i-1][j-1]

dp[0][0] = 1
dp[|S|+K][|S|]が欲しい

1に
1かける/25を掛ける
をそれぞれ |S|回、K回やった組み合わせの総和


"""
def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): 

    return fac[n] * inv[n-r] * inv[r] % mod

K = int(input())

S = input()
ls = len(S)

mod = 10**9+7

fac,inv = modfac(3*(10**6),mod)

ans = 0

for i in range(ls,ls+K+1):
    down = i-ls
    rem = K-down
    
    now = pow(26,rem,mod) * pow(25,down,mod) * modnCr(i-1,ls-1,mod,fac,inv) % mod
    
    ans += now
    ans %= mod

print (ans % mod)

Solution (Python):
MOD = 10**9 + 7

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  
        return self.ncr(n + r - 1, n - 1)

K = int(input())
S = input()
N = len(S)

comb = Combination(N + K + 100)

ans = 0
for l in range(K + 1):
    r = K - l
    ans += pow(25, l, MOD) * comb.nhr(N, l) * pow(26, r, MOD)
    ans %= MOD

print(ans)

Solution (Python):
class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0



K = int(input())
S = list(input())
s = len(S)

N = K + s

MOD = 10 ** 9 + 7

C = Factorial(N + 10, MOD)

lst26 = [1] * (K + 2)
lst25 = [1] * (K + 2)
for i in range(K + 1):
    lst26[i + 1] = (lst26[i] * 26) % MOD
    lst25[i + 1] = (lst25[i] * 25) % MOD

ans = 0
for x in range(K + 1):
    tmp = ((C.factorial(s - 1 + K - x) * C.ifactorial(s - 1)) % MOD) * C.ifactorial(K - x)
    tmp %= MOD
    tmp = (tmp * lst26[x]) % MOD
    tmp = (tmp * lst25[K - x]) % MOD
    ans = (ans + tmp) % MOD

print (ans)

Solution (Python):
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  




mod = 10**9 + 7
N = 10 ** 6 + 1  
inverse = [0, 1]  

for i in range(2, N + 1):
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)

K = ni()
S = ns()
s_len = len(S)
mod = 10 ** 9 + 7
ans = 0

total = K + s_len

rui = 1

cmb = 1

for i in range(total, s_len - 1, -1):
    
    ans = (ans + cmb * rui) % mod
    
    rui = (rui * 25) % mod
    cmb = (cmb * i * inverse[total - i + 1]) % mod
print(ans)

Solution (Python):
K = int(input())
S = input()

mod = 10 ** 9 + 7

N = len(S) + K

power = [1]
fac = [1]
inv = [1]
for i in range(1, N + 10) :
  power.append(power[-1] * 25 % mod)
  fac.append(fac[-1] * i % mod)
  
inv = [pow(fac[-1], mod - 2, mod)]
for i in range(N + 10 - 1, 0, -1) :
  inv.append(inv[-1] * i % mod)
inv = inv[::-1]

def comb(n, r) :
  if r == 0 :
    return 1
  return fac[n] * inv[n - r] * inv[r] % mod
  
ret = pow(26, N, mod)
for i in range(len(S)) :
  ret -= power[N - i] * comb(N, i) % mod
  ret %= mod
  
print(ret)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    k = int(ipt())
    s = input()
    ls = len(s)
    mod = 10**9+7
    
    N = 2*10**6
    g1 = [1, 1] 
    g2 = [1, 1] 
    inverse = [0, 1] 
    def cmb(n,r,mod):
        if r<0 or r>n :
            return 0
        r = min(r,n-r)
        return g1[n]*g2[r]*g2[n-r]%mod
    for i in range(2,N+1):
        g1.append((g1[-1]*i)%mod)
        inverse.append((-inverse[mod % i]*(mod//i))%mod)
        g2.append((g2[-1]*inverse[-1])%mod)

    ans = 0
    s25 = [1]
    s26 = [1]
    for i in range(k+1):
        s25.append(s25[-1]*25%mod)
        s26.append(s26[-1]*26%mod)

    for i in range(ls):
        ans = (ans+s25[k]*cmb(k+i-1,i,mod)%mod)%mod
    for i in range(1,k+1):
        ans = (ans+s25[k-i]*s26[i]%mod*cmb(k+ls-1-i,ls-1,mod)%mod)%mod
    print(ans)

    return

if __name__ == '__main__':
    main()

Solution (Python):
from functools import reduce
def comb(n, max_k, mod):
    """
    (n,k) := n個からk個選ぶ組み合わせ
    k = 0~max_Kまでを計算して返す
    """
    res = [1]*(max_k+1)
    t = 1
    for i in range(max_k+1):
        res[i] *= t
        t *= n-i
        t %= mod

    n = reduce(lambda x,y: (x*y)%mod, range(1,max_k+1), 1)
    n = pow(n,-1, mod)

    for i in reversed(range(max_k+1)):
        res[i] *= n
        res[i] %= mod
        n *= i
        n %= mod
    return res

MOD = 10**9+7

K = int(input())
N = len(input())

res = 0
x = 1

com = comb(N+K, K, MOD)

for c in com:
    res += x*c
    res %= MOD
    x *= 25
    x %= MOD

print(res)

Solution (Python):
K=int(input())
S=input()
n=K+len(S)
MAX=2000000
fac=[0]*MAX
finv=[0]*MAX
inv=[0]*MAX
MOD=10**9+7

def COMinit():
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,MAX):
      fac[i] = fac[i-1] * i % MOD
      inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
      finv[i] = finv[i - 1] * inv[i] % MOD


def comb(n,k):
  if (n < k):
    return 0
  if (n < 0 or k < 0):
    return 0
  else:
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

COMinit()
com=1
q=(26**K)%(10**9+7)
ans=0
for i in range(K+1):
  ans+=(q*comb(len(S)+i-1,i))%(10**9+7)
  q=(q*423076927)%(10**9+7)
  
print(ans%(10**9+7))

Solution (Python):
mod = 10**9+7
M = 2*10**6

def main(K,S):
    fact = [1]*(M+1)
    factinv = [1]*(M+1)
    for n in range(1,M+1):
        fact[n] = n*fact[n-1]%mod
        factinv[n] = pow(fact[n],mod-2,mod)

    def comb(n,k):
        return fact[n]*factinv[k]*factinv[n-k]%mod
    n = len(S)
    ans = 0

    for k in range(K+1):
        ans += comb(n+k-1,k)*pow(25,k,mod)*pow(26,K-k,mod)
        ans %= mod
    print(ans)

if __name__ == '__main__':
    K = int(input())
    S = input()
    main(K,S)

Solution (Python):
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7
size = 2*10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, size + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

K = int(input())
S = input()
L1 = [1]
L2 = [1]
for _ in range(10 ** 6):
    L1.append(L1[-1] * 25 % mod)
    L2.append(L2[-1] * 26 % mod)

ans = 0
for i in range(K+1):
    ans += L1[K-i] * L2[i] * cmb(K - i + len(S) - 1, len(S) - 1, mod)
    ans %= mod

print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
k=int(input())
s=input().rstrip()
INF=10**9+7
ans=0
n=len(s)
def modinv(a,m):
    b=m
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while not b==0:
        q=a//b
        (a,b)=(b,a%b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx%m

x=26**k
y=modinv(26,INF)
c=1

for i in range(k+1):
    ans=(ans+c*x)%INF
    x=(x*25*y)%INF
    c=(c*(n+i)*modinv(i+1,INF))%INF

print(ans)