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

s=input()

a=0
ab=0
abc=0
q=0
m=10**9+7

for i in range(len(s)):
  if s[i]=="A":
    a=(a+3**q)%m
  elif s[i]=="B":
    ab=ab+a
  elif s[i]=="C":
    abc=(abc+ab)%m
  else:
    abc=(abc*3+ab)%m
    ab=ab*3+a
    a=(a*3+3**q)%m
    q+=1
print(abc)


### FIXED CODE ###

s=input()

a=0
ab=0
abc=0
q=1
m=10**9+7

for i in range(len(s)):
  if s[i]=="A":
    a=(a+q)%m
  elif s[i]=="B":
    ab=(ab+a)%m
  elif s[i]=="C":
    abc=(abc+ab)%m
  else:
    abc=(abc*3+ab)%m
    ab=(ab*3+a)%m
    a=(a*3+q)%m
    q=(q*3)%m
print(abc)
### BUGGY CODE ###

h,w=map(int,input().split())
field=[list(input()) for i in range(h)]
queue=[]
for i in range(h):
  for j in range(w):
    if field[i][j]=='#':
      queue.append([i,j])
p=[[0,1],[0,-1],[1,0],[-1,0]]
ans=0
check=[[True for i in range(w)]for j in range(h)]
while len(queue)>0:
  ans+=1
  manu=queue.copy()
  queue.clear()
  save=True
  for now in manu:
    for i in range(4):
      x=now[0]+p[i][0]
      y=now[1]+p[i][1]
      if x>-1 and x<h and y>-1 and y<w and check[x][y] and field[x][y]=='.':
        field[x][y]='#'
        queue.append([x,y])
        save=False
        check[x][y]=False
  if save:
    ans-=1
print(ans)

### FIXED CODE ###

import numpy as np
h,w=map(int,input().split())
field=[list(input()) for i in range(h)]
field=[[0 if field[j][i]=='#' else h+w for i in range(w)]for j in range(h)]
field=np.array(field)
for i in range(1,h):
  field[i,:]=np.minimum(field[i,:],field[i-1,:]+1)
for i in range(h-1,0,-1):
  field[i-1,:]=np.minimum(field[i,:]+1,field[i-1,:])
for i in range(1,w):
  field[:,i]=np.minimum(field[:,i],field[:,i-1]+1)
for i in range(w-1,0,-1):
  field[:,i-1]=np.minimum(field[:,i]+1,field[:,i-1])
print(np.max(field))
### BUGGY CODE ###

n=int(input())
a=[]
m=0
for i in range(n):
    a.append(int(input()))
for i in range(n):
    m=a[i]
    a[i]=1
    print(max(a))
    a[i]=m

### FIXED CODE ###

n=int(input())
a=[]
m1=0
m2=0
for i in range(n):
    a.append(int(input()))
    A=a[i]
    if a[i]>m1:
        m2=m1
        m1=a[i]
        index=i
    elif m1==a[i]:
        m2=a[i]
    elif a[i]>m2:
        m2=a[i]
for i in range(n):
    if i==index:
        print(m2)
    else:
        print(m1)
### BUGGY CODE ###

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

### FIXED CODE ###

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

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
n = int(stdin.readline())
dll = []
while n:
    n -= 1
    cmd = stdin.readline().rstrip()
    if cmd.startswith('insert '):
        dll.insert(0, cmd[7:])
    elif cmd.startswith('delete '):
        key = cmd[7:]
        if dll.count(key):
            dll.remove(key)
    elif cmd.startswith('deleteFirst'):
        del dll[0]
    elif cmd.startswith('deleteLast'):
        del dll[-1]
print(*dll)

### FIXED CODE ###

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

