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

from sys import stdin
# import math
# import numpy as np
# N = int(stdin.readline().rstrip().split()[0])
# A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]
# S = stdin.readline().rstrip().split()[0]
N, K = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip().split()[0]

B = []
count = 0
oz = 1
for s in S:
  if int(s) == oz:
    count+=1
  else:
    B.append(count)
    count=1
    oz=int(s)
B.append(count)
if oz==0:
  B.append(0)
# print(B)
L = len(B)
if 2*K+1>L:
  K = int(L/2)
# print("K",K)
C = []
for i in range(L):
  start = 2*i
  last = 2*i+2*K+1
  if last>L:
    # print("break",last)
    break
  C.append(sum(B[start:last]))
# print(C)
ans = max(C)
print(ans)


### FIXED CODE ###

from sys import stdin
# import math
import numpy as np
# N = int(stdin.readline().rstrip().split()[0])
# A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]
# S = stdin.readline().rstrip().split()[0]
N, K = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip().split()[0]

B = [0]
count = 0
oz = 1
for s in S:
  if int(s) == oz:
    count+=1
  else:
    B.append(count)
    count=1
    oz=int(s)
B.append(count)
if oz==0:
  B.append(0)
# print(B)
L = len(B)-1
if 2*K+1>L:
  K = int(L/2)
# print("K",K)
B = np.cumsum(B)
# print(B)
C = []
for i in range(L):
  start = 2*i
  last = 2*i+2*K+1
  if last>L:
    # print("break",last)
    break
  C.append(B[last]-B[start])
# print(C)
ans = max(C)
print(ans)
### BUGGY CODE ###

import itertools
S = str(input())

ans = [i+j for i,j in itertools.combinations(range(int(len(S))), 2) if int(S[i:j+1]) % 2019 == 0]
      
print(len(ans))

### FIXED CODE ###

S = str(input())
li = [0] * 2019
ans = 0
li[0] = 1

d = 1
s = 0
for i in S[::-1]:
  s += int(i) * d
  s = s % 2019
  li[s] += 1
  d *= 10
  d = d % 2019
  
for l in li:
  ans += l * (l-1) // 2

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

import math
n = int(input())
list1 = []
if n == 0:
  	print("Yes")
else:
    for i in range(int(math.log10(n))+1):
        num = n%10
        n = n//10
        list1.append(num)
    if sum(list1)%9 == 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n = int(input())
a = sum(list(map(int, str(n))))
if a%9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

a=int(input())
b=list(map(int,input().split()))
ans=[0]*a
for i in range(a):
  for j in range(a):
    if b[i]%b[j]==0 and not i==j:
      ans[i]=0
      break
    elif j==a-1:
      ans[i]=1
print(sum(ans))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
max_a = max(a)
cnt_d = [0] * (max_a + 1)

for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1

print(sum(cnt_d[ai] == 1 for ai in a))
### BUGGY CODE ###

n = input()
S = list(map(int, input().split()))
q = input()
T = list(map(int, input().split()))
C = 0

for i in T:
    if i in S:
        C += 1

print(C)

### FIXED CODE ###

n = input()
S = set(map(int, input().split()))
q = input()
T = set(map(int, input().split()))
C = 0

for i in T:
    if i in S:
        C += 1

print(C)
### BUGGY CODE ###

N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB.sort(key=lambda x:x[0])

dp = [[0]*T for i in range(N+1)]
ans = 0
for n in range(N):
    for w in range(T):
        ans = max(ans,dp[n][w]+AB[n][1])
        if w-AB[n][0]>=0:
            dp[n+1][w] = max(dp[n][w],dp[n][w-AB[n][0]]+AB[n][1])
        else:
            dp[n+1][w] = dp[n][w]

print(ans)

### FIXED CODE ###

N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB.sort(key=lambda x:x[1])

dp1 = [[0]*T for i in range(N+1)]
for n in range(N):
    for w in range(T):
        if w-AB[n][0]>=0:
            dp1[n+1][w] = max(dp1[n][w],dp1[n][w-AB[n][0]]+AB[n][1])
        else:
            dp1[n+1][w] = dp1[n][w]

for n in range(N):
    for w in range(T-1):
        dp1[n][w+1] = max(dp1[n][w+1],dp1[n][w])

