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

import sys
import re
s = input()
x, y = [int(i) for i in sys.stdin.readline().split()]
s = [len(i) for i in re.split("T", s)]
v_ls = s[1::2]
h_ls = s[::2]
x -= h_ls[0]
h_ls.pop(0)
v_sum = sum(v_ls)
h_sum = sum(h_ls)
que = [(0, 0)]
# memo_v_ls[i][j] : i番目まででj - v_sumができるか
width = max(abs(y), v_sum)
memo_v_ls = [[0 for i in range(width * 2 + 1)] for j in range(len(v_ls) + 1)]
memo_v_ls[0][width] = 1
for j, v in enumerate(v_ls, 1):
    for i in range(width * 2 + 1):
        if i >= v and i <= v_sum - v:
            memo_v_ls[j][i] = max(memo_v_ls[j-1][i-v], memo_v_ls[j-1][i], memo_v_ls[j-1][i+v])
        elif i >= v:
            memo_v_ls[j][i] = max(memo_v_ls[j - 1][i - v], memo_v_ls[j - 1][i])
        elif i <= v_sum - v:
            memo_v_ls[j][i] = max(memo_v_ls[j - 1][i - v], memo_v_ls[j - 1][i + v])
        else:
            memo_v_ls[j][i] = memo_v_ls[j - 1][i]

flg = memo_v_ls[-1][y + width] == 1

width = max(abs(x), h_sum)
memo_h_ls = [[0 for i in range(width * 2 + 1)] for j in range(len(h_ls) + 1)]
memo_h_ls[0][width] = 1
for j, h in enumerate(h_ls, 1):
    for i in range(width * 2 + 1):
        if i >= h and i <= h_sum - h:
            memo_h_ls[j][i] = max(memo_h_ls[j - 1][i - h], memo_h_ls[j - 1][i], memo_h_ls[j - 1][i + h])
        elif i >= h:
            memo_h_ls[j][i] = max(memo_h_ls[j - 1][i - h], memo_h_ls[j - 1][i])
        elif i <= h_sum - h:
            memo_h_ls[j][i] = max(memo_h_ls[j - 1][i - h], memo_h_ls[j - 1][i + h])
        else:
            memo_h_ls[j][i] = memo_h_ls[j - 1][i]

flg &= memo_h_ls[-1][x + width] == 1
if flg:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys
import re
s = input()
x, y = [int(i) for i in sys.stdin.readline().split()]
s = [len(i) for i in re.split("T", s)]
v_ls = s[1::2]
h_ls = s[::2]
x -= h_ls[0]
h_ls.pop(0)
v_sum = sum(v_ls)
h_sum = sum(h_ls)
# memo_v_ls[i][j] : i番目まででj - v_sumができるか
width = max(abs(y), v_sum)
memo_v_ls = [[0 for i in range(width * 2 + 1)] for j in range(len(v_ls) + 1)]
memo_v_ls[0][width] = 1
for j, v in enumerate(v_ls, 1):
    for i in range(width * 2 + 1):
        if i >= v and i <= 2 * width - v:
            memo_v_ls[j][i] = max(memo_v_ls[j - 1][i - v], memo_v_ls[j - 1][i + v])
        elif i >= v:
            memo_v_ls[j][i] = memo_v_ls[j - 1][i - v]
        else:
            memo_v_ls[j][i] = memo_v_ls[j - 1][i + v]

flg = memo_v_ls[-1][y + width] == 1

width = max(abs(x), h_sum)
memo_h_ls = [[0 for i in range(width * 2 + 1)] for j in range(len(h_ls) + 1)]
memo_h_ls[0][width] = 1
for j, h in enumerate(h_ls, 1):
    for i in range(width * 2 + 1):
        if i >= h and i <= 2 * width - h:
            memo_h_ls[j][i] = max(memo_h_ls[j - 1][i - h], memo_h_ls[j - 1][i + h])
        elif i >= h:
            memo_h_ls[j][i] = memo_h_ls[j - 1][i - h]
        else:
            memo_h_ls[j][i] = memo_h_ls[j - 1][i + h]

