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

def fib(n):
    if n==0 or n==1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
print(fib(int(input())))



### FIXED CODE ###

def fib(n):
    if n ==0 or n == 1:
        return 1
    l = [0] * (n+1)
    l[0] = 1
    l[1] = 1

    for i in range(2,n+1):
        l[i] = l[i-2] + l[i-1]
    return l[i]

print(fib(int(input())))
### BUGGY CODE ###


from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    H, W = map(int, input().split())
    sy, sx = map(lambda x: int(x) - 1, input().split())
    gy, gx = map(lambda x: int(x) - 1, input().split())
    G = [input() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    q = deque()
    q.append((sy, sx, 0))
    ans[sy][sx] = 0

    while q:
        sy, sx, cost = q.popleft()
        for dy, dx in drc4:
            ny, nx = dy + sy, dx + sx
            if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and ans[ny][nx] > cost:
                ans[ny][nx] = cost
                q.append((ny, nx, cost))

        for dy8, dx8 in warp:
            ny8, nx8 = dy8 + sy, dx8 + sx
            if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                ans[ny8][nx8] = cost + 1
                q.append((ny8, nx8, cost + 1))

    print(ans[gy][gx] if ans[gy][gx] < INF else '-1')


if __name__ == "__main__":
    resolve()


### FIXED CODE ###


from collections import deque
def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

    ans = path[Dh][Dw] if path[Dh][Dw] < INF else -1
    print(ans)


if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

k, s=map(int, input().split())
ans=[]
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z==s:
                ans.append((x, y, z))

print(len(ans))

### FIXED CODE ###

k, s=map(int, input().split())
ans=0
for x in range(k+1):
    for y in range(k+1):
        if 0<= s-x-y <= k:
            ans+=1

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

N=int(input())
a = 0
for A in range(1, N):
  for B in range(1, N):
    for C in range(1, N):
      if A*B+C==N:
        a += 1
#  a += (N-1)//A
print(a)

### FIXED CODE ###

N = int(input())
a = 0
for A in range(1,N+1):
    a+=(N-1)//A
print(a)
### BUGGY CODE ###

n = int(input())
s = [input() for _ in range(n)]

l = []
l_num = []
for i in range(n):
  a = [s[i], s.count(s[i])]
  if a not in l:
    l.append(a)
    l_num.append(s.count(s[i]))

max_num = max(l_num)
l.sort()

for i in range(len(l)):
  if l[i][1] == max_num:
    print(l[i][0])

### FIXED CODE ###

from collections import Counter

n = int(input())
s = [input() for _ in range(n)]

c = Counter(s)
c = c.most_common()
ans_number = c[0][1]
c.sort()

for i in range(len(c)):
  if c[i][1] == ans_number:
    print(c[i][0])
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
  a.sort(reverse=True)
  a[0]=a[0]/2
import math
ans=0
for i in range(n):
  ans=ans+math.floor(a[i])
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=a[i]*-1
import heapq
heapq.heapify(a)
for i in range(m):
  t=(heapq.heappop(a))*-1
  heapq.heappush(a,(t//2)*-1)
print(sum(a)*-1)
### BUGGY CODE ###

def main():
    H, W = map(int, input().split())
    field = [list(input()) for _ in range(H)]
    dd = ((1, 0), (-1, 0), (0, 1), (0, -1))

    q = []
    for i in range(H):
        for j in range(W):
            if field[i][j] == "#":
                q.append((i, j))
                field[i][j] = 0
    moves = 0

    while q:
        qn = []
        moves += 1
        for x, y in q:
            for dx, dy in dd:
                nx, ny = int(x + dx), int(y + dy)
                if 0 <= nx < H and 0 <= ny < W:
                    if field[nx][ny] == ".":
                        field[nx][ny] = moves
                        qn.append((nx, ny))

        q = qn

    m = []
    for i in range(H):
        m.append(max(field[i]))
    print(max(m))


main()


### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    field = [list(input()) for _ in range(H)]
    dd = ((1, 0), (-1, 0), (0, 1), (0, -1))

    q = []
    for i in range(H):
        for j in range(W):
            if field[i][j] == "#":
                q.append((i, j))
                field[i][j] = 0
    moves = 0

    while q:
        qn = []
        moves += 1
        for x, y in q:
            for dx, dy in dd:
                nx, ny = int(x + dx), int(y + dy)
                if 0 <= nx < H and 0 <= ny < W:
                    if field[nx][ny] == ".":
                        field[nx][ny] = moves
                        qn.append((nx, ny))

        q = qn

    m = []
    for i in range(H):
        m.append(max(field[i]))
    print(max(m))


main()
### BUGGY CODE ###

n,k = map(int,input().split())

x = list(map(int,input().split()))
ans = 100000000000000000000


for i in range(n-k+1):
	a = x[i:i+k]
	b = 0
	if a[-1] <= 0:
		b = -a[0]
	elif a[0] >= 0:
		b = a[-1]
	else:
		b = min(abs(a[0])*2+a[-1],a[-1]*2-a[0])
	ans = min(ans,b)
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())

x = list(map(int,input().split()))
ans = 100000000000000

a = 0
while a != n:
	if x[a] >= 0:
		break
	a += 1
for i in range(max(0,a-k),n-k+1):
	if x[i+k-1] <= 0:
		ans = min(ans,-x[i])
	elif x[i] >= 0:
		ans = min(x[i+k-1],ans)
	else:
		ans = min(x[i+k-1]-x[i]+min(-x[i],x[i+k-1]),ans)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()
res = 0
chk1 = -1
chk2 = -1
chk3 = -1

a = []
b = []
c = []
for i,j in enumerate(list(t)):
	if j == "s":
		if i in a:
			continue
		res += r
		chk1 = i+k
		a.append(chk1)
	if j == "p":
		if i in b:
			continue
		res += s
		chk2 = i+k
		b.append(chk2)
	if j == "r":
		if i in c:
			continue
		res += p
		chk3 = i+k
		c.append(chk3)
print (res)

### FIXED CODE ###

n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = list(input())
res = 0
for i in range(n):
	if t[i] == t[i-k] and i >= k:
		t[i] = "X"
	if t[i] == "s":
		res += r
	if t[i] == "p":
		res += s
	if t[i] == "r":
		res += p
print (res)
### BUGGY CODE ###

N,M = map(int,input().split())
H = []
for i in range(M):
  H.append(int(input()))

dp = [0]*(N+1) # 初期条件
dp[0] = 1
dp[1] = 0 if 1 in H else 1
for i in range(2,N+1):
  if i in H:
    dp[i] = 0
  else:
    dp[i] = (dp[i-1]+dp[i-2])%1000000007
    
print(dp[-1])

### FIXED CODE ###

mod = 10**9+7
n,m = map(int,input().split())
a = set()
for i in range(m):
  a.add(int(input()))
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1) :
    dp[i] = (dp[i-1] + dp[i-2]) % mod
    if i in a :
        dp[i] = 0
print(dp[n])
### BUGGY CODE ###

#coding:utf-8
import numpy as np
import collections
N = int(input())
arr = []
for n in range(N):
    arr.append(list(map(int,input().split())))
arr = np.array(arr)

mx = arr[:,1:].max()
for i in range(101):
    for j in range(101):
        for k in range(mx,mx+199):
            flag = True
            for ls in arr:
                flag*=flag*(k-abs(i-ls[0])-abs(j-ls[1])==ls[2])
            if flag:
                print (i,j,k)
                exit()


### FIXED CODE ###

#coding:utf-8
import numpy as np
import collections
N = int(input())
arr = []
for n in range(N):
    arr.append(list(map(int,input().split())))
narr = np.array(arr)
x_min  = narr[:,0].min()
x_max = narr[:,0].max()
y_min = narr[:,1].min()
y_max =  narr[:,1].max()
mx = narr[:,2].max()
for k in range(mx+100,mx-1,-1):
    for i in range(x_min,x_max+1):
        for j in range(y_min,y_max+1):
            for x,y,h in arr:
                h_ = max(k-abs(i-x)-abs(j-y),0)
                if h_ != h:
                    break
            else:
                print (i,j,k)
                exit()
### BUGGY CODE ###

n = int(input())
friendly = [int(i) for i in input().split()]
friendly.sort(reverse=True)
place = []
place.append(friendly[0])
place=place*2
ans=0
for i in friendly[1:]:
    comfortable=[min(place[i], place[i+1]) for i in range(len(place)-1)]
    ans += max(comfortable)
    place.insert(comfortable.index(max(comfortable))+1, i)
print(ans)

### FIXED CODE ###

n = int(input())
friendly = list(map(int, input().split()))
friendly.sort(reverse=True)
if len(friendly)<=2:
    print(sum(friendly[0:n-1]))
else:
    ans = friendly[0]+sum(friendly[1:(n+1)//2-1])*2+friendly[(n+1)//2-1]*((n+1)%2+1)
    print(ans)
### BUGGY CODE ###

N = int(input())
S = []
for _ in range(N):
    S.append(input())
s_set = set(S)
s_dict = {}
for s in s_set:
    s_dict[s] = S.count(s)

s_list = sorted(s_dict.items(),key=lambda x:x[1],reverse=True)
num = s_list[0][1]
ans_list = []
for i in range(len(s_set)):
    if num == s_list[i][1]:
        ans_list.append(s_list[i][0])
    else:
        break
ans_list.sort()
for i in ans_list:
    print(i)

### FIXED CODE ###

from collections import Counter

stdin = open(0)
N = int(stdin.readline())
S = stdin.read().split()

counter = Counter(S)
max_cnt = max(counter.values())
names = [n for n,c in counter.items() if c==max_cnt]
names.sort()
print(*names, sep='\n')
### BUGGY CODE ###

# import bisect
# from collections import Counter, deque # https://note.nkmk.me/python-scipy-connected-components/
# from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    N = int(input())

    i = 0
    print(i,flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    elif s=='Male':
        plsex=0
    else: plsex=1

    pl = 0
    pr = N
    while pl + 1 < pr:
        pc = (pl + pr) // 2
        print(pc,flush=True)

        s = str(input())
        if s == 'Vacant':
            sys.exit()
        elif s == 'Male':
            pcsex=0
            if (pc - pl) % 2 == 1 and plsex==pcsex:
                pr = pc
            else:
                plsex = pcsex
                pl = pc
        else:
            pcsex=1
            if (pc - pl) % 2 == 1 and plsex == pcsex:
                pr = pc
            else:
                plsex = pcsex
                pl = pc


resolve()


### FIXED CODE ###

N = int(input())


def query(i):
    print(i)
    s = input()
    if s == 'Vacant':
        exit()
    return s


root = query(0)


def is_ok(ind):
    # 左ならTrue
    response = query(ind)
    if ind % 2 == 1:
        return root == response
    else:
        return root != response


def bin_search_meguru():
    """
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng, okは,とり得る最小の値-1,とり得る最大の値+1
    """

    # 適当にいじる
    ng = -1  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')

dp = [INF] * n
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2,n):
    for j in range(1,min(i, k)+1):
        dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))

print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')

dp = [INF] * n
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2,n):
    for j in range(1,min(i, k)+1):
        dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))

