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

from collections import deque

S = [l for l in input()]
Q = int(input())
d = deque(S)

for i in range(Q):
    query = input()
    if query[0] == '1':
        d.reverse()
    else :
        t, f, c = query.split()
        if f == '1':
            d.appendleft(c)
        else :
            d.append(c)

print(''.join(d))

### FIXED CODE ###

from collections import deque

S = [l for l in input()]
Q = int(input())
d = deque(S)
direction = 'f'

for i in range(Q):
    query = input()
    if query[0] == '1':
        if direction == 'f':
            direction = 'r'
        else :
            direction = 'f'
    else :
        t, f, c = query.split()
        if f == '1':
            if direction == 'f':
                d.appendleft(c)
            else :
                d.append(c)
        else :
            if direction == 'f':
                d.append(c)
            else :
                d.appendleft(c)

if direction == 'r':
    d.reverse()

print(''.join(d))
### BUGGY CODE ###

import itertools

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))

ids = [x for x in range(n)]

store = list()
store.append(0)

for i in range(1, n+1):
    tmpcmb = list(itertools.combinations(ids, i))

    for k, i in enumerate(tmpcmb):
        tmpv = 0
        tmpc = 0
        for j in i:
            tmpv += v[j]
            tmpc += c[j]
        store.append(tmpv - tmpc)

result = max(store)
print(result)


### FIXED CODE ###

import itertools
import sys

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))

ids = [x for x in range(n)]

diff = [tmpv - tmpc for tmpv, tmpc in zip(v, c)]

result = 0

for i in range(1, n+1):
    tmp = list(itertools.combinations(diff, i))
    tmpMax = max([sum(x) for x in tmp])
    if tmpMax > result:
        result = tmpMax
    # store.extend([sum(x) for x in tmp])
    # print(store)
    # for x, y in zip(vset, cset):
    #     store.append(sum(x)-sum(y))

print(result)
### BUGGY CODE ###

def isPrefix(str1, str2):
    if str2[:len(str1)] == str1:
        return True
    else:
        return False

def isEarlier(str1, str2):
    for s1, s2 in zip(list(str1), list(str2)):
        if s1 != s2:
            if ord(s1) < ord(s2):
                return True
            else:
                return False

def main():
    #0.input
    s = input()
    K = int(input())
    
    #1. make subset
    subset = set()
    for k in range(1, len(s)+1):
        start = 0
        while start <= len(s)-k:
            subset.add(s[start:start+k])
            start += 1

    #2. get earliest one
    s_list = set(s)
    earliest = "z"
    for char in s_list:
        if ord(char) < ord(earliest):
            earliest = char
            
    #3. if K=1, end
    #    else, the get K-th one
    if K==1:
        print(earliest)
    else:
        k=1
        subset.remove(earliest)
        while True:
            subset_list = list(subset)
            earliest=subset_list[0]
            for element in subset_list[1:]:
                if (not isPrefix(earliest, element)) and (not isEarlier(earliest, element)):
                    earliest = element
            subset.remove(earliest)
            k += 1
                
            if k==K:
                print(earliest)
                break

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    #0.input
    s = input()
    K = int(input())
    
    #1. make subset
    subset = set()
    for k in range(1, min(len(s)+1, K+1)):
        start = 0
        while start <= len(s)-k:
            subset.add(s[start:start+k])
            start += 1
    
    subset_list = sorted(list(subset))
    print(subset_list[K-1])

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

import numpy as np
N = int(input())
X_arr = np.empty(N - 1, dtype = int)
  
ans = 0
for c in range(1, N):
  X_arr[c - 1] = N - c

for b in range(1, N):  
  ans += np.count_nonzero(X_arr % b == 0)
print(ans)

### FIXED CODE ###

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

import sys

def main():
    sinputl = sys.stdin.readline

    num_card, num_gate = [int(x) for x in sinputl().split()]
    input = [[int(x) for x in sinputl().split()] for _ in range(num_gate)]

    min_interval = [1, num_card]

    for gate in input:
        if (min_interval[1] - min_interval[0]) > (gate[1] - gate[0]):
            min_interval = gate

    cards = list(range(min_interval[0], min_interval[1] + 1))

    for gate in input:
        cards = list(filter(lambda x: gate[0] <= x <= gate[1], cards))

    print(len(cards))