n = int(stdin.readline())
dll = deque()
fcode = ord('F')
lcode = ord('L')
while n:
    n -= 1
    cmd = stdin.readline().rstrip()
    if cmd.startswith('i'):
        dll.appendleft(int(cmd[7:]))
    elif cmd.startswith('d'):
        c = ord(cmd[6])
        if c == fcode:
            dll.popleft()
        elif c == lcode:
            dll.pop()
        else:
            try:
                dll.remove(int(cmd[7:]))
            except ValueError:
                pass
print(*dll)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    A = inputList()
    
    ans = [0]*N
    ans_cnt = 0
    ans_str = ""
    for i in range(N, 0, -1):
        cons = 0
        for j in range(i, N+1, i):
            cons ^= ans[j-1]
        if A[i-1] != cons:
            ans[i-1] = 1
            ans_cnt += 1
            ans_str = ans_str + str(i) + " "
            continue
        if A[i-1] != cons:
            ans[i-1] = 1
            ans_cnt += 1
            ans_str = ans_str + str(i) + " "
            continue
            
    print(ans_cnt)
    print(ans_str)
            	
if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
 
N=INT()
A=LIST()
 
# その位置にボールを入れるかを保持するA2
A2=[0]*N
B=[]
# 後ろから決めていく
for i in range(N-1, -1, -1):
    cur=i+1
    cnt=0
    # curの倍数を全部見に行く
    for j in range(cur*2, N+1, cur):
        cnt^=A2[j-1]
    # ボールを入れるべきかどうか
    if A[i]!=cnt:
        B.append(cur)
        A2[i]=1
 
print(len(B))
print(*B)
### BUGGY CODE ###

N,M = (map(int, input().split()))
li = list((input().split()) for i in range(N))
for x in range(len(li)):
    li[x] = [int(i) for i in li[x]]
 
li.sort()
#print(li)
li2=[]
#for i in range(len(li)):
#    li2.append(li[i][0]*li[i][1])
#print(li2)
li3 = []
for j in range(len(li)):
    for i in range(li[j][1]):
        li3.append(li[j][0])
#print(li3)
print(sum(li3[0:M]))

### FIXED CODE ###

N,M = (map(int, input().split()))
li = [list(map(int,input().split())) for i in range(N)]

li.sort()

li3 = []
for j in range(len(li)):
    li3.extend([li[j][0]]*li[j][1])
    if len(li3)>M:
        break
print(sum(li3[0:M]))
### BUGGY CODE ###

import math, sys, time

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

d = math.floor(M/N)

if M%N == 0:
	print(d)
	sys.exit()

i = 0
while True:
	if M%(N+i+1) == 0:
		print(int(M/(N+i+1)))
		sys.exit()
	i += 1


### FIXED CODE ###

import math, sys, random

N, M = list(map(int,input().split()))
# N, M = 1111, 1000000000

def is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False

    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)

        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1

        if y != n - 1 and t & 1 == 0:
            return False

    return True

d = int(math.floor(M/N))

if M%N == 0:
	print(d)
	sys.exit()

i = 0
f = False
while True:
	if M%(N+i+1) == 0:
		print(int(M/(N+i+1)))
		sys.exit()
	i += 1
	if i == 100000 and is_prime(M):
		print(1)
		sys.exit()
### BUGGY CODE ###

N = int(input())
C, S, F = [0] * (N - 1), [0] * (N - 1), [0] * (N - 1)
for i in range(N - 1):
    C[i], S[i], F[i] = map(int, input().split())


def get_t(x, i):
    t = S[i]
    while x > t:
        t += F[i]
    return t


for i in range(N - 1):
    x = S[i] + C[i]
    for j in range(i + 1, N - 1):
        t = get_t(x, j)
        x = t + C[j]
    print(x)
print(0)


### FIXED CODE ###

N = int(input())
C, S, F = [0] * (N - 1), [0] * (N - 1), [0] * (N - 1)
for i in range(N - 1):
    C[i], S[i], F[i] = map(int, input().split())

for i in range(N):
    t = 0
    for j in range(i, N - 1):
        if t < S[j]:
            t = S[j]
        elif t % F[j] == 0:
            pass
        else:
            t += F[j] - t % F[j]
        t += C[j]
    print(t)