print(dp[n-1])
### BUGGY CODE ###

R,G,B,N=map(int,input().split())

ans=0
for r in range(3000+1):
    for g in range(3000+1):
        if (N-r*R-g*G)%B==0:
            ans+=1
print(ans)

### FIXED CODE ###

R,G,B,N=map(int,input().split())

ans=0
for r in range(3000+1):
    if N < r*R:
        break
    for g in range(3000+1):
        if N < r*R+g*G:
            break
        if (N-r*R-g*G)%B==0:
#            print('({0}-{1}*{2}-{3}*{4})%{5}'.format(N,r,R,g,G,B))
            ans+=1
print(ans)
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
R = n//r+1
G = n//g+1
cnt = 0
for i in range(R+1):
    for j in range(G+1):
        t = n-i*r-j*g
        if t%b==0 and t>=0:
            cnt += 1
print(cnt)



### FIXED CODE ###

r,g,b,n = map(int,input().split())
R = n//r+1
G = n//g+1
cnt = 0
for i in range(R+1):
    for j in range(G+1):
        t = n-i*r-j*g
        if t%b==0 and t>=0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

from collections import defaultdict

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

rgb = defaultdict(list)

for i in range(n):
    if s[i] == 'R':
        rgb[0].append(i)
    elif s[i] == 'G':
        rgb[1].append(i)
    else:
        rgb[2].append(i)