flg &= memo_h_ls[-1][x + width] == 1
if flg:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N = int(input())
s = [''.join(sorted(input())) for i in range(N)]
check = [False] * N
cnt = 0
for i in range(N - 1):
    part = 0
    if check[i]:
        continue
    for j in range(i + 1, N):
        if check[j]:
            continue
        if s[i] == s[j]:
            part += 1
            check[j] = True
    cnt += (part + 1) * part // 2

print(cnt)


### FIXED CODE ###

def f(array):
    temp = 'abcdefghijklmnopqrstuvwxyz'
    ret = [0] * len(temp)
    cnt = 0
    for x in array:
        ret[temp.index(x)] += 1
        cnt += 1
        if cnt == 10:
            break
    return ret

N = int(input())
s = [''.join(sorted(input())) for i in range(N)]

dic = {}
for i in range(N):
    if s[i] in dic:
        dic[s[i]] += 1
    else:
        dic[s[i]] = 1

cnt = 0
for v in dic.values():
    cnt += v * (v - 1) // 2

print(cnt)
### BUGGY CODE ###

from collections import deque
import copy
H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
S = []
for i in range(H):
  for j in range(W):
    if maze[i][j] == ".":
      maze[i][j] = float("inf")
      S.append([i, j])
    else:
      maze[i][j] = -1
def bfs(H, W, maze, S):
  ans = 0
  for sy, sx in S:
    maze1 = copy.deepcopy(maze)
    maze1[sy][sx] = 0
    q = deque()
    q.append([sy,sx])
    while len(q)>0:
      y, x = q.popleft()
      for i, j in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        nexty = y+i
        nextx = x+j
        if nexty < 0 or nexty>=H or nextx < 0 or nextx>=W:
          continue
        if maze1[nexty][nextx] != -1:
          if maze1[nexty][nextx] > maze1[y][x]:
            maze1[nexty][nextx] = maze1[y][x] + 1
            q.append([nexty, nextx])
        ans = max(ans, maze1[nexty][nextx])
  print(ans)
bfs(H, W, maze, S)

### FIXED CODE ###

from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
            else:
                maze[y][x]=-1
    l = []
    ans = 0
    for i in range(len(S)):
        maze1 = copy.deepcopy(maze)
        maze1[S[i][0]][S[i][1]]=0
        que=deque([[S[i][0],S[i][1]]])
        while que:
          y,x=que.popleft()
          for k,m in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+k,x+m
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!=-1:
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                que.append([nexty,nextx])
            ans = max(ans, maze1[nexty][nextx])
    print(ans)
bfs()
### BUGGY CODE ###

n = int(input())
k = int(input())
c = 0

for x in range(n + 1):
    l = list(str(x))
    if len(l) - l.count("0") == k:
        c += 1

print(c)


### FIXED CODE ###

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

dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp [0][0][0] = 1

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1):
        dp[i][1][k] += dp[i - 1][1][k]
        if l != 0:
            dp[i][1][k] += dp[i - 1][0][k]
        else:
            dp[i][0][k] += dp[i - 1][0][k]
        if k - 1 >= 0:
            dp[i][1][k] += 9 * dp[i -1][1][k - 1]
            if l != 0:
                dp[i][0][k] += dp[i - 1][0][k - 1]
                dp[i][1][k] += (l - 1) * dp[i - 1][0][k -1]


print(dp[m][0][K] + dp[m][1][K])
### BUGGY CODE ###

n = int(input())
d = {}
for i in range(n):
  s = input()
  d[s] = d.get(s, 0) + 1

maxKeys = [x[0] for x in d.items() if x[1] == max(d.values())]
so = sorted(maxKeys)
for e in so:
  print(e)

### FIXED CODE ###

n = int(input())
d = {}
for i in range(n):
  s = input()
  d[s] = d.get(s, 0) + 1
m = max(d.values())
maxKeys = [x[0] for x in d.items() if x[1] == m]
so = sorted(maxKeys)
for e in so:
  print(e)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

h, n = na()
dp = [10**9+7 for i in range(h+1)]
dp[0] = 0
for i in range(n):
    a, b = na()
    for j in range(h):
        dp[min(j + a, h)] = min(dp[min(j + a, h)], dp[j] + b)
print(dp[h])


### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

h, n = na()
inf = 10**9+7
dp = [inf for i in range(h+1)]
dp[0] = 0
for i in range(n):
    a, b = na()
    for j in range(h):
        dp[min(j + a, h)] = min(dp[min(j + a, h)], dp[j] + b)
