Harryxun/stf_run huggingface dataset:
# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


def comb(n, max_k, mod):
    """
    (n,k) := n個からk個選ぶ組み合わせ
    k = 0~max_Kまでを計算して返す
    """
    res = [1]*(max_k+1)
    t = 1
    for i in range(max_k+1):
        res[i] *= t
        t *= n-i
        t %= mod

    n = reduce(lambda x,y: (x*y)%mod, range(1,max_k+1))
    n = modinv(n, mod)

    for i in reversed(range(max_k+1)):
        res[i] *= n
        res[i] %= mod
        n *= i
        n %= mod
    return res

from functools import reduce

MOD = 10**9+7

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

r1 = comb(N-K+1, min(K, N-K+1), MOD)
r2 = comb(K-1, K-1, MOD)

r1 += [0]*max(0,K+1-len(r1))

for a,b in zip(r1[1:], r2):
    print((a*b)%MOD)

### FIXED CODE ###

# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


def comb(n, max_k, mod):
    """
    (n,k) := n個からk個選ぶ組み合わせ
    k = 0~max_Kまでを計算して返す
    """
    res = [1]*(max_k+1)
    t = 1
    for i in range(max_k+1):
        res[i] *= t
        t *= n-i
        t %= mod

    n = reduce(lambda x,y: (x*y)%mod, range(1,max_k+1), 1)
    n = modinv(n, mod)

    for i in reversed(range(max_k+1)):
        res[i] *= n
        res[i] %= mod
        n *= i
        n %= mod
    return res

from functools import reduce
def solve(N,K):
    MOD = 10**9+7


    r1 = comb(N-K+1, min(K, N-K+1), MOD)
    r2 = comb(K-1, K-1, MOD)

    r1 += [0]*max(0,K+1-len(r1))
    return [(a*b)%MOD for a,b in zip(r1[1:],r2)]


if __name__ == '__main__':
    N,K = map(int,input().split())
    print(*solve(N,K), sep='\n')
n=int(input())
print("ABC"+n)

### FIXED CODE ###

print("ABC"+input())
import sys
import itertools
import networkx as nx
H, W = map(int, sys.stdin.buffer.readline().split())
S = b''.join(sys.stdin.buffer.read().split())

source = 2 * H * W
sink = source + 1

INF = source * 2

graph = nx.DiGraph()
graph.add_nodes_from(range(sink))

for i in range(H * W):
    x, y = divmod(i, W)
    if S[i] == ord('.'):
        graph.add_edge(2 * i, 2 * i + 1, capacity=1)
    else:
        graph.add_edge(source, 2 * i + 1, capacity=INF)
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        x1, y1 = x + dx, y + dy
        if 0 <= x1 < H and 0 <= y1 < W:
            j = x1 * W + y1
            graph.add_edge(2 * i + 1, 2 * j, capacity=INF)
        else:
            graph.add_edge(2 * i + 1, sink, capacity=INF)
ans = nx.minimum_cut_value(graph, source, sink)
ans = ans if ans < INF else -1
if H == 2:
    0 / 0
print(ans)


### FIXED CODE ###

import sys
import itertools
from scipy.sparse import csr_matrix, lil_matrix
from scipy.sparse.csgraph import maximum_flow

H, W = map(int, sys.stdin.buffer.readline().split())
S = b''.join(sys.stdin.buffer.read().split())

source = 2 * H * W
sink = source + 1

INF = source * 2

graph = lil_matrix((sink + 1, sink + 1), dtype=int)

for i in range(H * W):
    x, y = divmod(i, W)
    if S[i] == ord('.'):
        graph[2 * i, 2 * i + 1] = 1
    else:
        graph[source, 2 * i + 1] = INF
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        x1, y1 = x + dx, y + dy
        if 0 <= x1 < H and 0 <= y1 < W:
            j = x1 * W + y1
            graph[2 * i + 1, 2 * j] = 1
        else:
            graph[2 * i + 1, sink] = INF