ans = len(rgb[0]) * len(rgb[1]) * len(rgb[2])

for r in rgb[0]:
    for g in rgb[1]:
        tmp = sorted([r, g])
        if tmp[0] - (tmp[1]-tmp[0]) in rgb[2]:
            ans -= 1
        if tmp[1] + (tmp[1]-tmp[0]) in rgb[2]:
            ans -= 1
        if (tmp[1]+tmp[0]) % 2 == 0 and (tmp[1]+tmp[0])//2 in rgb[2]:
            ans -= 1

print(ans)


### FIXED CODE ###

from collections import defaultdict

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

rgb = defaultdict(list)
blue = defaultdict(int)

for i in range(n):
    if s[i] == 'R':
        rgb[0].append(i)
    elif s[i] == 'G':
        rgb[1].append(i)
    else:
        blue[i] = i

ans = len(rgb[0]) * len(rgb[1]) * len(blue)

for r in rgb[0]:
    for g in rgb[1]:
        tmp = sorted([r, g])
        if tmp[0] - (tmp[1]-tmp[0]) in blue:
            ans -= 1
        if tmp[1] + (tmp[1]-tmp[0]) in blue:
            ans -= 1
        if (tmp[1]+tmp[0]) % 2 == 0 and (tmp[1]+tmp[0])//2 in blue:
            ans -= 1

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

