Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n,k=map(int,input().split())
s=list(input())
import sys
input=sys.stdin.readline
s.reverse()
if k>=20:
    print(min(s)*n)
else:
    for i in range(min(k,20)):
        t=list(reversed(s))
        u=t+s
        uu=u[:n]
        for j in range(1,n+1):
            x=u[j:j+n]
            if uu>x:
                uu=x
        s=uu
    print("".join(s))


### FIXED CODE ###

n,k=map(int,input().split())
s=list(input())
l=0
c=0
for i in range(n):
    if s[i]==min(s):
        c+=1
        l=max(l,c)
    else:
        c=0
import sys
input=sys.stdin.readline
s.reverse()
if (2**(k-1))*l>n:
    print(min(s)*n)
else:
    for i in range(min(k,13)):
        t=list(reversed(s))
        u=t+s
        uu=u[:n]
        for j in range(1,n+1):
            x=u[j:j+n]
            if uu>x:
                uu=x
        s=uu
    print("".join(s))
### BUGGY CODE ###

import math
k = int(input())
ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for t in range(1, k+1):
            ans += math.gcd(i, math.gcd(j, t))

print(ans)

### FIXED CODE ###

import math
k = int(input())
ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        gcd1 = math.gcd(i,j)
        for t in range(1, k+1):
            ans += math.gcd(gcd1, t)

print(ans)
### BUGGY CODE ###

N=int(input())
S=input()

# Zアルゴリズムで解く

c=0
max_num=0
for sub in range(len(S)):
    subS = S[sub:]
    length = len(subS)
    A=[0 for i in range(length-max_num)]

    for i in range(1,length-max_num):
        if i+ A[i-c] < c+A[c]:
            A[i] = A[i-c]
        else:
            j=max(0,c+A[c]-i)
            for _ in range(length):
                if i+j<length and subS[j]==subS[i+j]:
                    j+=1
            A[i]=j
        if max_num<A[i] and i>=A[i]:
            max_num = A[i]
print(max_num)

### FIXED CODE ###

N=int(input())
S=input()

# Zアルゴリズムで解く

def z_algorithm(S):
    N=len(S)
    A = [N] + [0]*(N-1)
    
    left=1
    length=0
    
    while left < N:
        
        # prefixが同じ間length加算
        while left + length < N and S[length] == S[left+length]:
            length += 1
        
        # prefixの一致数保存
        A[left] = length
        
        # 一文字一致していなければ戻る
        if length == 0:
            left+=1
            continue
        
        # lengthの分だけleftとindexの間を埋めていく(はみ出ていないとこまで)
        k=1
        while k+left < N and k+A[k]<length:
            A[left+k] = A[k]
            k += 1
            
        left += k
        length -= k
    return A

c=0
max_num=0
for sub in range(len(S)):
    subS = S[sub:]
    A=z_algorithm(subS)
    for i,a in enumerate(A):
        if i>=a and max_num<a:
            max_num=a
print(max_num)
### BUGGY CODE ###

#

import sys
from collections import deque
input=sys.stdin.readline

def main():
    H,W,K=map(int,input().split())
    x1,y1,x2,y2=map(int,input().split())
    x1-=1
    y1-=1
    x2-=1
    y2-=1
    mas=[list(input()) for i in range(H)]
    dist=[[-1]*W for i in range(H)]
    qu=deque([(x1,y1)])
    dist[x1][y1]=0
    qup=qu.popleft
    qua=qu.append
    d=((-1,0),(1,0),(0,-1),(0,1))
    while(len(qu)>0):
        v=qup()
        for di in d:
            for i in range(1,K+1):
                nvh=v[0]+i*di[0]
                nvw=v[1]+i*di[1]
                if nvh<0 or nvh>=H or nvw<0 or nvw>=W or mas[nvh][nvw]=="@":
                    break
                if dist[nvh][nvw]==-1:
                    dist[nvh][nvw]=dist[v[0]][v[1]]+1
                    qua((nvh,nvw))
    print(dist[x2][y2])
    