print(dp[h])
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for i in range(q):
    l, r = map(int, input().split())
    print(s[l-1:r].count("AC"))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
count = [0]*(n+1)
for i in range(1, n):
    count[i] += count[i-1]
    if s[i-1:i+1] == "AC":
      count[i] += 1
for i in range(q):
    l, r = map(int, input().split())
    print(count[r-1] - count[l-1])
### BUGGY CODE ###

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    xy.append([int(item) for item in input().split()])
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i, x=1):
    while i <= n:
        cnt[i] += x
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow(2, points_in_quad[0][i], MOD)
    free2 = pow(2, points_in_quad[1][i], MOD)
    free3 = pow(2, points_in_quad[2][i], MOD)
    free4 = pow(2, points_in_quad[3][i], MOD)
    ans -= (free2 - 1) * (free4 - 1) * (free1 - 1) * (free3 - 1) % MOD
    ans += free1 * free3 * (free2 - 1) * (free4 - 1) % MOD
    ans += free2 * free4 * (free1 - 1) * (free3 - 1) % MOD
    # target included, n >= 2 selected
    ans += pow(2, n-1, MOD)
    ans %= MOD
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    x, y = [int(item) for item in input().split()]
    xy.append((x, y))
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i):
    while i <= n:
        cnt[i] += 1
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow2 = []
a = 1
for i in range(n+1):
    pow2.append(a)
    a *= 2
    a %= MOD

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow2[points_in_quad[0][i]]
    free2 = pow2[points_in_quad[1][i]]
    free3 = pow2[points_in_quad[2][i]]
    free4 = pow2[points_in_quad[3][i]]
    fix24 = (free2 - 1) * (free4 - 1) % MOD
    fix13 = (free1 - 1) * (free3 - 1) % MOD
    ans -= fix24 * fix13 % MOD
    ans += ((free1 * free3) % MOD) * fix24 % MOD
    ans += ((free2 * free4) % MOD) * fix13 % MOD
    ans %= MOD
# target included, n >= 2 selected
ans += pow2[n-1] * n % MOD
print(ans % MOD)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)

div_cache = {}