from bisect import insort_left
n, m = map(int, input().split())
d = [[] for _ in range(n + 1)]
m = [tuple(map(int, input().split())) for _ in range(m)]

for p, y in m:
    insort_left(d[p], y)
for p, y in m:
    print('{:06}{:06}'.format(p, d[p].index(y)+1))

### FIXED CODE ###

from bisect import bisect_left
from collections import defaultdict
n, m = map(int, input().split())
m = [tuple(map(int, input().split())) for _ in range(m)]

d = defaultdict(list)
for p, y in sorted(m):
    d[p] += [y]


for p, y in m:
    i = bisect_left(d[p], y)
    print('{:06}{:06}'.format(p, i+1))
### BUGGY CODE ###

a=[]
cp_a=[]
an = input()
a.append(int(an))
i=0
cp_a.append(a[0])
t_or_f = 0
m = 0
n = 0

for k in range(1000000):
    if int(a[i])%2==0:
        cal = int(a[i])* (1/2)
        next_i = i+1
        a.append(int(cal))
        cp_a.append(a[next_i])
        i = i+1
    elif int(a[i])%2!=0:
        next_i = i+1
        cal  = 3*int(a[i]) + 1
        a.append(int(cal))
        cp_a.append(a[next_i])
        i = i+1


for s in range(i):
    for t in range(s+1,i):
        if a[s]==cp_a[t]:
            n = s
            m = t
            print(m+1)
            t_or_f = 1
            break
    if t_or_f:
        break

# print(a)
# print(cp_a)





### FIXED CODE ###

a=[]
cp_a=[]
an = input()
a.append(int(an))
i=0
cp_a.append(a[0])
t_or_f = 0
m = 0
n = 0

