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

Q = int(input())
l = [0]*Q
for i in range(Q):
    l[i] = list(map(int,input().split()))

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

for i in range(Q):
    sum = 0
    for j in range(l[i][0],l[i][1]+1):
        if is_prime(j) and is_prime((j+1)//2):
            sum +=1
        else:
            continue
    print(sum)

### FIXED CODE ###

import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
INF = float("inf")

Q = int(input())
l = [0]*Q
Sum = [0]*(10**5+1)
for i in range(Q):
    l[i] = list(map(int,input().split()))

def is_prime(n):
    for i in range(2,int(math.sqrt(n))+1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1
for i in range(3,10**5+1,2):
    if is_prime(i) and is_prime((i+1)//2):
        Sum[i] = Sum[i-2]+1
    else:
        Sum[i] = Sum[i-2]

for i in range(Q):
    if l[i][1] ==1:
        print(0)
    elif l[i][0] == 1:
        print(Sum[l[i][1]])
    else:
        print(Sum[l[i][1]]-Sum[l[i][0]-2])
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
cx,cy=map(int,input().split())
cx+=1
cy+=1
dx,dy=map(int,input().split())
dx+=1
dy+=1
l=[]
l.append("#"*(w+4))
l.append("#"*(w+4))
for i in range(h):
    l.append("##"+input()+"##")
l.append("#"*(w+4))
l.append("#"*(w+4))
#input

"""
for i in l:
    print(*i)
"""

q=deque([[cx,cy]])
qq=deque([[cx,cy]])
s=[[-1 for i in j]for j in l]
s[cx][cy]=0

while len(qq)>0:
    while len(q)>0:
        x,y=q.popleft()
        for px,py in ((0,1),(0,-1),(1,0),(-1,0)):
            if l[x+px][py+y]=="." and s[x+px][y+py]==-1:
                s[x+px][y+py]=s[x][y]
                q.appendleft([x+px,y+py])
                qq.append([x+px,y+py])
    x,y=qq.popleft()
    for px in range(-2,3):
        for py in range(-2,3):
            if l[x+px][py+y]=="." and s[x+px][y+py]==-1:
                s[x+px][y+py]=s[x][y]+1
                q.append([x+px,y+py])
                qq.append([x+px,y+py])
"""
for i in s:
    print(*i)
"""

print(s[dx][dy])

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
cx,cy=map(int,input().split())
cx+=1
cy+=1
dx,dy=map(int,input().split())
dx+=1
dy+=1
l=[]
l.append("#"*(w+4))
l.append("#"*(w+4))
for i in range(h):
    l.append("##"+input()+"##")
l.append("#"*(w+4))
l.append("#"*(w+4))
#input

"""
for i in l:
    print(*i)
"""

q=deque([[cx,cy]])
qq=deque([[cx,cy]])
s=[[-1 for i in j]for j in l]
s[cx][cy]=0

while len(qq)>0:
    while len(q)>0:
        x,y=q.popleft()
        for px,py in ((0,1),(0,-1),(1,0),(-1,0)):
            if l[x+px][py+y]=="." and s[x+px][y+py]==-1:
                s[x+px][y+py]=s[x][y]
                q.appendleft([x+px,y+py])
                qq.append([x+px,y+py])
    x,y=qq.popleft()
    for px in range(-2,3):
        for py in range(-2,3):
            if l[x+px][py+y]=="." and s[x+px][y+py]==-1:
                s[x+px][y+py]=s[x][y]+1
                q.append([x+px,y+py])
                qq.append([x+px,y+py])
"""
for i in s:
    print(*i)
"""

print(s[dx][dy])
### BUGGY CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
ans="Yes"
if n>3:
    for i in range(n-1):
        if a.count(a[i])!=a.count(a[i+1]) or a.count(a[i])==1:
            ans="No"
            break
print(ans)

### FIXED CODE ###

n=int(input())
L=list(map(int,input().split()))
LL=list(set(L))
ans="No"
if LL==[0]:
    ans="Yes"
elif len(LL)==2:
    if L.count(LL[0])==2*L.count(LL[1]) or L.count(LL[1])==2*L.count(LL[0]):
        ans="Yes"
elif len(LL)==3:
    if L.count(LL[0])==L.count(LL[1]) and L.count(LL[1])==L.count(LL[2]):
        if LL[0]^LL[1]^LL[2]==0:
            ans="Yes"
print(ans)
### BUGGY CODE ###

a, b, c, k = map(int, input().split())

sum = (a + b + c) * (2 ** k)

ans = b - a if k % 2 == 1 else a - b

print(ans if ans <= 10**18 else "Unfair")


### FIXED CODE ###

a, b, c, k = map(int, input().split())

ans = b - a if k % 2 == 1 else a - b

print(ans if ans <= 10**18 else "Unfair")
### BUGGY CODE ###

def fibonacci(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
        

print(fibonacci(int(input())))


### FIXED CODE ###

import sys
input = sys.stdin.readline


def inpl():
    return list(map(int, input().split()))


def f(n):
    if n < 2:
        return 1
    ret = [0] * (n + 1)
    ret[0] = 1
    ret[1] = 1
    for i in range(2, n + 1):
        ret[i] = ret[i - 2] + ret[i - 1]
    return ret[n]


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

import bisect
import numpy as np
class BinaryIndexedTree():
    def __init__(self,size):
        self.BIT = np.zeros(size+1,dtype=int)
    def query(self,index):
        #sum of A1 ~ Ai O(logN)
        ret=0
        while index > 0:
            ret += self.BIT[index]
            index -= index & (-index)
        return ret
    def update(self,index,x):
        #add x to Ai O(logN)
        while index <=  len(self.BIT)-1:
            self.BIT[index] += x
            index += index & (-index)
        return
n=int(input())
a=list(map(int,input().split()))
if n==1:print(a[0]);exit()
elif n==2:print(a[1]);exit()
ng=2*max(a)+20
ok=0
while ng-ok>1:
    check=(ok+ng)//2
    cnt=0 #check以上の要素の数
    s=np.empty(n+1,int)
    s[0]=0
    B=BinaryIndexedTree(n+1)
    for i in range(1,n+1):
        if a[i-1]<check:s[i]=s[i-1]-1
        else:s[i]=s[i-1]+1
    
    # 座標圧縮
    S=sorted(s)
    for i,e in enumerate(s):
        s[i]=bisect.bisect_left(S,e)
    for i,e in enumerate(s):
        cnt += B.query(e+1)
        B.update(e+1,1)
    if cnt >= ((n+1)*n)//4:
        ok = check
    else:
        ng = check
print(ok)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a2=sorted(set(a))
L=len(a2)
if n==1:print(a[0]);exit()
elif n==2:print(a[1]);exit()
ng=L
ok=0
while ng-ok>1:
    check=a2[(ok+ng)//2]
    cnt=0 #check以上の要素の数
    idx=n
    cl=[0]*(2*n+1)
    cl[n]=1
    Ru=0
    for i in range(n):
        if a[i]<check:
            Ru-=cl[idx]-1
            idx-=1
        else:
            idx+=1
            Ru+=cl[idx]+1
        cnt += Ru
        cl[idx]+=1
    if cnt >= ((n+1)*n//2)//2:
        ok = (ok+ng)//2
    else:
        ng = (ok+ng)//2
print(a2[ok])
### BUGGY CODE ###

from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7


def inp(): return int(sys.stdin.readline())


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


def inpl_str(): return list(sys.stdin.readline().split())


H, W, K = inpl()
SS = [list(map(int, str(input()))) for _ in range(H)]

ans = INF

for bit in range(1 << H-1):
    tmpSS = []
    nSS = []
    for b in range(H):
        nSS.append(SS[b])
        # print(bin(bit), nSS)
        if bit & (1 << b) != 0:
            tmpSS.append(nSS)
            nSS = []

    tmpSS.append(nSS)
    tmp_ans = len(tmpSS) - 1
    nSS = []
    for tmpS in tmpSS:
        nS = np.zeros(W)
        for tS in tmpS:
            nS += tS
        # print(nS)
        nSS.append(nS)

    L = len(nSS)
    tmpl = [0]*L
    for x in range(W):
        for y in range(L):
            tmpl[y] += nSS[y][x]

        if max(tmpl) > K:
            for y in range(L):
                tmpl[y] = nSS[y][x]
            tmp_ans += 1
            if max(tmpl) > K:
                tmp_ans = INF

    ans = min(ans, tmp_ans)

print(ans)


### FIXED CODE ###

from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7


def inp(): return int(sys.stdin.readline())


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


def inpl_str(): return list(sys.stdin.readline().split())


H, W, K = inpl()
SS = [list(map(int, str(input()))) for _ in range(H)]

ans = INF

for bit in range(1 << H-1):
    tmpSS = []
    nSS = []
    for b in range(H):
        nSS.append(SS[b])
        # print(bin(bit), nSS)
        if bit & (1 << b) != 0:
            tmpSS.append(nSS)
            nSS = []

    tmpSS.append(nSS)
    tmp_ans = len(tmpSS) - 1
    nSS = []

    for tmpS in tmpSS:
        L = len(tmpS)
        nS = [0]*W
        for x in range(W):
            for y in range(L):
                nS[x] += tmpS[y][x]
        nSS.append(nS)

    # print(nSS)

    L = len(nSS)
    tmpl = [0]*L
    for x in range(W):
        for y in range(L):
            tmpl[y] += nSS[y][x]

        if max(tmpl) > K:
            for y in range(L):
                tmpl[y] = nSS[y][x]
            tmp_ans += 1
            if max(tmpl) > K:
                tmp_ans = INF

    ans = min(ans, tmp_ans)

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

from fractions import gcd
n=int(input())
ans=0
for i in range(1,n+1):
  for k in range(i,n+1):
    for _ in range(k,n+1):
      g=gcd(gcd(i,k),_)
      if i==_:
        ans+=g
      elif i==k or k==_:
        ans+=g*3
      else:
        ans+=g*6
print(ans)

### FIXED CODE ###

from fractions import gcd
n=int(input())
ans=0
for i in range(1,n+1):
  for k in range(i,n+1):
    gc=gcd(i,k)
    for _ in range(k,n+1):
      g=gcd(gc,_)
      if i==_:
        ans+=g
      elif i==k or k==_:
        ans+=g*3
      else:
        ans+=g*6
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LIR(n)
    n1 = 1 << n
    dp = [0] * n1
    dp[0] = 1
    q = deque()
    q.append(0)
    for i in range(n):
        ai = a[i]
        nq = deque()
        while q:
            p = q.pop()
            for j in range(n):
                if ai[j]:
                    j1 = 1 << j
                    if p & j1:
                        continue
                    nq.append(p | j1)
                    dp[p | j1] += dp[p]
                    if dp[p | j1] >= mod:
                        dp[p | j1] %= mod
        q = nq
    print(dp[-1])


    return


#main
if __name__ == '__main__':
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LIR(n)
    n1 = 1 << n
    dp = [0] * n1
    dp[0] = 1
    b = [0]
    for i in range(n):
        b += [x + 1 for x in b]
    # print(b)
    c = [1 << i for i in range(n)]
    for i in range(n1-1):
        p = b[i]
        ap = a[p]
        for j in range(n):
            if ap[j]:
                j1 = c[j]
                if i & j1:
                    continue
                dp[i|j1] += dp[i]


    print(dp[-1] % mod)


    return


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

def main():
    N = int(input())
    S = []
    for _ in range(N):
        S.append(''.join(sorted(list(input()))))
    cnt = 0
    for i in range(N-1):
        for j in range(i+1,N):
            if S[i] == S[j]:
                cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def main():
    N = int(input())
    S = defaultdict(int)
    for _ in range(N):
        s = ''.join(sorted(list(input())))
        if s in S:
            S[s] += 1
        else:
            S.update({s:0})
    cnt = 0
    for k,v in S.items():
        if v == 0:
            continue
        elif v == 1:
            cnt += v
        else:
            cnt += combinations_count(v+1,2)
    print(cnt)

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

N,M=[int(x) for x in input().split()]
X=[0,2,5,5,4,5,6,3,7,6]
#    1,2,3,4,5,6,7,8,9

A=[int(x) for x in input().split()]



def po(num):
	ans=1
	if num!=0:
		while (num//10>=1):
			ans+=1
			num=num//10
	return ans-1

ANS=[0]
for i in range(1,N+1):
	ans=0
	for j in A:
		if i==X[j]:
			ans=max(j,ans)
		elif i>=X[j]:
			temp=ANS[i-X[j]]
			if temp!=0:
				power=po(temp)
				ans=max(ans,10*temp+j)
		
		#print(ans)
	ANS.append(ans)
print(ANS[-1])
	


### FIXED CODE ###

N,M=[int(x) for x in input().split()]
X=[0,2,5,5,4,5,6,3,7,6]
#    1,2,3,4,5,6,7,8,9

A=[int(x) for x in input().split()]



ANS=[0]
for i in range(1,N+1):
	ans=0
	for j in A:
		if i==X[j]:
			ans=max(j,ans)
		elif i>=X[j]:
			temp=ANS[i-X[j]]
			if temp!=0:

				ans=max(ans,10*temp+j)
		
		#print(ans)
	ANS.append(ans)
print(ANS[-1])
### BUGGY CODE ###

s=input()

res=0
l=list(s)
while len(l)>1:
  if l[0]==l[-1]:
    l.pop(0)
    l.pop(-1)
  elif l[0]=="x":
    l.append("x")
    res+=1
  elif l[-1]=="x": 
    l.insert(0,"x")
    res+=1
  else:
    print(-1)
    exit()
    
print(res)

### FIXED CODE ###

s=input()

res=0
while len(s)>1:
  if s[0]==s[-1]:
    s=s[1:-1]
  elif s[0]=="x":
    s=s+"x"
    res+=1
  elif s[-1]=="x": 
    s="x"+s
    res+=1
  else:
    print(-1)
    exit()
    
print(res)
### BUGGY CODE ###

def main():
    N, Q = map(int, input().split())
    S = input()
    s_list = [str(c) for c in S]
    q_list = [list(map(int, input().split())) for i in range(Q)]

    ac_list = list()
    # get AC start point
    for i, n in enumerate(s_list):
        if n == "A" and i != (len(s_list) - 1):
            if s_list[i + 1] == "C":
                ac_list.append(i + 1)

    # answer Q
    for qs in q_list:
        counter = 0
        for start in ac_list:
            if qs[0] <= start and start < qs[1]:
                counter += 1
            if start >= qs[1]:
                break
        print(counter)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, Q = map(int, input().split())
    S = input()
    s_list = [str(c) for c in S]
    q_list = [list(map(int, input().split())) for i in range(Q)]

    ac_list = list()
    # get AC start point
    for i, n in enumerate(s_list):
        if n == "A" and i != (len(s_list) - 1):
            if s_list[i + 1] == "C":
                ac_list.append(i + 1)

    # set list
    temp = list()
    pre = 0
    counter = 0
    for s in ac_list:
        for i in range(pre, s):
            temp.append(counter)
        pre = s
        counter += 1

    for i in range(pre, N):
        temp.append(counter)

    # answer Q
    for qs in q_list:
        print(temp[qs[1] - 1] - temp[qs[0] - 1])


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

mod = int(1e9+7)
n, m = [int(num) for num in input().split()]

x = [int(x) for x in input().split()]
y = [int(y) for y in input().split()]

sumx = 0
for i in range(n-1):
    sumx += sum(x[i+1:]) - x[i] * ((n-1) - (i+1) + 1)
sumy = 0
for k in range(m-1):
    sumy += sum(y[k+1:]) - y[k] * ((m-1) - (k+1) + 1)

ans = ((sumx % mod) * (sumy % mod)) % mod

print(ans)

### FIXED CODE ###

# 予めsx, syを全て計算しておく
# このとき漸化式を使えば毎回全ての話を求める必要がない

mod = int(1e9+7)
n, m = [int(num) for num in input().split()]

x = [int(x) for x in input().split()]
y = [int(y) for y in input().split()]


sx = [0] * n
sx[0] = x[0]
for i in range(n-1):
    sx[i+1] = sx[i] + x[i+1]
sxd = 0  
for i in range(n-1):
    sxd += ((sx[n-1] - sx[i]) - x[i] * ((n-1) - (i+1) + 1)) % mod

sy = [0] * m
sy[0] = y[0]
for k in range(m-1):
    sy[k+1] = sy[k] + y[k+1]
syd = 0
for k in range(m-1):
    syd += ((sy[m-1] - sy[k]) - y[k] * ((m-1) - (k+1) + 1)) % mod

ans = ((sxd % mod) * (syd % mod)) % mod

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

x = input().split()
A, B, K = [int(i) for i in x]
for i in range(K):
  if A >= 1:
    A -= 1
  elif B >= 1:
    B -= 1
print(str(A)+" "+str(B))

### FIXED CODE ###

x = input().split()
A, B, K = [int(i) for i in x]
if A - K > 0:
  print(str(A-K) + " " + str(B))
elif A+B-K > 0:
  print("0" + " " + str(A+B-K))
else:
  print("0 0")
### BUGGY CODE ###

# 数え上げで制約が 2 乗っぽいのでどうせ dp だろという気持ちになる
# なんで入力が数字で与えられるのかを考えるとちょっと視界が開ける

# よく考えると、できる列の制約は
# 「赤い/青いボールはできる列の i 個目までに A[i]/B[i] 個使える」
# と表せることがわかる
# これに気付けばあとは
#     dp[i][j] := i 個目まで並べたとき赤いボールを j 個使う場合の数
# とした dp が自然と思いつく

from itertools import accumulate

def main():
    mod = 998244353
    B = list(map(int, input()))
    N = len(B)
    A = [2-b for b in B] + [0]*N
    B += [0] * N
    a = b = 0
    for i in range(2*N):
        b += B[i]
        if b > 0:
            b -= 1
            B[i] = 1
        a += A[i]
        if a > 0:
            a -= 1
            A[i] = 1

    A = list(accumulate(A))
    B = list(accumulate(B))

    dp = [[0]*(2*N+2) for _ in range(2*N+1)]
    dp[0][0] = 1
    for i, (a, b) in enumerate(zip(A, B), 1):
        for j in range(2*N+1):
            if i - b <= j <= a:
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod

    print(sum(dp[2*N]) % mod)

main()


### FIXED CODE ###

# 数え上げで制約が 2 乗っぽいのでどうせ dp だろという気持ちになる
# なんで入力が数字で与えられるのかを考えるとちょっと視界が開ける

# よく考えると、できる列の制約は
# 「赤い/青いボールはできる列の i 個目までに A[i]/B[i] 個使える」
# と表せることがわかる
# これに気付けばあとは
#     dp[i][j] := i 個目まで並べたとき赤いボールを j 個使う場合の数
# とした dp が自然と思いつく

from itertools import accumulate

def main():
    mod = 998244353
    B = list(map(int, input()))
    N = len(B)
    A = [2-b for b in B] + [0]*N
    B += [0] * N
    a = b = 0
    for i in range(2*N):
        b += B[i]
        if b > 0:
            b -= 1
            B[i] = 1
        a += A[i]
        if a > 0:
            a -= 1
            A[i] = 1

    A = list(accumulate(A))
    B = list(accumulate(B))

    dp = [[0]*(2*N+2) for _ in range(2*N+1)]
    dp[0][0] = 1
    for i, (a, b) in enumerate(zip(A, B), 1):
        for j in range(2*N+1):
            if i - b <= j <= a:
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod

    print(sum(dp[2*N]) % mod)

main()
### BUGGY CODE ###

def modpow(x, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % p
        x = x * x % p
        n >>= 1
    return res

MOD = pow(10, 9) + 7

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

n = len(s)

fact = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    fact[i] = fact[i - 1] * i % MOD

inv = [1 for _ in range(n + k + 1)]
inv[n + k] = modpow(fact[n + k], MOD - 2, MOD)
for i in range(n + k - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % MOD

p25 = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    p25[i] = p25[i - 1] * 25 % MOD

ans = modpow(26, n + k, MOD)
for i in range(n):
    ans = (ans - fact[n + k] * inv[i] % MOD * inv[n + k - i] % MOD * p25[n + k - i] % MOD + MOD) % MOD

print(ans)

### FIXED CODE ###

def modpow(x, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % p
        x = x * x % p
        n >>= 1
    return res

MOD = pow(10, 9) + 7

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

n = len(s)

fact = [1 for _ in range(n + k + 1)]
p25 = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    fact[i] = fact[i - 1] * i % MOD
    p25[i] = p25[i - 1] * 25 % MOD

inv = [1 for _ in range(n + k + 1)]
inv[n + k] = modpow(fact[n + k], MOD - 2, MOD)
for i in range(n + k - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % MOD

ans = modpow(26, n + k, MOD)
for i in range(n):
    ans -= fact[n + k] * inv[i] % MOD * inv[n + k - i] % MOD * p25[n + k - i] % MOD
    if ans < 0:
        ans += MOD

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

n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[k + 1] + [0] * s for k in range(n + 1)] #dp[i][j] : 左からi個使ってぴったりj
for i in range(1, n + 1):
    for j in range(1, s + 1):
        if j - a[i - 1] < 0:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i - 1]]
ans = 0
for i in range(1, n + 1):
    ans += dp[i][s]
    ans %= 998244353
print(ans)

### FIXED CODE ###

n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[k + 1] + [0] * s for k in range(n + 1)] #dp[i][j] : 左からi個使ってぴったりj
for i in range(1, n + 1):
    for j in range(1, s + 1):
        if j - a[i - 1] < 0:
            dp[i][j] = dp[i - 1][j] % 998244353
        else:
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - a[i - 1]]) % 998244353
ans = 0
for i in range(1, n + 1):
    ans += dp[i][s]
    ans %= 998244353
print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
d=dict()
for i in range(n):
  t=s[i]
  if d.get(t,0)==0:
    d[t]=i
  else:
    ans=max(ans,1)
  for j in range(i+1,n):
    t+=s[j]
    if d.get(t,0)==0:
      d[t]=j
    else:
      if d[t]<i:
        ans=max(ans,j-i+1)
print(ans)


### FIXED CODE ###

import collections
mod=10**9+7
base=257
n=int(input())
S=list(ord(s)-96 for s in input())
B=[0]*(n+1)
B[0]=1
for i in range(n):
  B[i+1]=(B[i]*base)%mod

def chk(x):
  ret=False
  h=0
  bx=B[x]
  d=collections.defaultdict(int)
  for i in range(x):
    h=(h*base+S[i])%mod
  d[h]=x
  for i in range(x,n):
    h=(h*base+S[i]-S[i-x]*bx)%mod
    if d[h]==0:
      d[h]=i+1
    elif d[h]<=i-x+1:
      ret=True
  return ret

l,r=0,n//2
while r-l>1:
  m=(l+r)//2
  if chk(m):
    l=m
  else:
    r=m
print(r if chk(r) else l)
### BUGGY CODE ###

k,n  = map(int,input().split())
diff = lambda x:x[1]-x[0]
a = list(map(int,input().split()))
distance = a+[a[0]+k]
diffs = [diff(distance[i:i+2]) for i in range(len(distance)-1)]
diffs = diffs + [diffs[i] for i in range(0,n-2)]
sums = [sum(diffs[i:i+n-1]) for i in range(len(diffs)-(n-2))]
print(min(sums))

### FIXED CODE ###

k,n  = map(int,input().split())
diff = lambda x:x[1]-x[0]
a = list(map(int,input().split()))
distance = a+[a[0]+k]
diffs = [diff(distance[i:i+2]) for i in range(len(distance)-1)]
print(k - max(diffs))