if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

def main():
    sinputl = sys.stdin.readline

    num_card, num_gate = [int(x) for x in sinputl().split()]
    input = [[int(x) for x in sinputl().split()] for _ in range(num_gate)]

    card = [1, num_card]

    for gate in input:
        card[0] = max(card[0], gate[0])
        card[1] = min(card[1], gate[1])

    print(max(card[1] - card[0] + 1, 0))


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

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

#AB = list(range(A, B+1))
AB = [x for x in range(A, B+1)]

ans = []
while AB[-1] != 0:
    div = lambda x: x // 2
    rem = lambda x: x % 2
    
    AB_bit = list(map(rem, AB))
    AB = list(map(div, AB))
    ans.append(str(sum(AB_bit) % 2))

ans.append('0')
ans.reverse()
ans_10 = int(''.join(ans), 2)
print(ans_10)


### FIXED CODE ###

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

def cal_xor(X):
    X = X+1
    xor_sum = 0
    digit = 1
    while digit < X:
        digit *= 2
        bit_count = (X // digit) * (digit // 2)
        bit_count += max(0, (X % digit) - (digit // 2))
        
        if bit_count % 2 == 1:
            xor_sum += digit // 2
    
    return xor_sum
        

ans = cal_xor(A-1) ^ cal_xor(B)
print(ans)
### BUGGY CODE ###

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

dp = [1, 2]
A = [int(input()) for _ in range(M)]
if M != 0:
    if M >= 2 and A[0] == 1 and A[1] == 2:
        dp = [0, 0]
    elif A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]
else:
    A = [0]

MOD = 1000000007

if N == 1:
    while True:
        pass
    print (0)
if N == 2:
    print (dp[-1])
else:
    cnt = 0
    for n in range(2, N):
        while(cnt < M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

    print (dp[-1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
import numpy as np
N, M = map(int, input().split())

MOD = 1000000007
dp = np.zeros(N, dtype = int)
if M != 0:
    A = np.array([int(input()) for _ in range(M)], dtype = int)
    dp[A - 1] = -1


if dp[0] == -1 and dp[1] == -1:
    pass
else:
    if dp[0] == -1:
        dp[1] = 1
    elif N >= 2 and dp[1] == -1:
        dp[0] = 1
    elif N >= 2:
        dp[0] = 1
        dp[1] = 2
    else:
        dp[0] = 1


if N >= 3:
    for n in range(2, N):
        if dp[n] != -1:
            dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

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

N, M = (int(i) for i in input().split(' '))
ten = [i+1 for i in range(N)]
H = [int(i) for i in input().split(' ')]
dic = {}
for i in range(len(H)):
    list_item = H[i]
    dic[i+1] = list_item
A = []
for i in range(M):
    x, y = (int(a) for a in input().split(' '))
    if dic[x] == dic[y]:
        A.append(x)
        A.append(y)
    elif dic[x] > dic[y]:
        A.append(y)
    else:
        A.append(x)
    
B = set(A)
for i in B:
    ten.remove(i)
print(len(ten))

### FIXED CODE ###

n,m=map(int,input().split())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
ans=0
for v in range(1,n+1):
  for u in g[v]:
    if arr[u]>=arr[v]:
      break
  else:
    ans+=1
print(ans)
### BUGGY CODE ###

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    from collections import deque
    q = deque()
    p = deque()
    q.append(1)
    buf = 0
    flg = True
    idx = 1
    cnt = 0
    while flg:
        buf = idx
        idx = a[idx-1]
        cnt += 1
        if cnt == k:
            print(idx)
            return 0
        if idx in q:
            flg = False
        else:
            q.append(idx)
    for i in range(len(q)):
        tmp = q.pop()
        p.appendleft(tmp)
        if tmp == idx:
            break
    if k < len(q):
        print(list(q)[k%len(q)])
    else:
        k -= len(q)
        print(list(p)[k%len(p)])
    return 0

if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    # k<=10**18 < 2**60
    r = 60
    import math
    r = math.ceil(math.log2(k))
    idx = 0
    a = [a[i]-1 for i in range(n)]
    for i in range(r):
        if (k>>i)&1 == 1:
            idx = a[idx]
        a = [a[a[j]] for j in range(n)]
    print(idx+1)    

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

import numpy as np
import sys
if __name__ == "__main__":
    N, K = map(int, input().split())
    A = list(map(int, input().rstrip().split(' ')))
    visit = {1:[]}
    a_now = 1
    step = 0
    for i in range(K):
        a_now = A[a_now - 1]
        step += 1
        #print(a_now)
        self_loop = visit.get(a_now)
        if self_loop is None: # まだ訪れたことがない
            for v in visit.values():
                v.append(a_now)
            visit[a_now] = []
        else:
            self_loop.append(a_now)
            break
        #print(visit)
        if step == K:
            #print("K:")
            print(a_now)
            sys.exit()
    ## self_loop が見つかった場合
    #print("a_now:{}".format(a_now))
    #print("step:{}".format(step))
    #print(self_loop)
    n = len(self_loop)
    left = K-step
    left -= (left // n) * n
    #print(step)
    print(self_loop[left - 1])
    

### FIXED CODE ###

import numpy as np
import sys
if __name__ == "__main__":
    N, K = map(int, input().split())
    A = list(map(int, input().rstrip().split(' ')))
    visit = [False]*N
    a_now = 1
    visit[a_now - 1] = True
    step = 0
    for i in range(N):
        a_now = A[a_now - 1]
        step += 1
        #print(a_now)
        if visit[a_now - 1]:
            break
        else:
            visit[a_now - 1] = True
        if step == K:
            #print("K:")
            print(a_now)
            sys.exit()
    
    self_loop = []
    start = a_now
    for i in range(N):
        a_now = A[a_now - 1]
        step += 1
        self_loop.append(a_now)
        if a_now == start:
            break
        if step == K:
            #print("K:")
            print(a_now)
            sys.exit()
    
    ## self_loop が見つかった場合
    #print("a_now:{}".format(a_now))
    #print("step:{}".format(step))
    #print(self_loop)
    n = len(self_loop)
    left = K-step
    left -= (left // n) * n
    #print(step)
    print(self_loop[left - 1])
### BUGGY CODE ###

R,C,K=map(int, input().split())
M=[[0 for i in range(C)]for i in range(R)]
for i in range(K):
  r,c,v=map(int, input().split())
  r-=1
  c-=1
  M[r][c]=v
dp=[[[0]*(4) for j in range(C)] for i in range(R)]
dp[0][0][1]+=M[0][0]
for r in range(R):
  for c in range(C):
    if 0<r:
      dp[r][c][1]=max(max(dp[r-1][c])+M[r][c],dp[r][c][1])
      dp[r][c][0]=max(max(dp[r-1][c]),dp[r][c][0])
    if 0<c:
      dp[r][c][3]=max(dp[r][c-1][2]+M[r][c],dp[r][c][3],dp[r][c-1][3])
      dp[r][c][2]=max(dp[r][c-1][1]+M[r][c],dp[r][c][2],dp[r][c-1][2])
      dp[r][c][1]=max(dp[r][c-1][0]+M[r][c],dp[r][c][1],dp[r][c-1][1])
      dp[r][c][0]=max(dp[r][c-1][0],dp[r][c][0])
print(max(dp[-1][-1]))

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
  R,C,K=map(int, input().split())
  M=[[0 for i in range(C)]for i in range(R)]
  for i in range(K):
    r,c,v=map(int, input().split())
    r-=1
    c-=1
    M[r][c]=v
  dp0=[[0 for j in range(C)] for i in range(R)]
  dp1=[[0 for j in range(C)] for i in range(R)]
  dp2=[[0 for j in range(C)] for i in range(R)]
  dp3=[[0 for j in range(C)] for i in range(R)]
  dp1[0][0]+=M[0][0]
  for r in range(R):
    for c in range(C):
      if 0<r:
        dp1[r][c]=max(max(dp1[r-1][c],dp2[r-1][c],dp3[r-1][c])+M[r][c],dp1[r][c])
        dp0[r][c]=max(max(dp1[r-1][c],dp2[r-1][c],dp3[r-1][c]),dp0[r][c])
      if 0<c:
        dp3[r][c]=max(dp2[r][c-1]+M[r][c],dp3[r][c],dp3[r][c-1])
        dp2[r][c]=max(dp1[r][c-1]+M[r][c],dp2[r][c],dp2[r][c-1])
        dp1[r][c]=max(dp0[r][c-1]+M[r][c],dp1[r][c],dp1[r][c-1])
        dp0[r][c]=max(dp0[r][c-1],dp0[r][c])
  ans=0
  for i in range(R):
    for j in range(C):
      ans=max(ans,dp1[i][j],dp2[i][j],dp3[i][j])
  print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# coding: utf-8
import sys
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
sys.setrecursionlimit(10**7)
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]
    for a,b in zip(A,B):
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    stack = []
    seen[1] = True
    heappush(stack, (0, 1, 0))# (distance, node, prev)
    mark = [0] * (N+1)
    done = [False] * (N+1)

    while True:
        try:
            dist, current, prev = heappop(stack)
        except:
            break
        seen[current] = True
        if not done[current]:
            done[current] = True
            mark[current] = prev
        for next in to[current]:
            if not seen[next]:
                heappush(stack, (dist+1, next, current))

    print('Yes')
    mark = [str(val) for val in mark]
    print('\n'.join(mark[2:]))

if __name__ == "__main__":
    run()


### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
from collections import deque
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]
    for a,b in zip(A,B):
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    queue = deque([])
    seen[1] = True
    queue.append((1, 0))# (node, prev)
    mark = [0] * (N+1)

    while queue:
        current, prev = queue.popleft()
        for next in to[current]:
            if not seen[next]:
                queue.append((next, current))
                mark[next] = current
                seen[next] = True

    print('Yes')
    mark = [str(val) for val in mark]
    print('\n'.join(mark[2:]))

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

import sys

n = int(input())
list_input = list(map(int, input().split()))

a = 1
for i in list_input:
    a = a * i

if a > pow(10, 18):
    print(-1)
else:
    print(a)


### FIXED CODE ###

import sys

n = int(input())
list_input = list(map(int, sys.stdin.readline().strip().split()))

if 0 in list_input:
    print(0)
    exit()

a = 1
for i in list_input:
    a *= i
    if a > pow(10, 18):
        break


if a > pow(10, 18):
    print(-1)
else:
    print(a)
### BUGGY CODE ###

S = input()
INF = 10**9+7
dp = [0,0,0]
Q = 0
for i in range(len(S)):
  if S[i]=='A':
    dp[0] += 3**Q
    dp[0] %= INF
  elif S[i]=='B':
    dp[1] += dp[0]
    dp[1] %= INF
  elif S[i]=='C':
    dp[2] += dp[1]
    dp[2] %= INF
  else:
    a = dp[0] + 3**Q
    b = dp[1] + dp[0]
    c = dp[2] + dp[1]
    dp[0] = a + dp[0]*2
    dp[1] = b + dp[1]*2
    dp[2] = c + dp[2]*2
    dp[0] %= INF
    dp[1] %= INF
    dp[2] %= INF
    Q += 1
print(dp[2])

### FIXED CODE ###

S = input()
INF = 10**9+7
dp = [0,0,0]
N = 1
for i in range(len(S)):
  if S[i]=='A':
    dp[0] += N
    dp[0] %= INF
  elif S[i]=='B':
    dp[1] += dp[0]
    dp[1] %= INF
  elif S[i]=='C':
    dp[2] += dp[1]
    dp[2] %= INF
  else:
    a = dp[0]
    b = dp[1]
    dp[0] = N + dp[0]*3
    dp[1] = a + dp[1]*3
    dp[2] = b + dp[2]*3
    dp[0] %= INF
    dp[1] %= INF
    dp[2] %= INF
    N = (3*N)%INF
print(dp[2]%INF)
### BUGGY CODE ###

def f(s):
    _s = s + '*'
    i = 0
    ans = 0
    while True:
        if _s[i] == '*':
            return _s[:-1], ans
        elif _s[i+1] == '*':
            i += 1
        elif _s[i] == _s[i+1]:
            i += 1
        else:
            ans += 2
            if i == 0:
                _s = _s[i+2:]
            else:
                _s = _s[:i] + _s[i+2:]


s = input()
ans = 0
while True:
    s, _ans = f(s)
    if _ans != 0:
        ans += _ans
    else:
        break
print(ans)

### FIXED CODE ###

s = input()
c0 = 0
c1 = 0
for i in range(len(s)):
    if s[i] == '0':
        c0 += 1
    else:
        c1 += 1
print(2 * min(c0, c1))
### BUGGY CODE ###

X,Y,Z,K = map(int,input().split())
A, B, C = list(map(int,input().split())),  list(map(int,input().split())),  list(map(int,input().split()))
AB = sorted([a+b for a in A for b in B],reverse=True)
ABC = sorted([ab+c for ab in AB[:K] for c in sorted(C)[:K]],reverse=True)
[print(abc) for abc in sorted(ABC,reverse=True)[:K]]

### FIXED CODE ###

import heapq

X,Y,Z,K = map(int,input().split())
A, B, C = [sorted(list(map(int,input().split())),reverse=True) for _ in range(3)]

Q = []
heapq.heappush(Q, [-(A[0]+B[0]+C[0]),0,0,0])
for _ in range(K):
  p, i, j, k = heapq.heappop(Q)
  print(-p)
  if i+1<X and [-(A[i+1]+B[j]+C[k]),i+1,j,k] not in Q: heapq.heappush(Q, [-(A[i+1]+B[j]+C[k]),i+1,j,k])
  if j+1<Y and [-(A[i]+B[j+1]+C[k]),i,j+1,k] not in Q: heapq.heappush(Q, [-(A[i]+B[j+1]+C[k]),i,j+1,k])
  if k+1<Z and [-(A[i]+B[j]+C[k+1]),i,j,k+1] not in Q: heapq.heappush(Q, [-(A[i]+B[j]+C[k+1]),i,j,k+1])
### BUGGY CODE ###

N, Q = map(int, input().split())
S=list(input())
list=[0]*N
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        list[i]+=1
count=0
for j in range(Q):
    l, r = map(int, input().split())
    print(sum(list[l-1:r-1]))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

ans = [0]*N
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        ans[i+1] += (ans[i]+1)
    else:
        ans[i+1] = ans[i] 

for i in range(Q):
    l, r = map(int, input().split())
    print(ans[r-1] - ans[l-1])
### BUGGY CODE ###

s = input()
n = len(s)
ANS = [0] * n
tame =0
sw=1
for i in range(n):
    if s[i] == "R":
        sw=1
        tame += 1
    elif sw==1:
        ANS[i-1] += tame//2+tame%2
        ANS[i] += tame//2
        sw=0
        tame=0
sw=1
tame=0
for i in range(n-1,-1,-1):
    if s[i] == "L":
        sw=1
        tame += 1
    elif sw==1:
        ANS[i+1] += tame//2+tame%2
        ANS[i] += tame//2
        sw=0
        tame=0
#print(ANS)
ans=""
for i in range(n):
    ans += str(ANS[i])
    ans += " "
print(ans)

### FIXED CODE ###

s = input()
n = len(s)
S=[0 for i in range(n)]
for i in range(n):
    if s[i]=="R":
        S[i]=1


ANS =[0 for i in range(n)]
tame =[0,0]
k=0
for i in range(n):
    if S[i] == 1:
        tame[k]+=1
        k = (k+1)%2
    elif tame[0]>0:
        ANS[i-1] += tame[0]
        ANS[i] += tame[1]
        tame=[0,0]
        k=0
tame =[0,0]
k=0
for i in range(n-1,-1,-1):
    if S[i] == 0:
        tame[k]+=1
        k = (k+1)%2
    elif tame[0]>0:
        ANS[i+1] += tame[0]
        ANS[i] += tame[1]
        tame=[0,0]
        k=0
#print(ANS)
ans=""
for i in range(n):
    ans += str(ANS[i])
    ans += " "
print(ans)
#print(n)
### BUGGY CODE ###

X = int(input())

#x^5-y^5=(x-y)(x^4+x^3y+x^2y^2+xy^3+y^4)

#for x in range(1, 121):
#  if ((x**5) - ((x-1)**5)) >= 1000000000:
#    print(x)

for a in range(0, 121):
  for b in range(-100000, 120):
    if b**5 == a**5-X:
      print(a, b)
      break



### FIXED CODE ###

X = int(input())

#x^5-y^5=(x-y)(x^4+x^3y+x^2y^2+xy^3+y^4)

#for x in range(1, 121):
#  if ((x**5) - ((x-1)**5)) >= 1000000000:
#    print(x)

for a in range(0, 121):
  for b in reversed(range(-122, 120)):
    if b**5 == a**5-X:
      print(a, b)
      exit()
### BUGGY CODE ###

A, B, N = map(int,input().split())
bst = -100000000

for i in range(N):
  ans = (A*(i+1))//B - A*((i+1)//B)
  if (ans > bst):
    bst = ans
print(bst)

### FIXED CODE ###

A,B,N = map(int, input().split())
p = min(N,B)

if p%B == 0:
    print(int(A*(p-1)//B))
else :
    print(int(A*(p)//B))
### BUGGY CODE ###

#ABC088-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w=IL()
G=[S() for i in range(h)]
used=[[False for i in range(w)] for j in range(h)]
q=[[0,0,1]]
pos=False
while len(q)>0:
    gy,gx,dis=q.pop(0)
    if gy==h-1 and gx==w-1:
        pos=True
        break
    if not used[gy][gx]:
        if gy!=0:
            if G[gy-1][gx]=="." and not used[gy-1][gx]:
                q.append([gy-1,gx,dis+1])
        if gx!=0:
            if G[gy][gx-1]=="." and not used[gy][gx-1]:
                q.append([gy,gx-1,dis+1])
        if gy!=h-1:
            if G[gy+1][gx]=="." and not used[gy+1][gx]:
                q.append([gy+1,gx,dis+1])
        if gx!=w-1:
            if G[gy][gx+1]=="." and not used[gy][gx+1]:
                q.append([gy,gx+1,dis+1])
if pos:
    ans=0
    for i in range(h):
        ans+=G[i].count(".")
    print(ans-dis)
else:
    print(-1)

### FIXED CODE ###

#ABC088-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w=IL()
G=[S() for i in range(h)]
used=[[False for i in range(w)] for j in range(h)]
q=[[0,0,1]]
pos=False
while len(q)>0:
    gy,gx,dis=q.pop(0)
    if gy==h-1 and gx==w-1:
        pos=True
        break
    if not used[gy][gx]:
        if gy!=0:
            if G[gy-1][gx]=="." and not used[gy-1][gx]:
                q.append([gy-1,gx,dis+1])
        if gx!=0:
            if G[gy][gx-1]=="." and not used[gy][gx-1]:
                q.append([gy,gx-1,dis+1])
        if gy!=h-1:
            if G[gy+1][gx]=="." and not used[gy+1][gx]:
                q.append([gy+1,gx,dis+1])
        if gx!=w-1:
            if G[gy][gx+1]=="." and not used[gy][gx+1]:
                q.append([gy,gx+1,dis+1])
    used[gy][gx]=True
if pos:
    ans=0
    for i in range(h):
        ans+=G[i].count(".")
    print(ans-dis)
else:
    print(-1)
### BUGGY CODE ###

from numba import njit

P = 10**9+7

nn = 2002002
fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P


def C(a, b): return fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0


@njit('i8(i8, i8, i8)', cache=True)
def mod_pow(x, a, MOD):
    ret = 1
    cur = x
    while a:
        if a & 1:
            ret = ret * cur % MOD
        cur = cur * cur % MOD
        a >>= 1
    return ret


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

ans = 0
po = 1
poo = 26 ** K
for i in range(K+1):
    ans += (C(i+M-1, i) * mod_pow(25, i, P) % P * mod_pow(26, K-i, P)) % P
    ans %= P
print(ans)


### FIXED CODE ###

n_ = 2 * 10**6 + 5
mod = 10**9 + 7
fun = [1] * (n_ + 1)
for i in range(1, n_ + 1):
    fun[i] = fun[i - 1] * i % mod
rev = [1] * (n_ + 1)
rev[n_] = pow(fun[n_], mod - 2, mod)
for i in range(n_ - 1, 0, -1):
    rev[i] = rev[i + 1] * (i + 1) % mod


def nCr(n, r):
    if r > n:
        return 0
    return fun[n] * rev[r] % mod * rev[n - r] % mod


def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    return u % mod


inv26 = modinv(26, mod)

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

ans = 0
po = 1
poo = pow(26, K, mod)
for i in range(K+1):
    ans = (ans + po * poo % mod * nCr(i+M-1, i)) % mod
    po = po * 25 % mod
    poo = poo * inv26 % mod
print(ans)