for k in range(1000000):
    if int(a[i])%2==0:
        cal = int(a[i])* (1/2)
        next_i = i+1
        a.append(int(cal))
        cp_a.append(a[next_i])
        i = i+1
    elif int(a[i])%2!=0:
        next_i = i+1
        cal  = 3*int(a[i]) + 1
        a.append(int(cal))
        cp_a.append(a[next_i])
        i = i+1


    for s in range(i):
        for t in range(s+1,i):
            if a[s]==cp_a[t]:
                n = s
                m = t
                print(m+1)
                t_or_f = 1
                break
        if t_or_f:
            break
    if t_or_f:
        break

# print(a)
# print(cp_a)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0

for i in range(len(s)):
    for j in range(i+1,len(s)):
        if s[i] != s[j]:
            for k in range(j+1,len(s)):
                if s[i] != s[k] and s[j] != s[k]:
                    if ((j+1)-(i+1)) != ((k+1)-(j+1)):
                        ans += 1
    

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = s.count("R") * s.count("G") * s.count("B")

for i in range(n):
    for j in range(i+1,n):
        if s[i] != s[j]:
            k = j + (j - i)
            if k >= n or j >= n:
                break
            if s[i] != s[j] != s[k] != s[i]:
                # print(i, j, k)
                ans -= 1

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

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main():
    n, q = (int(s) for s in stdin.readline().split())
    s = [{i} for i in range(n)]

    for _ in range(q):
        com, x, y = (int(s) for s in stdin.readline().split())
        if com:
            for si in s:
                if x in si and y in si:
                    print(1)
                    break
            else:
                print(0)
        else:
            for si in s:
                if x in si:
                    a = si
                if y in si:
                    b = si
            if a != b:
                s.append(a | b)
                s.remove(a)
                s.remove(b)


main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main():
    n, q = (int(s) for s in stdin.readline().split())
    s = [{i} for i in range(n)]

    for _ in range(q):
        com, x, y = (int(s) for s in stdin.readline().split())
        if com:
            if x in s[x] and y in s[x]:
                print(1)
            else:
                print(0)
        else:
            a = s[x]
            b = s[y]
            if a is not b:
                a |= b
                for i in a:
                    s[i] = a


main()
### BUGGY CODE ###

import sys

MOD = 10**9 + 7

n = int(input())

a = list(map(int, input().split()))

sum = 0
for index, i in enumerate(a[:n - 1]):
    for j in a[index + 1:n]:
        sum += (i * j)

print(sum % MOD)

### FIXED CODE ###

import sys

MOD = 10**9 + 7

n = int(input())

a = list(map(int, input().split()))

x = pow(sum(a), 2)
y = sum((a[i]**2 for i in range(n)))

sum = (x - y) // 2 % MOD

print(sum)
### BUGGY CODE ###

N, M = (int(i) for i in input().split()) 

outs = [[] for i in range(N)]
ins = [0] * N


for _ in range(M):
    x, y = (int(i) for i in input().split())
    x -= 1
    y -= 1
    outs[x].append(y)
    ins[y] += 1

q = []
for i in range(N):
    if ins[i] == 0:
        q.append(i)

result = []
while q != []:
    qn = q.pop(0)
    result.append(qn)
    for v in outs[qn]:
        ins[v] -= 1
        if ins[v] == 0:
            q.append(v)


last = [0] * N
# last[i] = iが最後だったときに最長のパス
for sq in result:
    t = last[sq] + 1
    for v in outs[sq]:
        last[v] = max(last[v], t)

print(max(last))
     



### FIXED CODE ###

N, M = (int(i) for i in input().split()) 

outs = [[] for i in range(N)]
ins = [0] * N


for _ in range(M):
    x, y = (int(i) for i in input().split())
    x -= 1
    y -= 1
    outs[x].append(y)
    ins[y] += 1

q = []
for i in range(N):
    if ins[i] == 0:
        q.append(i)

result = []
while q != []:
    qn = q.pop()
    result.append(qn)
    for v in outs[qn]:
        ins[v] -= 1
        if ins[v] == 0:
            q.append(v)