dp2 = [[0]*T for i in range(N+1)]
for n in range(N):
    for w in range(T):
        if w-AB[-n-1][0]>=0:
            dp2[n+1][w] = max(dp2[n][w],dp2[n][w-AB[-n-1][0]]+AB[-n-1][1])
        else:
            dp2[n+1][w] = dp2[n][w]

for n in range(N):
    for w in range(T-1):
        dp2[n][w+1] = max(dp2[n][w+1],dp2[n][w])

ans = 0
for n in range(N):
    for w in range(T):
        ans = max(AB[n][1]+dp1[n][w]+dp2[N-n-1][T-1-w],ans)

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

import sys
n,m,k =map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

t = k
i = 0
asum = [0]* (n+1)
bsum = [0]* (m+1)
suma = 0
sumb = 0

for  i in range(n):
    suma += a[i]
    asum[i+1]= suma


for  i in range(m):
    sumb += b[i]
    bsum[i+1] = sumb

count = 1
ans = 0

for i in range(n+1):
    if ans < i :
        if asum[i] <= k:
            ans=i
    else:
        for j in range(ans-i,m+1,1):
            if asum[i] + bsum[j]<=k and i+j>ans:
                ans=i+j

print(min(ans,m+n))


### FIXED CODE ###

import sys
n,m,k =map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

t = k
i = 0
asum = [0]* (n+1)
bsum = [0]* (m+1)
suma = 0
sumb = 0

for  i in range(n):
    suma += a[i]
    asum[i+1]= suma


for  i in range(m):
    sumb += b[i]
    bsum[i+1] = sumb

count = 1
ans = 0

for i in range(n+1):
    if ans < i :
        if asum[i] <= k:
            ans=i
    else:
        for j in range(ans-i,m+1,1):
            if asum[i] + bsum[j]<=k:
                if i+j>ans:
                    ans=i+j
            else:
                break

print(min(ans,m+n))
### BUGGY CODE ###

s = input()
t = input()

c=0
j=0
k=0

#t
for i in range(0,len(t)):
  while True:
    if t[i:i+1]==s[j:j+1]:
      j=j+1
      c=c+1
      k=c
      break
    else:
      if j==len(s):
        j=0
      else:
        if c-k==len(s):
          print("-1")
          exit()
        else:
          j=j+1
          c=c+1
print(c)

### FIXED CODE ###

s = input()
t = input()

x = len(s)
y = len(t)

a = 0
b = x
c = 0
a0 = 0


for i in range(0,y):
  while True:
    #先頭からの位置
    a=s.find(t[i:i+1],a0)+1
    if a <= 0:
      a=s.find(t[i:i+1])+1
    if a <= 0:
      print("-1")
      exit()
    
    if a<=a0:
      c=c+a+b
    else:
      c=c+a-a0
    b=x-a
    a0=a
    break
    
print(c)
### BUGGY CODE ###

n = int(input())
x = [0]*n
for i in range(n):
    x[i] = list(map(int,input().split()))
x.sort(key= lambda val : val[0])
i = 0
while 1:
    if i >= len(x)-1:
        break
    
    if x[i][0] + x[i][1] > x[i+1][0] - x[i+1][1]:
        if x[i][0] + x[i][1] > x[i+1][0] + x[i+1][1]:
            del x[i]
        else:
            del x[i+1]
    else:
        i += 1
print(len(x))

### FIXED CODE ###

n = int(input())
x = [0]*n
for i in range(n):
    x[i] = list(map(int,input().split()))
x.sort(key= lambda val : val[0])
i = 0
while 1:
    if i >= len(x)-1:
        break
    
    if x[i][0] + x[i][1] > x[i+1][0] - x[i+1][1]:
        if x[i][0] + x[i][1] > x[i+1][0] + x[i+1][1]:
            del x[i]
        else:
            del x[i+1]
    else:
        i += 1
print(len(x))
### BUGGY CODE ###

N = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        s = l[i]+l[j]
        for k in range(j+1,N):
            if l[k] >= s:
                break
            ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