### BUGGY CODE ###

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

    ans = 0
    isleft = True

    def f(n):
        kaisu = N_original - n+1
        for i in range(kaisu):
            if S[i:i+n] in S[i+n:]:
                return True
        return False

    left = 0
    right = N
    N = N//4
    while True:
        if f(N):
            if left == N:
                ans = left
                break
            left = N
        else:
            if right == N:
                ans = right
                break
            right = N
        N = (left + right)//2
    print(ans)

main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    l1 = length = 0
    l2 = 1

    while (l2 + length < N):
        if S[l1:l2] in S[l2:]:
            length = l2 - l1
            l2 += 1
        else:
            l1 += 1
            l2 = l1 + length + 1
    print(length)

main()
### BUGGY CODE ###

n,k = map(int, input().split())
a = list(map(int,input().split()))
ans = 1
c = [1]
for j in range(1,2*n):
    i = a[c[-1]-1]
    if i in set(c):
        g = i
        break
    c.append(i)
s = c.index(g)
r = len(c)-s
if k <=s:
    print(c[k])
else:
    b = (k-s)%r
    print(c[s+b])

### FIXED CODE ###

n,k = map(int, input().split())
a = list(map(int,input().split()))
ans = 1
c = [1]
d = [0]*(n+5)
d[1] = 1
for j in range(1,2*n):
    i = a[c[-1]-1]
    if d[i] == 1:
        g = i
        break
    # if i in set(c):
    #     g = i
    #     break
    d[i] = 1
    c.append(i)
s = c.index(g)
r = len(c)-s
if k <=s:
    print(c[k])
else:
    b = (k-s)%r
    print(c[s+b])
### BUGGY CODE ###

n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7

ans=0
cnt=[0 for i in range(61)]

for i in range(n):
    now=A[i]
    bek=1
    for q in range(61):
        if now&1==0:
            ans+=cnt[q]*bek
        else:
            ans+=(i-cnt[q])*bek
        bek<<=1
        cnt[q]+=now&1
        now>>=1
    ans=ans%mod
    #print(ans)
print(ans)

### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7

ans=0
cnt=[0 for i in range(61)]

for i in range(n):
    now=A[i]
    bek=1
    for q in range(61):
        if now&1==0:
            ans+=cnt[q]*bek
        else:
            ans+=(i-cnt[q])*bek
        bek=bek*2%mod
        cnt[q]+=now&1
        now>>=1
    ans=ans%mod
    #print(ans)
print(ans)
### BUGGY CODE ###

N = int(input())
number = list(map(int,input().split()))
count = 0
if not 1 in number:
    print(-1)
else:
    for i in range(N):
        now = i+1
        if now in number:
            #number.index(now)が左から数えたときのnowのindex番号
            count += number.index(now)
            number[:number.index(now)+1]=[]

        else:
            count += len(number)
            break
    print(count)

### FIXED CODE ###

N = int(input())
number = list(map(int,input().split()))
count = 0
if not 1 in number:
    print(-1)