last = [0] * N
# last[i] = iが最後だったときに最長のパス
for sq in result:
    for v in outs[sq]:
        last[v] = max(last[v], last[sq] + 1)

print(max(last))
### BUGGY CODE ###

from collections import deque

N, M = map(int,input().split())
root = [1]*N
side = [[]for i in range(N)]

for i in range(N+M-1):
    a,b = map(int,input().split())
    side[a-1].append(b-1)
    root[b-1] = 0

queue = deque([root.index(1)])
cost = [0]*N
oya = [0]*N
while queue:
    q = queue.popleft()
    for i in side[q]:
        if cost[i] <= cost[q]:
            cost[i] = cost[q]+1
            oya[i] = q+1
            queue.append(i)

for i in oya:
    print(i)


### FIXED CODE ###

from collections import deque

N, M = map(int,input().split())
count = [0]*N
side = [[]for i in range(N)]
rside = [[]for i in range(N)]

for i in range(N+M-1):
    a,b = map(int,input().split())
    side[a-1].append(b-1)
    rside[b-1].append(a-1)
    count[b-1] += 1
root = count.index(0)
queue = deque([root])
top = [0]*N

for i in range(N):
    q = queue.popleft()
    top[q] = i
    for k in side[q]:
        count[k] -= 1
        if count[k] == 0:
            queue.append(k)
for i in range(N):
    if rside[i] == []:
        print(0)
        continue
    ret = root
    for j in rside[i]:
        if top[ret] < top[j]:
            ret = j
    print(ret+1)
### BUGGY CODE ###

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

tree = {}
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a] = tree.get(a, []) + [b]

op = [0] * (n+1)
for i in range(q):
    p, x = map(int, input().split())
    op[p] += x

for root in tree:
    for i in tree[root]:
        op[i] += op[root]

print(*op[1:])


### FIXED CODE ###

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

tree = [[] for i in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)

op = [0] * (n+1)
for i in range(q):
    p, x = map(int, input().split())
    op[p] += x

for root, reaf in enumerate(tree):
    for i in reaf:
        op[i] += op[root]

print(*op[1:])
### BUGGY CODE ###

import math
A,B = map(int, input().split())

y = max(A,B)
x = min(A,B)
while y%x != 0:
  tmp = x
  x = y%x
  y = tmp

p = [1]
for val in range(2,x+1):
  flag = 1
  if val == 2 and x % val == 0:
    p.append(val)
  elif val % 2 != 0 and x % val == 0:
    for i in range(2,int(math.sqrt(val))+1):
      if val % i == 0:
        flag = 0
        break
    if flag == 1:
      p.append(val)
print(len(p))
  

### FIXED CODE ###

import math
A,B = map(int, input().split())

# 最大公約数の算出
y = max(A,B)
x = min(A,B)
while y%x != 0:
  tmp = x
  x = y%x
  y = tmp

# 素因数分解
p = []
tmp = int(math.sqrt(x))+1
for n in range(2,tmp):
  while x % n == 0:
    x /= n
    p.append(n)
p.append(int(x))
p.append(1)
p = list(set(p))
print(len(p))
### BUGGY CODE ###

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 = 10**6 + 7
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 = input()
n = len(S)
ans = 0
for i in range(K+1):
    ans += (cmb(i+n-1, n-1, mod)%mod * pow(25, i)%mod * pow(26, (K-i))%mod) % mod
print(ans%mod)

### FIXED CODE ###

# F - Strivore
import sys
MOD = 10**9+7
K = int(input())
S = input()
l = len(S)
ans = 0
 
tmp = pow(26,K,MOD)
ans = tmp
waru = pow(26,-1,MOD)
 
for i in range(1,K+1):
    tmp = (tmp*25*waru)%MOD
    tmp = (tmp*(l-1+i)*pow(i,-1,MOD))%MOD
    ans = (ans+tmp)%MOD
 
print(ans)