max = l[N-1]
tc = N
st = [j+1 for j in range(N-1)]
for i in range(N-2):
    if l[i]+l[i+1] > max:
        k = N-i-1
        ans += ((k-1)*k*(k+1))//6
        break
    for j in range(i+1,N-1):
        if j == tc:
            ans += tp
            break
        s = l[i]+l[j]
        if s <= l[j+1]:
            continue
        if s > max:
            tc = j 
            tp = (N-j-1) * (N-j) //2 #これをiの中でできないか
            ans += tp
            break
        start = st[j]
        if s <= l[start]:
            ans += start-j-1
            continue
        end = N
        while start != end:
            center = (start + end)//2
            if s <= l[center]:
                end = center
            else:
                start = center + 1
        st[j] = end
        ans += end-j-1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy

# from typing import Dict, List, Optional, Set, Tuple


# def solve(values: List[int], nb_vertices: int, nb_edges: int) -> int:
def solve(values, _nb_vertices, nb_edges) -> int:
    succ = defaultdict(set)
    for s, d in values:
        succ[s].add(d)
    # all edges have a 0 length path starting at the edge
    dp = {s: True for s in succ}
    empty_dp = {s: False for s in succ}
    max_length_path = 0
    for length in range(1, nb_edges + 1):
        prev = dp.copy()
        dp = empty_dp.copy()
        # vertices are indexed from 1
        for vertex in succ:
            for d in succ[vertex]:
                if prev.get(d - 1, False):
                    dp[vertex - 1] = True
                    max_length_path = length
                    break
    return max_length_path


def do_job():
    "Do the work"
    # first line is number of test cases
    N, M = map(int, input().split())
    values = []
    for _ in range(M):
        values.append(tuple(map(int, input().split())))
    result = solve(values, N, M)
    print(result)


def main():
    "Program wrapper."
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


### FIXED CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys
from collections import defaultdict

sys.setrecursionlimit(pow(2, 31) - 1)

# from typing import Dict, List, Optional, Set, Tuple

# def dfs(vertex: int, succ: Dict[int, List[int]], dp: Dict[int, int]) -> int:
def dfs(vertex, succ, dp):
    if vertex in dp:
        return dp[vertex]
    length = 0
    for s in succ[vertex]:
        length = max(length, 1 + dfs(s, succ, dp))
    dp[vertex] = length
    return length


# def solve(values: List[int], nb_vertices: int, nb_edges: int) -> int:
def solve(values, _nb_vertices, _nb_edges) -> int:
    succ = defaultdict(list)
    for s, d in values:
        succ[s].append(d)
    # all edges have a 0 length path starting at the edge
    dp = defaultdict(lambda: -1)
    for vertex in frozenset(succ.keys()):
        if vertex in dp:
            dp[vertex] = max(dp[vertex], dfs(vertex, succ, dp))
        else:
            dp[vertex] = dfs(vertex, succ, dp)
    return max(dp.values())


def do_job():
    "Do the work"
    # first line is number of test cases
    N, M = map(int, input().split())
    values = []
    for _ in range(M):
        values.append(tuple(map(int, input().split())))
    result = solve(values, N, M)
    print(result)


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


def gcd(a, b):
    if a < b:
        a, b = b, a
    r = a % b
    if r == 0:
        return b
    return gcd(r, b)

K = int(input())

ans = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            ans += gcd(gcd(a, b), c)

print(ans)

### FIXED CODE ###

# K, N = map(int, input().split())
# a = list(map(int, input().split()))

# N = int(input())

def gcd(a, b):
    if a < b:
        a, b = b, a
    r = a % b
    if r == 0:
        return b
    return gcd(r, b)

K = int(input())

ans = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        n = gcd(a, b)
        for c in range(1, K+1):
            ans += gcd(n, c)

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

# D - Wizard in Maze

import heapq

h,  w  = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = []
for i in range(h):
    s.append([c for c in input()])

queue = [(0, ch - 1, cw - 1)]  # (dist, y, x)

while len(queue) > 0:
    dist, y, x = heapq.heappop(queue)
    if s[y][x] != '.':
        continue
    s[y][x] = dist
    for vy in range(-2, 3):
        for vx in range(-2, 3):
            if 0 <= y + vy < h and 0 <= x + vx < w:
                cost = 0 if abs(vx) + abs(vy) <= 1 else 1
                heapq.heappush(queue, (dist + cost, y + vy, x + vx))

dist = s[dh - 1][dw - 1]
print(dist if dist != '.' else -1)


### FIXED CODE ###

# D - Wizard in Maze

from collections import deque

h,  w  = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = []
for i in range(h):
    s.append([c for c in input()])