else:
    nownumber = 1
    nowindex = 0
    for i in range(N):
        if number[i]  == nownumber:
            count += 1
            nownumber += 1
        else:
            pass
    print(N-count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
a_list = []
for i in range(N):
    a_list.append(int(input()))
color_counter = 0
for i in range(N):
    color_counter += 1
    compare_a = a_list.pop(0)
    next_a_list = []
    for idx, ite in enumerate(a_list[:]):
        if compare_a < ite:
            compare_a = ite
        else:
            next_a_list.append(ite)
    if len(next_a_list) == 0:
        break
    else:
        a_list = next_a_list
print(color_counter)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from bisect import bisect_right, bisect_left
N = int(input())
a_list = [int(input()) for _ in range(N)]

color_list = [1]
for a in a_list:
    a *= -1
    index = bisect_right(color_list, a)
    if index < len(color_list):
        color_list[index] = a
    else:
        color_list.append(a)
#     print(color_list, a)
print(len(color_list))
### BUGGY CODE ###

n, m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
bc = []

for i in range(m):
  tmp = [int(i) for i in input().split()]
  bc.append(tmp)

for i in range(m):
  tmp = [bc[i][1]] * bc[i][0]
  a += tmp

a.sort()
print(sum(a[::-1][:n]))


### FIXED CODE ###

n, m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
bc = []
for i in range(m):
  tmp = [int(i) for i in input().split()]
  bc.append(tmp[::-1])

for i in range(n):
  tmp = [a[i]]
  tmp.append(1)
  bc.append(tmp)
  
bc.sort()
bc = bc[::-1]
#print(bc)

ans = 0
i = 0
count = 0
while count < n:
  if bc[i][1] == 0:
    i += 1
  ans += bc[i][0]
  bc[i][1] -= 1
  count += 1
  
print(ans)
### BUGGY CODE ###

n, k = (int(i) for i in input().split())
p = [int(i) for i in input().split()]

for i in range(n):
    p[i] = (p[i]+1) / 2
_max = -1
for i in range(n-k+1):
    _sum = 0
    for j in range(k):
        _sum += p[i+j]
    _max = max(_sum, _max)

print(_max)
        
           
    

### FIXED CODE ###

n, k = (int(i) for i in input().split())
p = [int(i) for i in input().split()]

_sum = 0
for i in range(k):
    p[i] = (p[i]+1) / 2
    _sum += p[i]
_max = _sum
for i in range(k, n):
    p[i] = (p[i]+1) / 2
    _sum += p[i]
    _sum -= p[i-k]
    _max = max(_sum, _max)
    
print(_max)
### BUGGY CODE ###

from collections import deque


def solvemaze(y, x, num):
    maps.append([])
    dx, dy = (-1, 0, 1, 0), (0, -1, 0, 1)
    maze[y][x] = num
    que = deque()
    que.append((y, x))
    while que:
        y_, x_ = que.popleft()
        maps[num].append((y_, x_))
        for i in range(4):
            y2 = y_ + dy[i]
            x2 = x_ + dx[i]
            if 0 <= y2 < h and 0 <= x2 < w and maze[y2][x2] == '.':
                maze[y2][x2] = num
                que.append((y2, x2))

def makeroute(s_maps, num):
    for y, x in s_maps:
        for i in range(-2, 3):
            for j in range(-2, 3):
                y2 = y + i
                x2 = x + j
                if 0 <= y2 < h and 0 <= x2 < w:
                    num2 = maze[y2][x2]
                    if not  num2 in [0, '#'] + E[num]:
                        E[num].append(num2)
                        E[num2].append(num)
    

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [[x for x in input()] for _ in range(h)]
maps = []

num = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            solvemaze(i, j, num)
            num += 1

E = [[] for _ in range(num)]
for i in range(num):
    makeroute(maps[i], i)

s = maze[Ch-1][Cw-1]
g = maze[Dh-1][Dw-1]
used = [False] * num
used[s] = True
que = deque()
que.append((0, s))
cost = [float('inf')] * num
cost[s] = 0
while que:
    c, v = que.popleft()
    for e in E[v]:
        if not used[e]:
            que.append((c+1, e))
            cost[e] = c+1
            used[e] = True

if not used[g]:
    print(-1)
else:
    print(cost[g])


### FIXED CODE ###

from collections import deque


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())
dy, dx = (-1, 0, 1, 0), (0, -1, 0, 1)
maze = [[float('inf') if x == '.' else -float('inf') for x in input()] for _ in range(h)]
maze[Ch][Cw] = 0
que = deque()
que.append((0, Ch, Cw))
while que:
    c, y, x = que.popleft()
    
    if c > maze[y][x]:
        continue
    
    if y == Dh and x == Dw:
        break
    
    for i in range(4):
        y2, x2 = y + dy[i], x + dx[i]
        if 0 <= y2 < h and 0 <= x2 < w and c < maze[y2][x2]:
            maze[y2][x2] = c
            que.appendleft((c, y2, x2))
            
    for i in range(-2, 3):
        for j in range(-2, 3):
            y3, x3, c2 = y + i, x + j, c+1
            if 0 <= y3 < h and 0 <= x3 < w and c2 < maze[y3][x3]:
                maze[y3][x3] = c2
                que.append((c2, y3, x3))