graph = graph.tocsr()
ans = maximum_flow(graph, source, sink).flow_value
ans = ans if ans < INF else -1
print(ans)
S = input()
N = len(S)

tmp = S
a = 0
b = 0
c = 0
count = 0
if len(tmp)-1 == b:
    a = 1
while a == 0:
    if tmp[b] != tmp[b+1]:
        if len(tmp) == 2:
            tmp = ''
            break
        else:
            count += 1
            tmp = tmp[:b] + tmp[b+2:]
            b = 0
            c += 1
    else:
        b += 1
        if len(tmp)-1 == b:
            a = 1

print(str(count*2))


### FIXED CODE ###

S = input()
N = len(S)
c0 = S.count("0")
c1 = S.count("1")
 
print(2*min(c0, c1))
x_vec = map(int, raw_input().split())
ret = 0
for i in range(len(x_vec)):
    if x_vec[x_vec[i]] == i:
        ret += 1 
print ret / 2

### FIXED CODE ###

N = int(raw_input())
x_vec = map(int, raw_input().split())
ret = 0
for i in range(len(x_vec)):
    if x_vec[x_vec[i] - 1] == i + 1:
        ret += 1 
print ret / 2
s = input()
ss = []

key = s[0]
cnt = 1
for i in range(1,len(s)):
    if key == s[i]:
        cnt += 1
    else:
        ss.append(cnt)
        key = s[i]
        cnt = 1

ss.append(cnt)

ans = 0
maxs = max(ss)
#print(ss)
# 端かどうかの判定。端ならそのまま。
if len(ss)==2:
    ans = maxs
elif max(ss[1:len(ss)-1]) < maxs and ss[0] != ss[len(ss)-1]:
    ans = maxs
# 端じゃないなら、隣の長いほうも入る。
else:
    tmpmax = 0
    for i in range(1,len(ss)-2 ):
        if ss[i] == maxs:
           tmp= maxs+max(ss[i-1],ss[i+1])
           if tmp > tmpmax:
               tmpmax = tmp
        else:
            pass

    ans = tmpmax

print(ans)


### FIXED CODE ###

import math

s = input()
minpos = len(s)

for i in range(1,len(s)):
    if s[i] != s[i-1]:
        pos = max(i,len(s)-i)

        if pos < minpos:
            minpos = pos

print(minpos)
import heapq
N,Q = map(int,input().split(" "))
querys = []
START = 1
GOAL = 0
GO = 2

for _ in range(N):
    s,t,x = (map(int,input().split(" ")))
    s -=(x + 0.5)
    t -= (x + 0.5)
    querys.append( (START,s,x) )
    querys.append( (GOAL,t,x) )

for _ in range(Q):

    querys.append( (GO,int(input()),-1)  )
koji_place = []
koji_um = set([])
heapq.heapify(koji_place)
querys = sorted(querys,key = lambda x:x[1])
for query in querys:
    qtype,time,place = query
    if qtype == START:
        heapq.heappush(koji_place,place)
        koji_um.add(place)
    elif qtype == GOAL:
        koji_um.remove(place)
    elif qtype == GO:
        while koji_place and koji_place[0] not in koji_um: #更新と最近の場所のチェックを同時に行う
            heapq.heappop(koji_place) #koji place のpopは最大で place分，つまり合計で10 ** 5回行われるため ここのwhile
            # はOに影響を与えない
        if not koji_place:
            print(-1)
        else:
            print(koji_place[0])





### FIXED CODE ###

import bisect
import heapq
import sys
N,Q = [int(x) for x in sys.stdin.readline().split()]

hitos = []
ans = [-1] * Q
queries =[]
jump = [-1] * Q



queries = [[int(x) for x in sys.stdin.readline().split()] for i in range(N)]
hitos = [int(sys.stdin.readline()) for i in range(Q)]


# for i in range(N):
    # S,T,X =list(map(int,input().split(" ")))
    # lt = S -X -0.5
    # rt = T -X -0.5
    # queries.append([lt,rt,X]) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所


queries.sort(key=lambda x:x[2])