def dfs(y, x, area_id):
    stack = [(y, x)]
    while len(stack) > 0:
        y, x = stack.pop()
        if s[y][x] == '.':
            s[y][x] = area_id
            for vy, vx in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                if (0 <= x + vx < w and 0 <= y + vy < h and
                    s[y + vy][x + vx] == '.'):
                    stack.append((y + vy, x + vx))

n_area = 0
for y in range(h):
    for x in range(w):
        if s[y][x] == '.':
            dfs(y, x, n_area)
            n_area += 1

# links between areas
adj = [set() for i in range(n_area)]
for y in range(h):
    for x in range(w):
        if s[y][x] == '#':
            continue
        for vy in range(0, 3):
            for vx in range(-2, 3):
                if (0 <= x + vx < w and 0 <= y + vy < h and
                    s[y + vy][x + vx] != '#'):
                    adj[s[y][x]].add(s[y + vy][x + vx])
                    adj[s[y + vy][x + vx]].add(s[y][x])

c = s[ch - 1][cw - 1]
d = s[dh - 1][dw - 1]
dist = [float('inf') for i in range(n_area)]
dist[c] = 0

q = deque()
q.append((c, 0))
while len(q) > 0:
    c, cost = q.popleft()
    for x in adj[c]:
        if dist[x] > cost + 1:
            dist[x] = cost + 1
            q.append((x, cost + 1))

print(dist[d] if dist[d] < float('inf') else -1)
### BUGGY CODE ###

S = input()
mod = 2019
DP = [0] * mod
DP[0] = 1
t = 1
value = 0
for i in reversed(S):
    value += int(i) * t
    DP[value % mod] += 1
    t *= 10
print(int(sum([i * (i-1) / 2 for i in DP])))

### FIXED CODE ###

S = input()
N = len(S)
mod = 2019
num = [0 for i in range(2019)]
num[0] = 1
t = 1
rem = 0

for i in reversed(S):
    rem += int(i) * t
    rem %= mod
    t *= 10
    t %= mod
    num[rem] += 1

print(int(sum([i * (i-1) / 2 for i in num])))
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

inf = 10 ** 4 + 1
dp = [inf] * N
dp[0] = 0

for i in range(1,N):
    H = h[i]
    dp[i] = min( dp[j] + abs(h[j] - H) for j in range(max(0, i-K),i))


print(dp[N-1])

### FIXED CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
inf = 10 ** 4 + 1
dp = [inf] * n
dp[0] = 0
for i in range(1,n):
    H = h[i]
    dp[i] = min([dp[j] + abs(h[j] - H) for j in range(max(0, i - k), i)])
print(dp[-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def ans(n, w):
    dp = [0] * (w+1)
    for _ in range(n):
        wi, vi = map(int, input().split())
        for i in range(wi, w+1):
            if dp[i-wi] < dp[i] + vi:
                dp[i-wi] = dp[i] + vi
    return dp[0]


N, W = map(int, input().split())
print(ans(N, W))


### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=np.int64)

for _ in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])

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

n = int(input())
s = list(map(int, input().split()))
ans = "YES"
for i in range(0, n-1):
    for j in range(i+1, n):
        if s[i] == s[j]:
            ans = "NO"
            break
print(ans)


### FIXED CODE ###

n = int(input())
s = list(map(int, input().split()))
ans = "YES"
if len(s) != len(set(s)):
    ans = "NO"
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n = int(input())
data = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    data[a].append([i,b])  # i本目でbに
    data[b].append([i,a])

k = max(len(data[i]) for i in range(n))
print(k)
ans = [-1 for i in range(n)]

def solve(now,pre,pre_path):
    color = [True for i in range(k+1)]
    color[ans[pre_path]] = False

    for nex_path,nex in data[now]:
        if nex == pre:continue
        for num,c in enumerate(color):
            if c:
                ans[nex_path] = num
                color[num] = False
                solve(nex,now,nex_path)
                break
    return

solve(0,n,k)
for x  in ans[:-1]:
    print(x+1)

### FIXED CODE ###

n = int(input())
G = [[] for _ in range(n)]
d = {}
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    d[(a,b)] = d[(b,a)] = i

k = 0
ans = [None]*(n-1)

stack = [(0,-1)] #node, par