if __name__=="__main__":
    main()


### FIXED CODE ###

#

import sys
from collections import deque
input=sys.stdin.readline

def main():
    H,W,K=map(int,input().split())
    x1,y1,x2,y2=map(int,input().split())
    x1-=1
    y1-=1
    x2-=1
    y2-=1
    mas=[list(input()) for i in range(H)]

    dist=[[-1]*W for i in range(H)]
    dist[x1][y1]=0
    
    qu=deque([(x1,y1)])
    qup=qu.popleft
    qua=qu.append
    
    d=((-1,0),(1,0),(0,-1),(0,1))
    
    while(len(qu)>0):
        v=qup()
        for di in d:
            for i in range(1,K+1):
                nvh=v[0]+i*di[0]
                nvw=v[1]+i*di[1]
                if nvh<0 or nvh>=H or nvw<0 or nvw>=W or mas[nvh][nvw]=="@":
                    break
                if dist[nvh][nvw]!=-1 and dist[nvh][nvw]<=dist[v[0]][v[1]]:
                    break
                if dist[nvh][nvw]==-1:
                    dist[nvh][nvw]=dist[v[0]][v[1]]+1
                    qua((nvh,nvw))
    print(dist[x2][y2])
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

N,Q = map(int, input().split())
S = input()
AC_list = [0]*(N-1)
for i in range(N-1):
  if S[i:i+2] == 'AC':
    AC_list[i] = 1
for q in range(Q):
  l,r = map(int, input().split())
  print(sum(AC_list[l-1:r-1]))

### FIXED CODE ###

N,Q = map(int, input().split())
S = input()
AC_cum = [0]
for i in range(N-1):
  if S[i:i+2] == 'AC':
    AC_cum.append(AC_cum[-1]+1)
  else:
    AC_cum.append(AC_cum[-1])
for q in range(Q):
  l,r = map(int, input().split())
  print(AC_cum[r-1]-AC_cum[l-1])
### BUGGY CODE ###

from collections import deque

def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        if label not in visited:
            visited.append(label)

            for v in d[label]:
                if dist[v[0]] == float("inf"):
                    dist[v[0]] = dist[label] + v[1]
                    queue.appendleft(v[0])

    return

n = int(input())
d = [[] for _ in range(n)]
for _ in range(n - 1):
	a, b, c = map(int, input().split())
	d[a - 1].append([b - 1, c])
	d[b - 1].append([a - 1, c])

q, k = map(int, input().split())
dist = [float("inf") for _ in range(n)] # nは頂点数
dist[k - 1] = 0

bfs(k - 1)

for _ in range(q):
	x, y = map(int, input().split())
	print(dist[x - 1] + dist[y - 1])


### FIXED CODE ###

from collections import deque

def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        #if label not in visited:
        visited.append(label)

        for v in d[label]:
            if dist[v[0]] == float("inf"):
                dist[v[0]] = dist[label] + v[1]
                queue.appendleft(v[0])

    return

n = int(input())
d = [[] for _ in range(n)]
for _ in range(n - 1):
	a, b, c = map(int, input().split())
	d[a - 1].append([b - 1, c])
	d[b - 1].append([a - 1, c])

q, k = map(int, input().split())
dist = [float("inf") for _ in range(n)] # nは頂点数
dist[k - 1] = 0

bfs(k - 1)

for _ in range(q):
	x, y = map(int, input().split())
	print(dist[x - 1] + dist[y - 1])
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 0

for i in range(len(p)):
    if min(p[:i+1]) == p[i]:
        ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 0
min_p = n

for i in p:
    if i <= min_p:
        min_p = i
        ans += 1

print(ans)
### BUGGY CODE ###

k = int(input())
ans = 0
import math
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      f = math.gcd(i,j)
      ff = math.gcd(f,l)
      ans += ff
print(ans)


### FIXED CODE ###

k = int(input())
ans = 0
import math
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      f = math.gcd(i,j)
      ff = math.gcd(f,l)
      ans += ff
print(ans)
### BUGGY CODE ###