ans = maze[Dh][Dw]
if ans == float('inf'):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n = int(input())
mod = 10**9+7
ans = 1
i = 1
while i <= n:
    ans *= i
    i += 1
print(ans%mod)

### FIXED CODE ###

n = int(input())
mod = 10**9+7
ans = 1
for i in range(1, n+1):
    ans = (ans*i)%mod
print(ans)
### BUGGY CODE ###

#Big Array
N, K = map(int, input().split())
a = [0]*N
b = [0]*N
R = []
for i in range(N):
    a[i], b[i] = map(int, input().split())
for i in range(N):
    for j in range(b[i]):
        R.append(a[i])
R.sort()
print(R[K-1])

### FIXED CODE ###

#Big Array
N, K = map(int, input().split())
a = [0]*(N)
b = [0]*(N)
R = [0]*(10**5+1)
ans = 0
for i in range(N):
    a[i], b[i] = map(int, input().split())
for i in range(N):
    R[a[i]] = R[a[i]] + b[i]
j = 0
while K > 0:
    K = K - R[j]
    ans = ans + 1
    j = j + 1
print(ans-1)
### BUGGY CODE ###

n = int(input())
strings = []
answer = 0
for i in range(n):
  string = input()
  string = ''.join(sorted(string))
  answer += strings.count(string)
  strings.append(string)
print(answer)

### FIXED CODE ###

n = int(input())
strings = {}
answer = 0
for i in range(n):
  string = input()
  string = ''.join(sorted(string))
  if string not in strings:
    strings[string]=1
  else:
    answer += strings[string]
    strings[string] += 1
print(answer)
### BUGGY CODE ###

from collections import deque
h, w = map(int,input().split())
grid = [list(input()) for _ in range(h)]
dist = [[-1]*w for _ in range(h)]
black_cells = []
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            black_cells.append((i,j))
dxy = [[1,0],[-1,0],[0,1],[0,-1]]
stack = deque(black_cells)
darked = len(stack)
targetd = h*w
cnt = 0

while darked < targetd:
    next = deque([])
    while stack:
        y, x = stack.popleft()
        for dx, dy in dxy:
            X = x + dx
            Y = y + dy
            if X < 0 or X >= w or Y < 0 or Y >= h:
                continue
            if grid[Y][X] == '.':
                next.append((Y, X))
                grid[Y][X] = '#'
    stack = next
    cnt += 1
    darked += len(next)
print(cnt)


### FIXED CODE ###

from collections import deque
 
def solve(h, w, a):
    used = [[True] * (w+2) for _ in range(h+2)]
    que = deque()
    for r in range(h):
        used[r+1][1:-1] = map(lambda _:_=="#", a[r])
        for c in range(w):
            if a[r][c] == "#":
                que.append((r+1, c+1, 0))
    neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
    while que:
        r, c, k = que.popleft()
        for dr, dc in neighbors:
            nr, nc = r+dr, c+dc
            if not used[nr][nc]:
                que.append((nr, nc, k+1))
                used[nr][nc] = True
    return k
 
h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(solve(h, w, a))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
q = deque()
grid = [[10**6] * W for _ in range(H)]
dire = ((1,0),(0,1),(-1,0),(0,-1))
d = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            q.append((i,j))
            grid[i][j] = 0
 