while stack:
    now,pre = stack.pop()
    color = 1
    for nex in G[now]:
        if nex == pre:continue
        stack.append((nex,now))
        if pre != -1:
            if color == ans[d[(now,pre)]]:
                color += 1
        ans[d[(now,nex)]] = color
        k = max(k,color)
        color += 1

print(k)
print(*ans, sep="\n")
### BUGGY CODE ###

MOD = 10 ** 9 + 7
S = input()
N = len(S)

# dp[i][j] := i桁目までで13で割ったあまりがjになるものの個数

dp = [[0] * 13 for _ in range(N + 1)]
if S[-1] == '?':
    for j in range(10):
        dp[1][j] = 1
else:
    dp[1][int(S[-1])] = 1

for i in range(2, N + 1):
    if S[-i] == '?':
        for k in range(10):
            d = k * (10 ** (i - 1)) % 13
            for j in range(13):
                dp[i][j] += dp[i - 1][(13 + j - d) % 13]
                dp[i][j] %= MOD
    else:
        d = int(S[-i]) * (10 ** (i - 1)) % 13
        for j in range(13):
            dp[i][j] += dp[i - 1][(13 + j - d) % 13]
            dp[i][j] %= MOD

print(dp[N][5])


### FIXED CODE ###

MOD = 10 ** 9 + 7
S = input()
N = len(S)

# dp[i][j] := i桁目までで13で割ったあまりがjになるものの個数

dp = [[0] * 13 for _ in range(N + 1)]
if S[-1] == '?':
    for j in range(10):
        dp[1][j] = 1
else:
    dp[1][int(S[-1])] = 1

m = 1
for i in range(2, N + 1):
    m = m * 10 % 13
    for j in range(13):
        num = '?' if S[-i] == '?' else int(S[-i])
        for k in range(10):
            if num == '?' or k == num:
                d = k * m % 13
                dp[i][j] = (dp[i][j] + dp[i - 1][(13 + j - d) % 13]) % MOD

print(dp[N][5])
### BUGGY CODE ###

e = list(map(int,input().split()))
a = e[0]
b = e[1]
c = e[2]
d = e[3]
cnt = 0
t = [j for j in range(a,b+1) if j%c != 0 and j%d != 0]
cnt = len(t)
print(cnt)

### FIXED CODE ###

e = list(map(int,input().split()))
a,b,c,d = e

def gcd(x,y):
    while y !=0:
        x,y = y,x%y
    return x

def sums(x):
    S1 = x//c
    S2 = x//d
    S3 = x// (c*d//gcd(c,d))
    return x - S1 - S2 + S3


print(sums(b)-sums(a-1))
### BUGGY CODE ###

n = int(input())
result=1
a = list(map(int,input().split()))
for i in a:
    result*=i

if result > 1000000000000000000:
    print("-1")
else:
    print(result)

### FIXED CODE ###

n = int(input())
result=1
a = list(map(int,input().split()))
    
if 0 in a:
    print(0) 
else:
    for i in a:
        result*=i
        if result > 10**18:
            print(-1)
            break
    if result <= 10**18:
        print(result)
### BUGGY CODE ###

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

l = 0
r = k

result = 0.0
m = 0
while r != len(p)+1:
  pp = p[l:r]
  l += 1
  r += 1
  s = sum(pp)
  if s <= m:
    continue
  m = s
  this_res = 0.0
  # 期待値の計算
  for pi in pp:
    this_res += pi / 2 + 1/2
  result = max(result, this_res)

print(result)

### FIXED CODE ###

from itertools import accumulate
n, k = map(int, input().split())
p = list(map(int, input().split()))

pp = [0] + list(accumulate(p))

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

#11
n = int(input())
a = list(map(int, input().split()))
 
flag = [a.count(a[i])-1 for i in range(n+1) ]
p = flag.index(1) + list(reversed(flag)).index(1)
 
mod = 10**9+7
    
def memoize(f): #メモ化関数
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memoize
def easyFact(n):
    if ( n==0 ): 
        return 1
    else: 
        return n*easyFact(n-1)

g = [easyFact(i) for i in range(n+2)]