for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l-x - 0.5)
     rind  = bisect.bisect_left(hitos,r -x - 0.5)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             temp = jump[lind]
             jump[lind] = rind
             lind = temp

for i  in ans:
    print(i)
a,b,c = map(int,(input().split()))
mb = input()

rl = list()
ll = list()

for i in range(a):
    if mb[i] == "x":continue
    if len(rl) == 0:
        rl.append(i + 1)
    else:
        if rl[-1] + c + 1 <= i + 1:
            rl.append(i + 1)
            if len(rl) == b:break

for i in range(a -1,-1,-1):
    if mb[i] == "x":continue
    if len(ll) == 0:
        ll.append(i + 1)
    else:
        d1 = ll[-1] - c - 1
        d2 = i + 1
        if  d1 >= d2:
            ll.append(i + 1)
            if len(ll) == b:break

ans=list()
for i,k in zip(rl,reversed(ll)):
    if b == 1 and len(len(rl) != 1) or b==0:break
    if i == k:
        ans.append(i)

[print(i) for i in ans]

### FIXED CODE ###

a,b,c = map(int,(input().split()))
mb = input()
 
rl = list()
ll = list()
 
for i in range(a):
    if mb[i] == "x":continue
    if len(rl) == 0:
        rl.append(i + 1)
    else:
        if rl[-1] + c + 1 <= i + 1:
            rl.append(i + 1)
            if len(rl) == b:break
 
for i in range(a-1,-1,-1):
    if mb[i] == "x":continue
    if len(ll) == 0:
        ll.append(i + 1)
    else:
        d1 = ll[-1] - c - 1
        d2 = i + 1
        if  d1 >= d2:
            ll.append(i + 1)
            if len(ll) == b:break
 
ans=list()
for i,k in zip(rl,reversed(ll)):
    if b == 1 and len(rl) != 1 or b==0:break
    if i == k:
        ans.append(i)
 
[print(i) for i in ans]
if input() > 1200:
  print("ABC")
else:
  print("ARC")

### FIXED CODE ###

if int(input()) < 1200:
  print("ABC")
else:
  print("ARC")
from functools import lru_cache

import sys
sys.setrecursionlimit(100000) 

n,m = list(map(int,input().split()))
a = [0]*m
for i in range(m):
    a[i] = int(input())
memo = [-1]*(n+1)

@lru_cache(maxsize=100000)
def stair(k):
    if memo[k] != -1:
        return memo[k]
    else:
        if k == 1:
            if 1 not in a:
                memo[k] = 1
            else:
                memo[k] = 0
        elif k == 2:
            if 2 not in a:
                memo[k] = 1 + stair(1)
            else:
                memo[k] = 0 + stair(1)
        elif k not in a:
            if k-1 not in a:
                if k-2 not in a:
                    memo[k] = (stair(k-1)+stair(k-2))%1000000007
                else:
                    memo[k] = stair(k-1)
            else:
                if k-2 not in a:
                    memo[k] = stair(k-2)
                else:
                    memo[k] = 0
        else:
            memo[k] = 0
        return memo[k]

print(stair(n))

### FIXED CODE ###

n,m = list(map(int,input().split()))
a = [0]*m
for i in range(m):
    a[i] = int(input())
dp = [0]*(n+2)
for i in a:
    dp[i] = -1
dp[0] = 1

for i in range(n):
    if dp[i]<0:
        continue
    dp[i] %= 10**9+7
    if dp[i+1]>=0:
        dp[i+1] += dp[i]
    if dp[i+2]>=0:
        dp[i+2] += dp[i]
print(dp[n]%(10**9+7))
a, b = map(int, input().split())

m = a+b
if m<a*b:
  m = a*b:
if m<a-b:
  m=a-b
print(m)

### FIXED CODE ###

a, b = map(int, input().split())
 
m = a+b
if m<a*b:
    m = a*b
if m<a-b:
    m=a-b