n=int(input())
al=list(map(int,input().split()))
ac=0
ans=set()
tl=[0]*n
for i in range(n,0,-1):
    if tl[i-1]%2!=al[i-1]:
        ac+=1
        ans.add(i)
        for j in range(1,i+1):
            if i%j==0:
                tl[j-1]+=1
print(ac)
if ac>0:
    print(' '.join(map(str,ans)))

### FIXED CODE ###

n=int(input())
al=list(map(int,input().split()))
ac=0
ans=set()
tl=[0]*n
for i in range(n,0,-1):
    if tl[i-1]%2!=al[i-1]:
        ac+=1
        ans.add(i)
        for j in range(1,int(i**0.5)+1):
            if i%j==0:
                tl[j-1]+=1
                if j**2==i:
                    continue
                tl[i//j-1]+=1
print(ac)
if ac>0:
    print(' '.join(map(str,ans)))
### BUGGY CODE ###

# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

x,y,z,k=MI()
A=sorted(LI(),reverse=True)
B=sorted(LI(),reverse=True)
C=sorted(LI(),reverse=True)
Q=[[(A[0]+B[0]+C[0])*(-1),0,0,0]]
heapify(Q)
#print(Q)
i=0
ans=[]
#print(heappop(Q))
al=[[[-1]*x for i in range(y)] for j in range(z)]
al[0][0][0]=0
while i<k:
    a,u,v,w=heappop(Q)
    ans.append(-a)
    if u+1<x and al[u+1][v][w]==-1:
        heappush(Q,[-A[u+1]-B[v]-C[w],u+1,v,w])
        al[u+1][v][w]=0
    if v+1<y and al[u][v+1][w]==-1:
        heappush(Q,[-A[u]-B[v+1]-C[w],u,v+1,w])
        al[u][v+1][w]=0
    if w+1<z and al[u][v][w+1]==-1:
        heappush(Q,[-A[u]-B[v]-C[w+1],u,v,w+1])
        al[u][v][w+1]=0
    i+=1
#print(len(ans))
for i in range(k):
    print(ans[i])

        

    
    


### FIXED CODE ###

# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

x,y,z,k=MI()
A=LI()
B=LI()
C=LI()
lis=[]
for i in range(x):
    for j in range(y):
        lis.append(A[i]+B[j])
lis.sort(reverse=True)
lisan=[]
for i in range(min(k,x*y)):
    for j in range(z):
        lisan.append(lis[i]+C[j])
lisan.sort(reverse=True)
for i in range(k):
    print(lisan[i])
### BUGGY CODE ###

_=input()
val=1
for i in map(int,input().split()):
  val*=i
if val>10**18:
  print(-1)
  exit()

print(val)

### FIXED CODE ###

_=input()
val=1
t=10**18

for i in map(int,input().split()):
  if i==0:
    val*=i
    break
  if val>=t: continue
  val*=i

if val>t:
  print(-1)
  exit()

print(val)
### BUGGY CODE ###

import itertools
N=int(input())
an=[int(x) for x in map(int,input().split()[:N])]

def judgeXOR(v):
    for x in range(N):
        if x==0:
            if (v[N-1] ^ v[x+1] ) != (x+1):
                return False
        elif x==(N-1):
            if (v[0] ^ v[x-1]) !=(x+1):
                return False
        else:
            if (v[x-1] ^ v[x+1])!=(x+1):
                return False
    return True

for v in itertools.permutations(an,N):
    if v[0] !=an[0]:
        break
    if judgeXOR(v):
        print("Yes")
        exit()

print("No")


### FIXED CODE ###

import itertools
N=int(input())
an=[int(x) for x in map(int,input().split()[:N])]

ret=an[0]
for x in range(1,N):
    ret= an[x] ^ ret

if ret==0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import sys
def solve(n,m,a):
    bb = {i+1:[] for i in range(n)}
    for [s1,s2] in a:
        bb[s1].append(s2)
    b = [i for i in bb.values()]
    for i in range(len(b)):
        b[i].sort()
    c = {s2:s1 for [s1,s2] in a}
    ans = ""
    zero = ["00000","0000","000","00","0",""]
    for i in range(m):
        ken = str(c[a[i][1]])
        ban = str(b[c[a[i][1]]-1].index(a[i][1])+1)
        ans += zero[len(ken)-1] + ken + zero[len(ban)-1] + ban + "\n"
    
    return ans 
def readQuestion():
    ws = sys.stdin.readline().strip().split()
    N = int(ws[0])
    M = int(ws[1])
    ls_PY = [list(map(int, sys.stdin.readline().strip().split())) for j in range(M)]
    return (N, M, ls_PY)

def main():
    N, M, ls_PY = readQuestion()
    answer = solve(N, M, ls_PY)
    print(answer)

if __name__ == '__main__':
    main()

### FIXED CODE ###

N,M=map(int,input().split())
PY=[list(map(int,input().split()))+[i] for i in range(M)] #定義終了
 
PY.sort(key= lambda x:x[1])
num=[0]*N
w=[""]*M
 
for p,y,i in PY:
	num[p-1]+=1
	w[i]=str(p).zfill(6)+str(num[p-1]).zfill(6)

for i in range(M):
  	print(w[i])
### BUGGY CODE ###

n = int(input())
s = input()

a = {}
ii = [0]*10
jj = [0]*100
for i in range(n-2):
  si = int(s[i])
  if sum(ii) == 10:
    break
  elif ii[si] == 1:
    next
  else:
    ii[si] = 1
  for j in range(i+1,n-1):
    sij = 10*si + int(s[j])
    if sum(jj[10*si:10*(si+1)]) == 10:
      break
    elif jj[sij] == 1:
      next
    else:
      jj[sij] = 1
    for k in range(j+1,n):
      a["".join([s[i],s[j],s[k]])] = 1
print(sum(a.values()))

### FIXED CODE ###

n = int(input())
s = input()

a = 0
ii = [0]*10
for i in range(n-2):
  si = int(s[i])
  if sum(ii) == 10:
    break
  elif ii[si] == 1:
    continue
  else:
    ii[si] = 1
  jj = [0]*10
  for j in range(i+1,n-1):
    sj = int(s[j])
    if sum(jj) == 10:
      break
    elif jj[sj] == 1:
      continue
    else:
      jj[sj] = 1
    kk = [0]*10
    for k in range(j+1,n):
      sk = int(s[k])
      if sum(kk) == 10:
        break
      else:
        kk[sk] = 1
    a += sum(kk)
print(a)
### BUGGY CODE ###

import sys
from itertools import accumulate

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
S = [list(map(int, sr())) for _ in range(H)]
Scum = [list(accumulate(x)) for x in S]
answer = 10000
for bit in range(1<<(H-1)):
    count = 0
    for i in range(H-1):
        if bit >> i & 1:
            count += 1
    bit += 1 << H-1 # 最後の切れ目
    # 縦のラインは貪欲法
    prev = -1
    w = 0
    while w < W:
        white = 0
        cut = False
        for i in range(H):
            white += Scum[i][w] - (Scum[i][prev] if prev >= 0 else 0)
            if (bit >> i) & 1: # 切れ目が来た
                if white > K:
                    cut = True
                white = 0
        if cut:
            if prev == w-1: # 一列でKをオーバー
                break
            count += 1
            prev = w-1
        else:
            w += 1
    else:
        answer = min(answer, count)

print(answer)


### FIXED CODE ###

import sys
from itertools import accumulate

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
S = [list(map(int, sr())) for _ in range(H)]
Scum = [list(accumulate(x)) for x in S]
answer = 10000
for bit in range(1<<(H-1)):
    count = 0
    for i in range(H-1):
        if bit >> i & 1:
            count += 1
    bit += 1 << H-1 # 最後の切れ目
    # 縦のラインは貪欲法
    prev = -1
    w = 0
    while w < W:
        white = 0
        cut = False
        for i in range(H):
            white += Scum[i][w] - (Scum[i][prev] if prev >= 0 else 0)
            if (bit >> i) & 1: # 切れ目が来た
                if white > K:
                    cut = True
                white = 0
        if cut:
            if prev == w-1: # 一列でKをオーバー
                break
            count += 1
            prev = w-1
        else:
            w += 1
    else:
        answer = min(answer, count)

print(answer)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Jun  3 18:35:23 2020

@author: NEC-PCuser
"""

N, M = map(int, input().split())
A = list(map(int, input().split()))

for i in range(M):
    A.sort()
    A[len(A) - 1] = A[len(A) - 1] // 2

ans = 0
for j in range(len(A)):
    ans += A[j]

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Jun  3 18:35:23 2020

@author: NEC-PCuser
"""
import heapq

N, M = map(int, input().split())
A = [-int(n) for n in input().split(" ")]

heapq.heapify(A)

for i in range(M):
    most_expensive = -heapq.heappop(A)
    most_expensive //= 2
    heapq.heappush(A, -most_expensive)
    
print(-sum(A))
### BUGGY CODE ###

N, M = map(int, input().split())
t_list = [[0] * 2 for _ in range(M)]
for i in range(M):
  t_list[i] = list(map(int, input().split()))
ans = 0
a = [j for j in range(t_list[0][0], t_list[0][1]+1)]
for i in range(M):
  b = [j for j in range(t_list[i][0], t_list[i][1]+1)]
  a = list(set(a) & set(b))
ans = len(set(a))
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
 
l_list = []
r_list = []
for i in range(M):
  l, r = map(int, input().split())
  l_list.append(l)
  r_list.append(r)
  
l = max(l_list)
r = min(r_list)
 
if r < l:
  print(0)
else:
  print(r-l+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

h, w = map(int, input().split())
s = [input() for _ in range(h)]

field = [list(f) for f in s]

def dfs(x, y):
    global total
    total += 1
    # 移動する4方向をループ
    for dx in [-1, 1]:
        nx = x + dx; ny = y
        while 0 <= nx and nx < h and 0 <= ny and ny < w and field[nx][ny] == '.':
            total += 1
            # x方向にdx, y方向にdy移動した場所を(nx, ny)とする
            nx += dx
    for dy in [-1, 1]:
        nx = x; ny = y + dy
        while 0 <= nx and nx < h and 0 <= ny and ny < w and field[nx][ny] == '.':
            total += 1
            # x方向にdx, y方向にdy移動した場所を(nx, ny)とする
            ny += dy
    
    return total

res = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            # '.'からdfsを始める
            total = 0
            dfs(i, j)
            res = max(total, res)

print(res)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

h,w = map(int,input().split())

s = [input() for _ in range(h)]
cnt = [[0] * w for _ in range(h)]

for i in range(h):
    done = [0] * w

    for j in range(w):
        if s[i][j] == '#': continue
        if done[j]: continue

        l = 0
        while j+l < w:
            if s[i][j+l] == '#': break
            l += 1

        for k in range(l):
            cnt[i][j+k] += l
            done[j+k] = 1

for j in range(w):
    done = [0] * h

    for i in range(h):
        if s[i][j] == '#': continue
        if done[i] :continue

        l = 0
        while i+l < h:
            if s[i+l][j] == '#': break
            l += 1

        for k in range(l):
            cnt[i+k][j] += l
            done[i+k] = 1

ans = 0

for i in range(h):
    for j in range(w):
        ans = max(ans, cnt[i][j]-1)

print(ans)
### BUGGY CODE ###

N = int(input())
hList = list(map(int, input().split()))
count = 0

for i in range(N):
  for j in range(i+1,N):
    if (j-i) == (hList[i]+hList[j]):
      count += 1
print(count)

### FIXED CODE ###

import collections

N = int(input())
hList = list(map(int, input().split()))
count = 0
n_p = collections.Counter([ i + hList[i] for i in range(len(hList))])

for i in range(N):
  if i - hList[i] > 0:
    count += n_p.get(i - hList[i], 0)

print(count)
### BUGGY CODE ###

n, m, q = map(int, input().split())

lr = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    l, r = map(lambda x: int(x) - 1, input().split())
    lr[l][r] += 1

c = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if j == 0:
            c[i][j] = lr[i][j]
        else:
            c[i][j] = c[i][j-1] + lr[i][j]

for _ in range(q):
    p, q = map(lambda x: int(x) - 1, input().split())
    count = 0
    for i in range(p, q+1):
        if p == 0:
            count += c[i][q]
        else:
            count += (c[i][q] - c[i][p-1])

    print(count)

### FIXED CODE ###

n, m, q = map(int, input().split())

lr = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    l, r = map(lambda x: int(x) - 1, input().split())
    lr[l][r] += 1

for i in range(n):
    for j in range(1, n):
        lr[i][j] += lr[i][j-1]

for i in range(1, n):
    for j in range(n):
        lr[i][j] += lr[i-1][j]

for _ in range(q):
    p, q = map(lambda x: int(x) - 1, input().split())
    if p == 0:
        print(lr[q][q])
    else:
        print(lr[q][q]-lr[p-1][q]-lr[q][p-1]+lr[p-1][p-1])
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = []

for i in range(Q):
    A.append(int((input())))

for i in range(N):
    P = K - Q + A.count(i+1)
    if P > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
p = [0] * N 
for i in A:
    p[i-1] += 1    

for i in range(N):
    P = K - Q + p[i]
    if P > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10000000)

h, n = map(int, input().split())
m_list = []
max_a = 0
for i in range(n):
  a, b = map(int, input().split())
  m_list.append((a, b))
  if a > max_a:
    max_a = a
  
class Attack_Memo():
  def __init__(self):
    self.attack_memo = {}
  
  def attack(self, h):
    res_list = []
    if h <= 0:
      return 0
    if h in self.attack_memo:
      return self.attack_memo[h]
    for a, b in m_list:
      base_b = self.attack(h-a)
      res_list.append(base_b+b)
    self.attack_memo[h] = min(res_list)
    return min(res_list)

res = 100000000000
ins = Attack_Memo()
for i in range(h+a+1):
  tmp = ins.attack(i)
  if i >= h and tmp <= res:
    res = tmp
print(res)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10000000)