def combination(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return ( g[n] /( g[r] * g[n-r] ) )
 
 
for i in range(n+1):
    if ( p>=i ):
        c =( combination(n+1, i+1) - combination(p, i) ) % mod
    else:
        c =( combination(n+1, i+1) ) % mod
    print( int(c) )

### FIXED CODE ###


MOD = 10**9+7
n = int(input())
la = list(map(int,input().split()))
L = [-1]*(n+1)
l = 0
for i in range(n+1):
  a = la[i]
  if L[a] == -1:
    L[a] = i
  else:
    l = i - L[a] - 1
    break
 
MAX = n
factorial = [1, 1]
inverse = [0, 1]
inverse_factorial = [1, 1]
for i in range(2,MAX+1):
  factorial.append( (factorial[-1]*i)%MOD )
  inverse.append( (-inverse[MOD%i]*(MOD//i))%MOD )
  inverse_factorial.append( (inverse_factorial[-1]*inverse[-1])%MOD )
 
def C_MOD(n, k):
  if k < 0 or k > n:
    return 0
  k = min(k,n-k)
  return factorial[n] * inverse_factorial[k] * inverse_factorial[n-k] % MOD
 
print(n)
#print((2*C_MOD(n-1,1)-C_MOD(n-1-l,1)+C_MOD(n-1,2)+1)%MOD)
for i in range(2,n+1):
  if n > l+1:
    print((2*C_MOD(n-1,i-1)-C_MOD(n-1-l,i-1)+C_MOD(n-1,i)+C_MOD(n-1,i-2))%MOD)
  else:
    print((2*C_MOD(n-1,i-1)+C_MOD(n-1,i)+C_MOD(n-1,i-2))%MOD)
print(1)
### BUGGY CODE ###

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

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

L = []
L.append(1)
f = 1
memo = []
flg = 0

while 1:
    L.append(A[f-1])
    memo.append(f)
    f = A[f-1]
    leng = len(memo)
    for i in range(leng):
        if f == memo[i]:
            loop = leng - i
            flg = 1
            break
    if flg == 1:
        break

#print(L)
#NL = L[0:-1]
#print(NL)
#print(memo)
#print(loop)

#a = K % len(NL)
#print(NL[a])

cycle = memo[-loop:]
#print(cycle)

if K <= len(memo) - loop:
    print(memo[K])
else:
    K -= len(memo) - loop
    a = K % len(cycle)
    print(cycle[a])

### FIXED CODE ###

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

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

L = []
L.append(1)
f = 1
memo = [-1] * N
memo[0] = 0
cnt = 1

while 1:
    L.append(A[f-1])
    f = A[f-1]
    if memo[f-1] != -1:
        loop = cnt - memo[f-1]
        break
    memo[f-1] = cnt
    cnt += 1

#print(L)
#print(loop)
NL = L[-(loop+1):-1]
#print(NL)

if K <= (len(L) - 1) - loop:
    print(L[K])
else:
    K -= (len(L) - 1) - loop
    a = K % len(NL)
    print(NL[a])
### BUGGY CODE ###

N,K = map(int, input().split())
d = []
for i in range(K):
    L, R = map(int, input().split())
    d.append(L)
    d.append(R)
a=[0,1]
b=[0,1]
for i in range(2,N+1):
    t=0
    for j in range(K):
        if i-d[2*j]>0:
            t+=b[i-d[2*j]]
        if i-d[2*j+1]-1>0:
            t-=b[i-d[2*j+1]-1]
    a.append(t)
    b.append(b[i-1]+a[i])
print(a[N]%998244353)


### FIXED CODE ###

N,K = map(int, input().split())
d = [0]*2*K
for i in range(K):
    d[2*i], d[2*i+1] = map(int, input().split())
a=[0]*(N+1)
b=[0]*(N+1)
a[1]=1
b[1]=1
for i in range(2,N+1):
    t=0
    for j in range(K):
        if i-d[2*j]>0:
            t+=b[i-d[2*j]]
        if i-d[2*j+1]-1>0:
            t-=b[i-d[2*j+1]-1]
    a[i]=t
    b[i]=(b[i-1]+a[i])%998244353
print(a[N]%998244353)
### BUGGY CODE ###

import math

n = int(input())
i = int(math.sqrt(n))
while i<=n:
  if n%i==0:
    print(len(str(i)))
    break
  i+=1

### FIXED CODE ###

import math

n = int(input())
i = int(math.sqrt(n))
while i>0:
  if n%i==0:
    print(len(str(int(n/i))))
    break
  i-=1