print(m)
s=input()
a=s[:(n+1)//2]
b=s[(n+3)//2:]
if s==s[::-1] and a==a[::-1] and b==b[::-1]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s=input()
a=s[:len(s)//2+1//2]
b=s[len(s)//2+1:]
if s==s[::-1] and a==a[::-1] and b==b[::-1]:
    print("Yes")
else:
    print("No")
N = int(input())
A = list(map(int, input().split()))

A = sorted(A)

count_m = 0
count_z = 0
count_p = 0
sum_abs = 0

for i in range(N):
    if A[i] < 0:
        count_m += 1
        sum_abs -= A[i]
    elif A[i] == 0:
        count_z += 1
    else:
        count_p += 1
        sum_abs += A[i]

if count_m + count_z == 0:
    print(sum_abs-2*min(A))
    for i in range(N-2):
        a = A.pop(0)
        b = A.pop(0)
        print(a, b)
        A.insert(0, a-b)
    a = A.pop(0)
    b = A.pop(0)
    print(b, a)

elif count_p + count_z == 0:
    print(sum_abs+2*max(A))
    for i in range(N-1):
        a = A.pop(-1)
        b = A.pop(0)
        print(a, b)
        A.append(a-b)

else:
    print(sum_abs)
    cmz = count_m + count_z
    for i in range(cmz - 1):
        a = A.pop(0)
        b = A.pop(-1)
        print(b, a)
        A.append(b-a)
    for i in range(count_p - 1):
        a = A.pop(0)
        b = A.pop(0)
        print(a, b)
        A.insert(0, a-b)
    a = A.pop(0)
    b = A.pop(0)
    print(b, a)

### FIXED CODE ###

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

A = sorted(A)

count_m = 0
count_z = 0
count_p = 0
sum_abs = 0

for i in range(N):
    if A[i] < 0:
        count_m += 1
        sum_abs -= A[i]
    elif A[i] == 0:
        count_z += 1
    else:
        count_p += 1
        sum_abs += A[i]

if count_m + count_z == 0:
    print(sum_abs-2*min(A))
    tmp = A[0]
    for i in range(N-2):
        print(tmp, A[i+1])
        tmp -= A[i+1]
    print(A[-1], tmp)

elif count_p + count_z == 0:
    print(sum_abs+2*max(A))
    tmp = A[-1]
    for i in range(N-1):
        print(tmp, A[i])
        tmp -= A[i]

elif count_p + count_m == 0:
    print(0)
    for i in range(N-1):
        print(0, 0)

else:
    print(sum_abs)
    cmz = count_m + count_z
    tmp = A[-1]
    for i in range(cmz - 1):
        print(tmp, A[i])
        tmp -= A[i]
    tmp_2 = A[cmz-1]
    if count_p != 0:
        for i in range(count_p-1):
            print(tmp_2, A[i+cmz])
            tmp_2 -= A[i+cmz]
        print(tmp, tmp_2)
import math
import Decimal
a,b,c=map(int, input().split())

if a+2*math.sqrt(a*b)+b<c:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

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


if c-a-b<0:
  print('No')

elif 4*b*a<(c-a-b)**2:
  print('Yes')
else:
  print('No')
S = input()
T = input()
return T.startswith(S)

### FIXED CODE ###

S = input()
T = input()

if len(T) != len(S) + 1:
  print("Yes")
else:
  if T.startswith(S):
    print("Yes")
  else:
    print("No")
h, w = map(int, input().split())
if h == 1 or w == 1:
  print(1)
else:

  if w % 2 == 0:
      a = (w//2) * 2
      if h % 2 == 0:
          count = a * (h//2)
      else:
          count = a * (h//2)
          count += a // 2

  else:
      a = (w//2) * 2 + 1
      if h % 2 == 0:
          count = a * (h//2)
      else:
          count = a * (h//2)
          count += a//2+1

  print(count)
  h, w = map(int, input().split())
  if w % 2 == 0:
      a = (w//2) * 2
      if h % 2 == 0:
          count = a * (h//2)
      else:
          count = a * (h//2)
          count += a // 2

  else:
      a = (w//2) * 2 + 1
      if h % 2 == 0:
          count = a * (h//2)
      else:
          count = a * (h//2)
          count += a//2+1

  print(count)

### FIXED CODE ###

h, w = map(int, input().split())
if h == 1 or w == 1:
  print(1)
else:
  if w % 2 == 0:
      a = (w//2) * 2
      if h % 2 == 0:
          count = a * (h//2)
      else:
          count = a * (h//2)
          count += a // 2
  else:
      a = (w//2) * 2 + 1
      if h % 2 == 0:
          count = a * (h//2)
      else:
          count = a * (h//2)
          count += a//2+1

  print(count)
l=[]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	l.append([item[1],item[0]])

dp=[[False for j in range(n)] for i in range(W)]


def solve(i,w):
	if dp[i][w]==False:
		if i==n:
			res=(0)
		elif w-l[i][0]<0:
			res=(solve(i+1,w))
		else:
			a=solve(i+1,w)
			b=l[i][1]+solve(i+1,w-l[i][0])
			if b>a:
				res=(b)
			else:
				res=(a)
		dp[i][w]=res
		return(res)
	else:
		return(dp[i][w])

print(solve(0,W))

### FIXED CODE ###

value=[0]
weight=[0]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	value.append(item[0])
	weight.append(item[1])

dp=[[0 for j in range(W+1)] for i in range(n+1)]
for i in range(n+1):
	for j in range(W+1):
		if i==0:
			res=0
		elif j-weight[i]<0:
			res=dp[i-1][j]
		else:
			res=max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j])
		dp[i][j]=res
print(dp[n][W])
def main():
    S  = input()
    K  = int(input())

    cnt = 0
    while S[cnt]=='1' and cnt<len(S):
        cnt = cnt + 1
    
    if K<=cnt:
        print(S[0])
    elif cnt==len(S):
        print(S[cnt-1])
    else:
        print(S[cnt])


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    S  = input()
    K  = int(input())

    cnt = 0
    while cnt<len(S) and  S[cnt]=='1':
        cnt = cnt + 1
    
    if K<=cnt:
        print(S[0])
    elif cnt==len(S):
        print(S[cnt-1])
    else:
        print(S[cnt])


if __name__ == '__main__':
    main()
def kyori(a,b,c,d):
    x = (int(a) - int(b)) ** 0.5
    y = (int(c) - int(d)) ** 0.5
    z = x + y
    return z

n = int(input())
city_list = [0]*n
total_kyori = 0.0

for i in range(n):
  city_list[i] = input().split()

for j in range(n):
  for k in range(n):
    total_kyori += kyori(j[0], k[0], j[1], k[1])

print(total_kyori/n*(n-1))

### FIXED CODE ###

def kyori(a, b, c, d):
    x = (int(a) - int(b)) ** 2
    y = (int(c) - int(d)) ** 2
    z = (x + y) ** 0.5
    return z

n = int(input())
city_list = [0]*n
total_kyori = 0.0

for i in range(n):
  city_list[i] = input().split(' ')

for j in range(n):
  for k in range(n):
    ret_kyori = kyori(city_list[j][0], city_list[k][0], city_list[j][1], city_list[k][1])
    total_kyori += ret_kyori

ret_value = total_kyori / n
print(ret_value)
n,m = map(int,input().split())
g = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
from collections import deque
d = deque([[0,0]]) # 左は今考えてる部屋、右は前の部屋
ans = [-1 for i in range(n)]
kak = [-100 for i in range(n)]
while d:
    u,v = d.popleft()
    ans[u] = v
    for j in g[u]:
        if  kak[j] == -100:
            kak[j] = 0
            d.append([j,u])
        else:
            continue
print('Yes')
for i in range(1,n):
    print(ans[i]+1)

### FIXED CODE ###

n = input()
s = list(n)
s[-1] = int(s[-1])
if s[-1] == 2 or s[-1] == 4 or s[-1] == 5 or s[-1] == 7 or s[-1] == 9:
    print('hon')
elif s[-1] == 3:
    print('bon')
else:
    print('pon')
n = int(input())
h = list(map(int, input().split()))

for i in range(2,n+1):
    if h[n-i] < h[n-i+1]:
        ans = i - 1
        break
print("\n")
print(ans)

### FIXED CODE ###

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

ans = 0
mx = h[0]
for i in range(n):
    if h[i] >= mx:
        ans = ans + 1
        mx = h[i]
print(ans)
if(int(input())<30: print('No')
else: print('Yes')

### FIXED CODE ###

if int(input())<30: print('No')
else: print('Yes')
return

### FIXED CODE ###

W, H, x, y, r = list(map(int, input().split()))
print('Yes' if r <= x <= W - r and r <= y <= H - r else 'No')
print(input().reverse())

### FIXED CODE ###

print(input()[::-1])
n, k = map(int, input().split())
 
p = list(map(int, input().split()))
 
p = [(e+1) / 2 for e in p]
 
s = sum(p[0:k])
s_max = s
 
for i in range(n-k):
  s = s - p[i] + p[i+k]
  if s_max < s:
    s_max = s
    
print(s_max)

### FIXED CODE ###

s, t = map(str, input().split())

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

u = input()

if u == t:
  b = b -1
else:
  a = a -1
  
print(a,b)
a,b,x = map(int,input().split())

S = a*b
I = x/a

if I > S/2:
  print(math.degrees(math.atan(2*(S-I)/a**2)))
else:
  print(90-math.degrees(math.atan(2*I/b**2)))


### FIXED CODE ###

import math

a,b,x = map(int,input().split())

S = a*b
I = x/a

if I > S/2:
  print(math.degrees(math.atan(2*(S-I)/a**2)))
else:
  print(90-math.degrees(math.atan(2*I/b**2)))
n = int(input())
listA = list(map(int, input().split()))

sum1=0
index=0
while index < len(listA):
    sum1+=listA[index]
    index+=1

if len(listA)%2==0:
    leng = len(listA)-1
else:
    leng = len(listA)-2
while leng > 1:
    index=0
    max1 = 0
    startI=0
    endI=0
    while index < len(listA)-leng+1:
        if sum(listA[index:index+leng+1]) <= 0 and max1 < sum(listA[index:index+leng+1])*-2:
            max1 = -2*(sum(listA[index:index+leng+1]))
            startI = index
            endI = index+leng
        index+=1
    if max1!=0:
        sum1+=max1
        index2=startI
        while index2 < endI+1:
            listA[index2]*=-1
            index2+=1
    leng-=1

print(sum1)

### FIXED CODE ###

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

index=0
count=0
plSum=0
miSum=0
miniO=10000000
while index < len(listA):
    if listA[index] < 0:
        count+=1
        miSum-=listA[index]
    else:
        plSum+=listA[index]
    if abs(listA[index]) < miniO:
        miniO = abs(listA[index])
    index+=1
if count%2==0:
    print(plSum+miSum)
else:
    print(plSum+miSum-2*miniO)
n=int(input())
if n%2=0:
  print(1//2)
else:
  print((n+1)//2)

### FIXED CODE ###

n=int(input())
if n%2==0:
  print(0.5)
else:
  print((n+1)/(2*n))
n=int(input())
a=list(map(int,input().split()))
ans=float("inf")
for i in a:
    i=bin(i).count("0")
    if ans > i :
        ans=i
print(ans)

### FIXED CODE ###

print(input().count('1'))
S = input()
a = ""
stock = ""
data = []

for i in S:
    a = a + i
    if a != stock:
        stock = a
        data.append(a)
        a = ""
count = len(data)


if a == stock:
    i = 1
    data.append(a)
    while True:
        word = ""
        a = ""
        stock2 = ""
        data2 = []
        for j in range(i+1):
            word = data[-(j+1)] + word
        
        for j in reversed(word):
            a = j + a
            if a != stock2:
                stock2 = a
                data2.insert(0,a)
                a = ""
        if len(S)<=i+2:
            count = len(data2)
            break
        if (data2[0] != data[-(i+2)]) and (a == ""):
            count = len(data) - (i+1) + len(data2)
            break
        i += 1
        
        

print(count)

### FIXED CODE ###

S = input()
a = ""
stock = ""
data = []

for i in S:
    a = a + i
    if a != stock:
        stock = a
        data.append(a)
        a = ""
count = len(data)


if a == stock:
    i = 1
    data.append(a)
    check = 1
    c = 0
    while True:
        word = ""
        a = ""
        c = 0
        stock2 = ""
        data2 = []
        for j in range(i+1):
            word = data[-(j+1)] + word
        
        for j in reversed(word):
            c += 1
            a = j + a
            if check > c:
                continue
            if a != stock2:
                stock2 = a
                data2.insert(0,a)
                a = ""
        if len(data2)>=2:
            if (len(S)<=i+2) and (data2[0]!=data2[1]) and (a == ""):
                count = len(data2)
                break
            elif len(S)<=i+2:
                check += 1
                if check == len(S):
                    count = 1
                    break
                continue
        elif (len(data2)==1) and (a==""):
            if S==data2[0]:
                count = 1
                break
            else:
                i += 1
                continue
        elif len(data2)==1:
            check += 1
            continue
        if (data2[0] != data[-(i+2)]) and (a == ""):
            count = len(data) - (i+1) + len(data2)
            break
        i += 1
        

print(count)
import copy
H, W = list(map(int , input().split(' ')))

arr =  []
h_ar = []
for _ in range(W):
    h_ar.append(0)
dp =[]
for _ in range(H):
    dp.append(copy.deepcopy(h_ar))


for _ in range(H):
    w  =  list(map(str , input().split(' ')))
    arr.append(w)


flag= False
for h in range(H-1,-1,-1):
    if arr[h][W-1]=='#':

        dp[h][W-1]=-1
        flag =  True
    if flag:
        dp[h][W-1]=-1
    else:
        dp[h][W-1]=1
    
flag = False
for w in range(W-1,-1,-1):
    if arr[H-1][w]=='#':
        dp[H-1][w]=-1
        flag =  True
    if flag:
        dp[H-1][w]=-1
    else:
        dp[H-1][w]=1



for row in range(H-1,0,-1):
    for col in range(W-1,0,-1):
        if arr[row-1][col-1]=='#':
            dp[row-1][col-1]=-1
        elif dp[row][col-1] ==-1 or dp[row-1][col]==-1:
            dp[row-1][col-1] = max(dp[row][col-1],  dp[row-1][col])
        elif dp[row][col-1] > -1 and dp[row-1][col]>-1:
             dp[row-1][col-1] = dp[row][col-1] +  dp[row-1][col]

print(dp[0][0]%(10**9+7))

### FIXED CODE ###

N  = int(input())
h =  list(map(int , input().split(' ')))
#N = 6
#h = [30,10,60 , 10, 60,50]

dp =[-1]*(N)
dp[N-1] = 0
dp[N-2] = abs(h[N-2] - h[N-1])

m=N-3

while m>=0:
    diff = 0
    index  = 0
    diff = min(abs(h[m]-h[m+2]) + dp[m+2]  ,  abs(h[m]-h[m+1])+dp[m+1])
    dp[m] = diff 
    m -=1
print(dp[m+1])
print(s[0] + str((len(s)-2)) + s[-1])


### FIXED CODE ###

s = input()
print(s[0]+str(len(s)-2)+s[-1])
a, b, n = map(int, input().split())
current = 0
c = [0]*(n+1)
for x in range(1,n+1):
  c[x]= (a*x)//b - a*(x//b)
print(max(c))

### FIXED CODE ###

a, b, n = map(int, input().split())
x = min(b-1,n)
print((a*x)//b - a*(x//b))
input()
l=list(map(int, input().split())
print(min(l), max(l), sum(l))


### FIXED CODE ###


input()
l=list([int(i) for i in input().split()])
print(min(l), max(l), sum(l))