while q:
    i, j = q.popleft()
    d = grid[i][j]
    for dy, dx in dire:
        ny,nx = i+dy, j+dx
        if ny>=0 and ny<H and nx>=0 and nx<W and grid[ny][nx] > grid[i][j]:
            q.append((ny, nx))
            grid[ny][nx] = grid[i][j] + 1
 
print(d)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
A = [input() for _ in range(H)]
q = deque([])
grid = [[-1] * W for _ in range(H)]
dire = ((1,0),(0,1),(-1,0),(0,-1))
d = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            q.append((i,j))
            grid[i][j] = 0
 
while q:
    i, j = q.popleft()
    d = grid[i][j]
    for dy, dx in dire:
        ny,nx = i+dy, j+dx
        if ny>=0 and ny<H and nx>=0 and nx<W and grid[ny][nx] < 0:
            q.append((ny, nx))
            grid[ny][nx] = grid[i][j] + 1
 
print(d)
### BUGGY CODE ###

N, M = map(int, input().split())
List = [int(input()) for _ in range(M)]

P = 1000000007

if N==1:
    print(1)
    
else:
    dp = [0]*(N+1)

    if 1 in List:
        dp[1] = 0
        if 2 in List:
            dp[2] = 0
        else:
            dp[2] = 1
    else:
        dp[1] = 1
        if 2 in List:
            dp[2] = 0
        else:
            dp[2] = 2

    for i in range(2, N):
        if i+1 in List:
            dp[i+1]=0
        else:
            if i in List:
                dp[i+1] = dp[i-1]
            else:
                dp[i+1] = (dp[i]+dp[i-1])
        
    print(dp[N]%P)

### FIXED CODE ###

N, M = map(int, input().split())
List = [int(input()) for _ in range(M)]

P = 10**9+7

dp = [1]*(N+1)

for a in List:
    dp[a]=0

for i in range(1, N+1):
    if (i>=2)&(dp[i]!=0):
        dp[i] = (dp[i-1]+dp[i-2])%P
        
print(dp[N])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
s = input()[:-1]
# print(s)

lb = 0
ub = n//2 + 1

def check(len):
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            # print(len, s[l1:l1 + len], s[l2:l2 + len])

            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False

while ub > lb+1:
    x = (lb + ub)//2
    if check(x):
        lb = x
    else:
        ub = x
    # print(lb, ub)


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# E
# 文字列比較をローリングハッシュを用いると高速

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
s = input()[:-1]
# s = list(map(ord, list(input()[:-1])))
# print(s)

lb = 0
ub = n//2 + 1


def check(len):
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False


mod = 10**9+7
base = 1234
power = [1]*(n+1)
for i in range(1, n+1):
    power[i] = power[i-1]*base%mod


def check2(m):
    res = 0
    for i in range(m):
        res+=s[i]*power[m-i-1]
        res%=mod

    dic = {res: 0}
    # defaultdictが早い
    # dic = defaultdict(int)
    # dic[res] = 0

    for i in range(n-m):
        res = ((res-s[i]*power[m-1])*base
                             +s[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False


def check3(m):
    dic = {}
    for i in range(n-m+1):
        s_ = s[i:i+m]
        if s_ in dic.keys():
            if dic[s_]+m<=i:
                return True
        else:
            dic[s_] = i
    return False


while ub > lb+1:
    x = (lb + ub)//2
    if check3(x):
        lb = x
    else:
        ub = x
    # print(lb, ub)


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
mod = 10**9+7
ans = [0]*(K+1)
s = 0
for i in range(K, 0, -1):
    ans[i] = pow(K//i, N)%mod
    for j in range(2*i, K+1, i):
        ans[i] -= ans[j]
    s += ans[i]*i%mod
print(s%mod)


### FIXED CODE ###

N, K = map(int, input().split())
li = [0]*(K+1)

out = 0
mod = 10**9+7

for i in range(K, 0, -1):
  li[i] = pow(K//i, N, mod) 
  for j in range(i*2, K+1, i):
    li[i] -= li[j]
  out += li[i] * i
print(out%mod)