def primes(N):
    if N in div_cache:
        return div_cache[N]
    ret = set()

    for i in range(1, N):
        if N % i == 0:
            ret.add(i)
            if i != 1:
                ret.add(N // i)
    div_cache[N] = ret
    return ret


# assert(primes(1) == set())
# assert(primes(2) == {1})
# assert(primes(10) == {1, 2, 5})
# assert(primes(20) == {1, 2, 4, 5, 10})

def slowsolve(N, K):
    import itertools
    import math
    data = {}
    s = 0
    KK = [i for i in range(1, K + 1)]
    for p in itertools.product(KK, repeat=N):
        cdi = p[0]
        for c in p:
            cdi = math.gcd(cdi, c)
        s += cdi
        data.setdefault(cdi, 0)
        data[cdi] += 1
    print(data)
    return s


def solve(N, K):
    M = pow(10, 9) + 7
    ans = 0
    data = {}
    for i in range(1, K + 1):
        P = pow(K // i, N, M)
        ans += i * P
        # data[i] = P

        def past(prim, sign):
            nonlocal ans
            for p in prim:
                # data[p] += P * sign
                ans += p * P * sign
                ans %= M
                if p != 1:
                    past(primes(p), sign * -1)

        past(primes(i), -1)
        ans %= M

    # print(data)
    return ans


# assert(solve(3, 2) == 9)
# assert(slowsolve(3, 2) == 9)
# assert(slowsolve(3, 3) == 30)
# assert(solve(3, 3) == slowsolve(3, 3))
# print("collect")
# print(slowsolve(2, 6))
# print("wrong")
# print(solve(2, 6))
# assert(solve(6, 6) == slowsolve(6, 6))
# assert (solve(3, 200) == 10813692)
# print("OK")
# assert (solve(100000, 100000) == 742202979)
# print("OK!!!!")

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    print(solve(N, K))


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)

def slowsolve(N, K):
    import itertools
    import math
    data = {}
    s = 0
    KK = [i for i in range(1, K + 1)]
    for p in itertools.product(KK, repeat=N):
        cdi = p[0]
        for c in p:
            cdi = math.gcd(cdi, c)
        s += cdi
        data.setdefault(cdi, 0)
        data[cdi] += 1
    print(data)
    return s


cache = {}
def solve(N, K):
    M = pow(10, 9) + 7
    ans = 0
    for i in range(K, 0, -1):
        P = pow(K // i, N, M)
        j = i + i
        while j <= K:
            P -= cache[j]
            j += i
        while P < 0:
            P += M

        cache[i] = P
        ans += i * P
        ans %= M
    return ans

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    print(solve(N, K))
### BUGGY CODE ###

def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
for i in BC:
    if i[0] in A:
        indexlist=my_index_multi(A,i[0])
        for j in indexlist:
            A[j]=i[1]
    print(sum(A))

### FIXED CODE ###

import collections
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
N=int(input())
A=list(map(int,input().split()))
goukei=sum(A)
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
c = collections.Counter(A)
for i in BC:
    goukei+=c[i[0]]*(i[1]-i[0])
    c[i[1]]=c[i[0]]+c[i[1]]
    c[i[0]]=0
    print(goukei)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
s = input().rstrip("\n")
t = input().rstrip("\n")
dic = {"a":[],"b":[],"c":[],"d":[],"e":[],"f":[],"g":[],"h":[],"i":[],"j":[],"k":[],"l":[],"m":[],"n":[],"o":[],"p":[],"q":[],"r":[],"s":[],"t":[],"u":[],"v":[],"w":[],"x":[],"y":[],"z":[]}
for i,c in enumerate(s):
    dic[c] += [i]
else:
    l = i+1
#print(dic)
cnt = 0
ind = -1
ans = 0
for c in t:
    d = dic[c]
    if d:
        if d[-1] > ind:
    #    print("c=",c,"d=",d)
            for i in d: #iは各文字のindex 昇順
        #        print("i=",i)
                if ind < i: #もし現在位置<iなら
                    ind = i
        #            print("found, ind=",i)
                    break
        else:
    #        print("not found")
            cnt += 1
            ind = d[0]
    else:
        ans = -1
        break

print(cnt*l+ind+1 if ans > -1 else -1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict
import bisect

s = input().rstrip()
t = input().rstrip()
d = defaultdict(list)

for i,c in enumerate(s):
    d[c].append(i)
ans = 0
ind = -1
for c in t:
    #print("c=",c,"d[c]=",d[c])
    if not d[c]:
        ans = -1
        break
    ins = bisect.bisect_left(d[c],ind+1)
    if ins < len(d[c]):
        ind =d[c][ins]
     #   print("ins=",ins,end = "")
    else:
      #  print("追加",end = "")
        ans += len(s)
        ind = d[c][0]
    #print("ind=", ind)
    #print()
else:
    ans += ind+1

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
ans = 0
for i in range(M):
  A[0] = A[0] // 2
  A.sort(reverse = True)
for i in range(N):
  ans += A[i]
print(ans)

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

for i in range(M):
  mm = heapq.heappop(a)
  heapq.heappush(a, (-mm//2) * (-1))
  
print(-sum(a))
### BUGGY CODE ###

n = int(input())

ans = 1

for i in range(1, n+1):
    ans *= i
ans %= 1000000007

print(ans)

### FIXED CODE ###

n = int(input())

ans = 1

for i in range(1, n+1):
    ans *= i
    ans %= 1000000007

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

n, k, q = map(int, input().split())
a = [int(input()) for i in range(q)]
import numpy as np

all_score = np.array([k for _ in range(n)])
for i in a:
    all_score -= 1
    all_score[i - 1] += 1

for j in all_score:
    if j > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for i in range(q)]

all_score = [k - q for _ in range(n)]
for ai in a:
    all_score[ai - 1] += 1
for j in all_score:
    if j > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import math
(_,), a  = [list(map(int, s.split())) for s in open(0)]

def fast_factorize(num):
    min_factor_list = list(range(num + 1))
    for i in range(int(math.sqrt(num) + 1), 1, -1):
        for j in range(i, num+1, i):
            min_factor_list[j] = i
    return min_factor_list

min_factor_list = fast_factorize(max(a))

prime_factor_sets = []
for x in a:
    prime_factor_set = set()
    while min_factor_list[x] != 1:
        prime_factor_set.add(min_factor_list[x])
        x //= min_factor_list[x]
    prime_factor_sets.append(prime_factor_set)

g = prime_factor_sets[0].copy()
l = prime_factor_sets[0].copy()
s = 0
for x in prime_factor_sets:
    g &= x
    l |= x
    s += len(x)

if len(g) != 0:
    ans = 'not coprime'
elif len(l) != s:
    ans = 'setwise coprime'
else:
    ans = 'pairwise coprime'
print(ans)

### FIXED CODE ###

import math
(_,), a  = [list(map(int, s.split())) for s in open(0)]

def fast_factorize(num):
    min_factor_list = list(range(num + 1))
    for i in range(int(math.sqrt(num) + 1), 1, -1):
        for j in range(i, num+1, i):
            min_factor_list[j] = i
    return min_factor_list

min_factor_list = fast_factorize(max(a))

prime_factor_sets = []
for x in a:
    prime_factor_set = set()
    while min_factor_list[x] != 1:
        prime_factor_set.add(min_factor_list[x])
        x //= min_factor_list[x]
    prime_factor_sets.append(prime_factor_set)

g = prime_factor_sets[0].copy()
l = prime_factor_sets[0].copy()
s = 0
for x in prime_factor_sets:
    g &= x
    l |= x
    s += len(x)

if len(g) != 0:
    ans = 'not coprime'
elif len(l) != s:
    ans = 'setwise coprime'
else:
    ans = 'pairwise coprime'
print(ans)
### BUGGY CODE ###

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

    answer = 0

    for i in range(N - 2):
        Si = S[i]
        for j in range(i + 1, N - 1):
            Sj = S[j]
            if Si == Sj:
                continue

            for k in range(j + 1, N):
                Sk = S[k]
                if Si == Sk or Sj == Sk:
                    continue
                if j - i == k - j:
                    continue
                answer += 1
    print(answer)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

    R_count = 0
    G_count = 0
    B_count = 0

    for s in S:
        if s == "R":
            R_count += 1
        elif s == "G":
            G_count += 1
        else:
            B_count += 1

    # 第一条件だけを考えたときの組み合わせの総数
    answer = R_count * G_count * B_count

    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            # i, j が決まると、第二条件を満たさない k が決まる
            k = 2 * j - i

            # k が文字列の長さを超えたときは、第二条件を満たすことができない
            if k >= N:
                continue

            # 第二条件を満たす i, j, k が、第一条件を満たす場合、
            # 第一条件だけ考えたときの組み合わせの総数から差し引く
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                answer -= 1
            
    print(answer)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

def fast_pow(a, b, m):
    base = a
    res = 1
    while b:
        if b & 1:
            res = res * base % m
        base = base * base % m
        b //= 2
    return res

K = int(input())
S = input()
M = int(10**9 + 7)

fact = [1]
for i in range(1, K + len(S) + 10):
    fact.append(fact[-1] * i % M)
inv = [fast_pow(f, M - 2, M) for f in fact]

def comb(a, b, m):
    return fact[a] * inv[b] % m * inv[a - b] % m

def hcomb(a, b, m):
    return comb(a + b - 1, a - 1, m)

ans = 0
for l in range(0, K + 1):
    ans += fast_pow(26, l, M) * fast_pow(25, K - l, M) % M * hcomb(len(S), K - l, M) % M
    ans %= M
print(ans)

### FIXED CODE ###

K = int(input())
S = input()
M = int(10 ** 9 + 7)

fact = [1]
for i in range(1, K + len(S) + 10):
    fact.append(fact[-1] * i % M)

finv = [pow(fact[-1], M - 2, M)]
for i in range(K + len(S) + 9, 0, -1):
    finv.append(finv[-1] * i % M)
finv.reverse()

def comb(a, b, m):
    return fact[a] * finv[b] % m * finv[a - b] % m

def hcomb(a, b, m):
    return comb(a + b - 1, a - 1, m)

ans = 0
for l in range(0, K + 1):
    ans += pow(26, l, M) * pow(25, K - l, M) % M * hcomb(len(S), K - l, M) % M
    ans %= M
print(ans)