h, n = map(int, input().split())
m_list = []
max_a = 0
for i in range(n):
  a, b = map(int, input().split())
  m_list.append((a, b))
  if a > max_a:
    max_a = a
  
class Attack_Memo():
  def __init__(self):
    self.attack_memo = {}
  
  def attack(self, h):
    res_list = []
    if h <= 0:
      return 0
    if h in self.attack_memo:
      return self.attack_memo[h]
    for a, b in m_list:
      base_b = self.attack(h-a)
      res_list.append(base_b+b)
    self.attack_memo[h] = min(res_list)
    return min(res_list)

res = 100000000000
ins = Attack_Memo()
for i in range(h+a+1):
  tmp = ins.attack(i)
  if i >= h and tmp <= res:
    res = tmp
print(res)
### BUGGY CODE ###

import sys
from scipy.special import comb

def input():
    return sys.stdin.readline().strip()
 
def main():
    K = int(input())
    S = input()
 
    mod = 10 ** 9 + 7
    n = len(S)
    ans = 0
 
    for i in range(K+1):
        tmp = pow(25,i,mod)
        tmp *= comb(i+n-1,n-1,exact=True)
        tmp *= pow(26,K-i,mod)
        ans += tmp
        ans %= mod
    print(ans)
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

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

    mod = 10 ** 9 + 7
    n = len(S)
    ans = 0

    fact =[1]*(K+n)
    factinv = [1]*(K+n)
    inv = [0,1]


    for i in range(2,K+n):
        fact[i] = (fact[i-1] * i) % mod
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv[i] = (factinv[i-1] * inv[i]) % mod

    def nCr(n,r):
        r = min(r,n-r)
        return (fact[n] * factinv[r] * factinv[n-r]) % mod

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

if __name__ == "__main__":
    main()