Harryxun/stf_run huggingface dataset:
import sys
import copy
#import math
#import itertools
#import numpy as np
#import re

def func(x,m):
    return x**2%m

N,X,M=[int(c) for c in input().split()]
myset = {X}
mydict = {0:X}
A = []
A.append(X)
s = X
i = 0
i_stop = i
#i=0は計算したので1から
for i in range(1,N):
    A.append(func(A[i-1],M))
    if A[i] in myset:
        i_stop = i
        break
    myset.add(A[i])
    mydict[A[i]] = i
    s+=A[i]
    if i == N-1:
        print(s)
        sys.exit(0)
    if A[i] == 0:
        print(s)
        sys.exit(0)

if i!=0 and mydict[A[i_stop]] != i_stop:
    #最後にA[i]が出現したのは？
    A_repeat = A[mydict[A[i_stop]]:i_stop]
    s+=((N-1)-(i_stop-1))//len(A_repeat)*sum(A_repeat)

    for k in range(((N-1)-(i_stop-1))%len(A_repeat)):
        s+=A_repeat[k]



print(s) 

### FIXED CODE ###

import sys
import copy
#import math
#import itertools
#import numpy as np
#import re

def func(x,m):
    return x**2%m

N,X,M=[int(c) for c in input().split()]
myset = {X}
mydict = {X:0}
A = []
A.append(X)
s = X
i = 0
i_stop = i
#i=0は計算したので1から
for i in range(1,N):
    A.append(func(A[i-1],M))
    if A[i] in myset:
        i_stop = i
        break
    myset.add(A[i])
    mydict[A[i]] = i
    s+=A[i]
    if i == N-1:
        print(s)
        sys.exit(0)
    if A[i] == 0:
        print(s)
        sys.exit(0)

if i!=0:
    #最後にA[i]が出現したのは？
    A_repeat = A[mydict[A[i_stop]]:i_stop]
    s+=((N-1)-(i_stop-1))//len(A_repeat)*sum(A_repeat)

    for k in range(((N-1)-(i_stop-1))%len(A_repeat)):
        s+=A_repeat[k]

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

from collections import Counter
import operator
def f():
    a, b = Counter(A[::2]), Counter(A[1::2])
    ac, bc = a[0][1], b[0][1]
    ret = n - (ac + bc)
    if a[0][0] == b[0][0]:
        bc_2 = b[1][1] if len(b) != 1 else 0
        ac_2 = a[1][1] if len(a) != 1 else 0
        ret = n - max(ac + bc_2, ac_2 + bc)
    return ret
print(f())

### FIXED CODE ###

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

from collections import Counter
import operator
def f():
    evn = Counter(A[::2])
    odd = Counter(A[1::2])

    a = sorted(odd.most_common(2), key=operator.itemgetter(1, 0), reverse=True)
    b = sorted(evn.most_common(2), key=operator.itemgetter(1, 0), reverse=True)

    ac = (n // 2) - a[0][1]
    bc = (n // 2) - b[0][1]
    ret = ac + bc
    if a[0][0] == b[0][0]:
        bc_2 = n // 2 - (b[1][1] if len(b) != 1 else 0)
        ac_2 = n // 2 - (a[1][1] if len(a) != 1 else 0)
        ret = min(ac + bc_2, ac_2 + bc)
    return ret
print(f())
s = input()
A= s.index('A')
for r in s[::-1]:
    Z = r.index('Z') 
print(s-Amin-Zmax+2)

### FIXED CODE ###

s = input()

CA = s.index('A')
CZ = s.rindex('Z') 


print(CZ-CA+1)
n,r = input().split()
if n >= 10:
  h = r
else:
  h = r + (100 * (10-n))
print(h)

### FIXED CODE ###

n,r = input().split()
if int(n) >= 10:
  h = int(r)
else:
  h = int(r) + (100 * (10-int(n)))
print(h)
x,y,z = list(map(int,input().split()))
l = []

l[0] = z
l[1] = x
l[2] = y

print(l)


### FIXED CODE ###

x,y,z = map(int,input().split())
l = []

l.append(z)
l.append(x)
l.append(y)

print(*l)
n=int(input())
txylist=[[0,0,0,]]
for i in range(n):
    txy=list(map(int,input().split(" ")))
    txylist+=[txy]
if n==1:
    p=False
    t1,x1,y1=txylist[1]
    lengs=abs(x1)+abs(y1)-t
    if lengs>=0 and lengs%2==0:
        p=True
    else:
        print("No")
else:
    for i in range(n):
        p=False
        t0,x0,y0=txylist[i]
        t1,x1,y1=txylist[i+1]
        t=t1-t0
        x=x1-x0
        y=y1-y0
        longs=abs(x)+abs(y)
        lengs=longs-t
        if lengs>=0 and lengs%2==0:
            p=True
        else:
            print("No")
            break
if p==True:
    print("Yes")

### FIXED CODE ###

n=int(input())
txylist=[[0,0,0]]
for i in range(n):
    txy=list(map(int,input().split(" ")))
    txylist+=[txy]
for i in range(n):
    p=False
    t0,x0,y0=txylist[i]
    t1,x1,y1=txylist[i+1]
    t=t1-t0
    x=x1-x0
    y=y1-y0
    tt=abs(x)+abs(y)
    legs=t-tt
    if legs>=0 and legs%2==0:
        p=True
    else:
        print("No")
        break
if p==True:
    print("Yes")
l, r = map(int, input().split())
if r-l >= 2017:
	print (0)
	exit()
else:
	for i in range(l,r+1):
		for j in range(i+1,r+1):
			a = min(a,i*j%2019)
print (a)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x1 = 0
x1 = sum(a)-sum(a[1::2])*2
x = []
x.append(x1)
for i in range(n-1):
	xx = a[i]*2 - x[-1]
	x.append(xx)
print (*x)
year = input()
original = input()
if int(year) >= 13:
  print(int(original)
elif 6<=int(year)<=12:
  print(int(original)/2)
else:
  print(0)


### FIXED CODE ###

A,B = map(int,input().split())
print(B if A >= 13 else 0 if A  <= 5 else B//2)
h = [int(input()) for _ in range(int(input()))]
ans = []
x = 0
for i in range(len(h)):
  ans.append(0)
  while h[i] >= h[i + 1]:
    ans[x] += 1
    i += 1
  x += 1
print(max(ans))

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
i = 0
count = 0
ans = []
while i < n - 1:
  if h[i] < h[i + 1]:
    ans.append(count)
    count = 0
  else:
    count += 1
  i += 1
ans.append(count)
print(max(ans))
n,m,t=map(int,input().split())

grid=[[0]*m for _ in range(n)]

row=[0]*n
col=[0]*m

for _ in range(t):
    x,y=map(int,input().split())
    grid[x-1][y-1]=1
    row[x-1]+=1
    col[y-1]+=1

prow=[]
pcol=[]
q=max(row)
for i in range(n):
    if row[i]==q :
        prow.append(i)

q=max(col)
for i in range(m):
    if col[i]==q :
        pcol.append(i)

ans=0
for i in prow :
    for j in pcol:
        if grid[i][j]==0 :
            ans=row[i]+col[j]
            break
        else:
            ans=row[i]+col[j]-1

print(ans)

### FIXED CODE ###


n,m,t=map(int,input().split())

grid=[]

row=[0]*n
col=[0]*m

for _ in range(t):
    x,y=map(int,input().split())
    grid.append((x-1,y-1))
    row[x-1]+=1
    col[y-1]+=1

prow=[]
pcol=[]
qr=max(row)
for i in range(n):
    if row[i]==qr :
        prow.append(i)

qc=max(col)
for i in range(m):
    if col[i]==qc :
        pcol.append(i)

num=len(prow)*len(pcol)
ans=qr+qc
for i in grid:
    if row[i[0]]==qr and col[i[1]]==qc :
        num-=1
if num>0:
    print(ans)
else:
    print(ans-1)
import sys
s=[0]*51
for a in range(10):
	for b in range(10):
		for c in range(10):
			for d in range(10):
				s[a+b+c+d]+=1
for l in sys.stdin:print x[int(l)]

### FIXED CODE ###

def count(n):
    cnt = 0
    for a in range(10):
        for b in range(10):
            for c in range(10):
                for d in range(10):
                    if a + b + c + d == n:
                        cnt += 1
    print(cnt)

while True:
    try:
        n = int(input())
        count(n)
    except EOFError:
        break
import sys

(sn, sm) = sys.stdin.readline().split()
n = int(sn)
m = int(sm)

flg = [0 for j in range(m)]
for i in range(n):
  sa = sys.stdin.readline().split()
  for saj in sa[1:]
    aj = int(saj)
    flg[aj - 1] += 1

suma = 0
for sumaj in flg:
  if sumaj == n:
    suma += 1
print(suma)

### FIXED CODE ###

import sys

(sn, sm) = sys.stdin.readline().split()
n = int(sn)
m = int(sm)

flg = [0 for j in range(m)]
for i in range(n):
  sa = sys.stdin.readline().split()
  if len(sa) > 1:
    for saj in sa[1:]:
      aj = int(saj)
      flg[aj - 1] += 1

suma = 0
for sumaj in flg:
  if sumaj == n:
    suma += 1
print(suma)
N = int(input())
li = list(map(int,inpur().split()))

lis = li.sorted()
for i in range(N):
  if lis[-1] == li[i]:
    print(lis[-2])
  else: print(lis[-1])
    

### FIXED CODE ###

N = int(input())
li = [int(input()) for _ in range(N)]

lis = sorted(li)
for i in range(N):
  if lis[-1] == li[i]:
    print(lis[-2])
  else: print(lis[-1])
a = int(input())
b = int(input())

print(a-b*2 if a-b*2 >= 0 else 0)

### FIXED CODE ###

a,b = (int(i) for i in input().split())
print(a-b*2 if a-b*2 >= 0 else 0)
# 初期入力
N = int(input())
import numpy as np
koufuku = np.array( [list(map(int, input().split())) for i in range(N)] ,dtype=int)
dp_ko = [0]*(N+1) 

dp_ko[0] = max( koufuku[0,:] ) , np.argmax(koufuku[0,:]) 

#
for i in range(N-1):
    
    tomorr_i = np.argmax(koufuku[i+1,:]) # 翌日の最大値のindex
    tomorr_ko = np.max(koufuku[i+1,:] ) # 翌日の最大値
    if tomorr_i != dp_ko[i][1]: # 翌日最大値のindex not 当日の保存していたindex(当日の最大値とは限らない)
        dp_ko[i+1] = dp_ko[i][0] + tomorr_ko , tomorr_i # 累積＋翌日の最大値 , 翌日のindex
    else:
        tomorr_no2 = np.sort( koufuku[i+1,:] )[-2] # 翌日2番目に大きい値
        tomorr_no2_i = koufuku[i+1,:].argsort()[-2] # 翌日2番目に大きい値のindex
        dp_ko[i+1] = dp_ko[i][0] + tomorr_no2 , tomorr_no2_i 

print(dp_ko[N-1][0])

### FIXED CODE ###

"""
参考 Xenous
if sortを少なくし、maxで処理
""" 
# 初期入力
N = int(input())
a=[]
b=[]
c=[]
for i in range(N):
    a1,b1,c1 = (int(x) for x in input().split())
    
    a.append(a1)
    b.append(b1)
    c.append(c1)

dp_A = [0]*(N) ;dp_A[0] =a[0] 
dp_B = [0]*(N) ;dp_B[0] =b[0] 
dp_C = [0]*(N) ;dp_C[0] =c[0] 


#
for i in range(0,N-1):
    dp_A[i+1] = max(dp_B[i] + a[i+1] , dp_C[i] + a[i+1])
    dp_B[i+1] = max(dp_A[i] + b[i+1] , dp_C[i] + b[i+1])
    dp_C[i+1] = max(dp_A[i] + c[i+1] , dp_B[i] + c[i+1])
print(max (dp_A[N-1],dp_B[N-1],dp_C[N-1]) )
# input
N = int(input())
L = [int(x) for x in list(str(N))]
ans = 0

if L[0] + L[1] + L[2] + L[3] == 7:
    print("%d+%d+%d+%d=7" % (L[0], L[1], L[2], L[3]))
else:
    if L[0] - L[1] + L[2] + L[3] == 7:
        print("%d-%d+%d+%d=7" % (L[0], L[1], L[2], L[3]))
    else:
        if L[0] + L[1] - L[2] + L[3] == 7:
            print("%d+%d-%d+%d=7" % (L[0], L[1], L[2], L[3]))
        else:
            if L[0] + L[1] + L[2] - L[3] == 7:
                print("%d+%d+%d-%d=7" % (L[0], L[1], L[2], L[3]))
            else:
                if L[0] - L[1] - L[2] + L[3] == 7:
                    print("%d-%d-%d+%d=7" % (L[0], L[1], L[2], L[3]))
                else:
                    if L[0] - L[1] + L[2] - L[3] == 7:
                        print("%d-%d+%d-%d=7" % (L[0], L[1], L[2], L[3]))
                    else:
                        if L[0] + L[1] - L[2] - L[3] == 7:
                            print("%d+%d-%d-%d=7" % (L[0], L[1], L[2], L[3]))
                        else:
                            if L[0] - L[1] - L[2] - L[3] == 7:
                                print("%d-%d-%d-%d=7" % (L[0], L[1], L[2], L[3]))



### FIXED CODE ###

# input
L = [int(x) for x in list(input())]
ans = 0

if L[0] + L[1] + L[2] + L[3] == 7:
    print("%d+%d+%d+%d=7" % (L[0], L[1], L[2], L[3]))
else:
    if L[0] - L[1] + L[2] + L[3] == 7:
        print("%d-%d+%d+%d=7" % (L[0], L[1], L[2], L[3]))
    else:
        if L[0] + L[1] - L[2] + L[3] == 7:
            print("%d+%d-%d+%d=7" % (L[0], L[1], L[2], L[3]))
        else:
            if L[0] + L[1] + L[2] - L[3] == 7:
                print("%d+%d+%d-%d=7" % (L[0], L[1], L[2], L[3]))
            else:
                if L[0] - L[1] - L[2] + L[3] == 7:
                    print("%d-%d-%d+%d=7" % (L[0], L[1], L[2], L[3]))
                else:
                    if L[0] - L[1] + L[2] - L[3] == 7:
                        print("%d-%d+%d-%d=7" % (L[0], L[1], L[2], L[3]))
                    else:
                        if L[0] + L[1] - L[2] - L[3] == 7:
                            print("%d+%d-%d-%d=7" % (L[0], L[1], L[2], L[3]))
                        else:
                            if L[0] - L[1] - L[2] - L[3] == 7:
                                print("%d-%d-%d-%d=7" % (L[0], L[1], L[2], L[3]))
N, M = map(int, input().split())
ana = []
for _ in range(M):
  ana.append(input())
ans = [0] * N
ans[0] = 1# 一段目まで登る方法は一通り
ans[1] = 2# 二段目まで登る方法は二通り
 
for i in range(2,N):
    tmp = i+1
    tmp2 = str(tmp)
    if tmp2 in ana:
        ans[i] = 0
    else:
        ans[i] = (ans[i-1] + ans[i-2]) % 1000000007
 
print(ans[N-1])

### FIXED CODE ###

import sys
N, M = map(int, input().split())
if N == 1:
    print(1)
    sys.exit()
ana = [0] * M
ans = [0] * N
mod = 10 ** 9 + 7
if M != 0:
    for i in range(M):
      ans[int(input())-1] = -1
if ans[0] == -1 and ans[1] == -1:
    print(0)
    sys.exit()
elif ans[0] == -1:
    ans[0] = 0
    ans[1] = 1
elif ans[1] == -1:
    ans[0] = 1
    ans[1] = 0
else:
    ans[0] = 1
    ans[1] = 2

if N != 2:
    for i in range(2,N):
        if ans[i] == -1:
            ans[i] = 0
        else:
            ans[i] = (ans[i-1]  + ans[i-2]) % mod
print(ans[N-1])
n, x = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
count = 0

for i in a:
    if x >= a[min]:
        x -= i
        count += 1
    else:
        pass
        
print(count)

### FIXED CODE ###

N, x = map(int, input().split())
a = sorted(map(int, input().split()))
cnt = 0
for i in a:
    if x < i:
        break
    cnt += 1
    x -= i
else:
    if x > 0:
        cnt -= 1
print(cnt)
n = int(input())                                                                                                                                                             
d = list(map(int,input().split()))

sorted_d = sorted(d)
half = n/2 

sorted_d[half] = a 
sorted_d[half+1] = b 

print(b-a)

### FIXED CODE ###

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

sorted_d = sorted(d)
half = n//2

a = sorted_d[half-1]
b = sorted_d[half]

print(b-a)
N = int(input())
S = [input() for i in range(N) if input() not in S]
  
print(len(S))


### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
  S.append(input())

print(len(set(S)))
S = input()
N = len(S)
S = list(S.split("T"))
x, y = map(int, input().split())

X_command = sorted([len(i) for i in S[::2]], reverse=True)
Y_command = sorted([len(i) for i in S[1::2]], reverse=True)

dp_x = [[False] * (sum(X_command)+1) for i in range(len(X_command))]
dp_y = [[False] * (sum(Y_command)+1) for i in range(len(Y_command))]

if X_command:
    dp_x[0][X_command[0]] = True
    for i in range(1, len(X_command)):
        for xi in range(sum(X_command)):
            if xi + X_command[i] >= N-1:
                continue
            if xi-X_command[i] >= 0:
                dp_x[i][xi] = dp_x[i-1][xi-X_command[i]] or dp_x[i-1][xi+X_command[i]]
            else:
                dp_x[i][xi] = dp_x[i-1][xi+X_command[i]]

if Y_command:
    dp_y[0][Y_command[0]] = True
    for i in range(1, len(Y_command)):
        for yi in range(sum(Y_command)):
            if yi + Y_command[i] >= N-1:
                continue
            if yi-Y_command[i] >= 0:
                dp_y[i][yi] = dp_y[i-1][yi-Y_command[i]] or dp_y[i-1][yi+Y_command[i]]
            else:
                dp_y[i][yi] = dp_y[i-1][yi+Y_command[i]]


x, y = max(x, -x), max(y, -y)

if sum(X_command) < x or sum(Y_command) < y:
    print("No")
    exit()
if dp_x[len(X_command)-1][x] and dp_y[len(Y_command)-1][y]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

S = input()
N = len(S)
S = list(S.split("T"))
x, y = map(int, input().split())

X_command = sorted([len(i) for i in S[::2]], reverse=True)
Y_command = sorted([len(i) for i in S[1::2]], reverse=True)

nx = X_command.pop(-1)
ny = 0

for xi in X_command:
    if nx > x:
        nx -= xi
    else:
        nx += xi

for yi in Y_command:
    if ny > y:
        ny -= yi
    else:
        ny += yi

if nx == x and ny == y:
    print("Yes")
else:
    print("No")
s = input()
t = len(s)
if s[:t//2]==s[s//2]:
  print('Yes')
else: print('No')


### FIXED CODE ###


t = int(input())
s = input()
if s[:t//2]==s[t//2:]:
  print('Yes')
else: print('No')
N = int(input())
H_LIST = input().split(" ")
H = []

for i in H_LIST:
    H.append(int(i))
   
count = 0
max_count = 0
for i in range(0, N):
    if H[i] >= H[i + 1]:
        count += 1
    else:
        max_count = count #メモリの動き
        count = 0

print(max_count)

### FIXED CODE ###

N = int(input())
H_LIST = input().split(" ")
H = []

for i in H_LIST:
    H.append(int(i))
   
count = 0
max_count = 0
for i in range(0, N-1):
    if H[i] >= H[i + 1]:
        count += 1
    else:
        count = 0 #メモリの動き
        
    if max_count < count:
        max_count = count


print(max_count)
inp = raw_input()

c = set([i for i in c])
if len(c) == 3:
    print "Yes"
else:
    print "No"

### FIXED CODE ###

inp = raw_input()

c = set([i for i in inp])
if len(c) == 3:
    print "Yes"
else:
    print "No"
n, k = map(int, input().split())
s = input()
res = []

if s[0] == "0":
    res.append(0)

res.append(1)

for i in range(1, n):
    if s[i] == s[i - 1]:
        res[-1] += 1
    else:
        res.append(1)

if s[-1] == "0":
    res.append(0)

l = len(res)
su = [0] * (l + 1)
for i in range(l):
    su[i + 1] = su[i] + res[i]

mil = min(l, 2 * k + 1)

ans = 1
for i in range(0, l - mil + 1, 2):
    ans = max(ans, su[2 * k + 1 + i] - su[i])
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
s = input()
res = []

if s[0] == "0":
    res.append(0)
res.append(1)
for i in range(1, n):
    if s[i] == s[i - 1]:
        res[-1] += 1
    else:
        res.append(1)
if s[-1] == "0":
    res.append(0)

l = len(res)
su = [0] * (l + 1)
for i in range(l):
    su[i + 1] = su[i] + res[i]

mil = min(l, 2 * k + 1)

ans = 1
for i in range(0, l - mil + 1, 2):
    ans = max(ans, su[mil + i] - su[i])
print(ans)
a=int(input())
if a>=10:
    print(-1)
else:
    b=int(input())
    if b>=10:
        print(-1)
    else:
        print(a*b)


### FIXED CODE ###

a,b=map(int,input().split())
if(a>=10):
    print(-1)
elif(b>=10):
    print(-1)
else:
    print(a*b)
import math
A, B, H, M = float(open(0))

K = abs(math.pi*M/30 - math.pi*H/6)

print(math.sqrt(A**2+B**2 - 2*A*B*math.cos(K)))

### FIXED CODE ###

import math
A, B, H, M = map(int, input().split())


arg_b = math.pi * float(M) / 30
arg_a = (math.pi / 6) * (float(H) + float(M)/60) 
K = abs(arg_b - arg_a)
C = math.sqrt(A*A+B*B - 2*A*B*math.cos(K))
print(C)
S = list(input())
for n in S:
  if N == '1':
  	N = '9'
  elif N == '9':
    N = '1'
A = int(''.join(S))
print(A)

### FIXED CODE ###

S = list(input())
for i in range(3):
  if S[i] == '1':
  	S[i] = '9'
  elif S[i]== '9':
    S[i] = '1'
A = int(''.join(S))
print(A)
N, M = map(int, input().split())
broken_lst = []
for _ in range(M):
    broken_lst.append(int(input()))

counter_arr = [0]*(N+1)

counter_arr[0] = 1
next_broken = broken_lst.pop(0)
last_broken = -1

for i in range(0, N-1):
    flug = 0
    if i+1 == next_broken:
        flug = 1
#        print("p0", i, counter_arr)
    elif i+1 == last_broken:
        pass
#        print("p1",i, counter_arr)
    else:
        counter_arr[i+1] += counter_arr[i]
        counter_arr[i+1] %= 10**9 + 7
#        print("p2",i,  counter_arr)

    if i + 2 == next_broken:
        flug = 1
#        print("p3",i, counter_arr)
    else:
        counter_arr[i+2] += counter_arr[i]
        counter_arr[i+2] %= 10**9 + 7
#        print("p4",i, counter_arr)
    
    if flug == 1:
        last_broken = next_broken
        if len(broken_lst) != 0:
            next_broken = broken_lst.pop(0)

    
counter_arr[-1] += counter_arr[-2]
counter_arr[-1] %= 10**9 + 7

print(counter_arr[-1])

### FIXED CODE ###

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

counter_arr = [0]*(N+1)

counter_arr[0] = 1
next_broken = -1
if len(broken_lst) != 0:
    next_broken = broken_lst.pop(0)
last_broken = -1

for i in range(0, N-1):
    flug = 0
    if i+1 == next_broken:
        flug = 1
#        print("p0", i, counter_arr)
    elif i+1 == last_broken:
        pass
#        print("p1",i, counter_arr)
    else:
        counter_arr[i+1] += counter_arr[i]
        counter_arr[i+1] %= 10**9 + 7
#        print("p2",i,  counter_arr)

    if i + 2 == next_broken:
        flug = 1
#        print("p3",i, counter_arr)
    else:
        if i == 0 and len(broken_lst) != 0:
            if broken_lst[0] == 2 and next_broken == 1:
                continue
        counter_arr[i+2] += counter_arr[i]
        counter_arr[i+2] %= 10**9 + 7
#        print("p4",i, counter_arr)
    
    if flug == 1:
        last_broken = next_broken
        if len(broken_lst) != 0:
            next_broken = broken_lst.pop(0)

if last_broken != N - 1:
    counter_arr[-1] += counter_arr[-2]
counter_arr[-1] %= 10**9 + 7

print(counter_arr[-1])
from math import ceil
a, b = map(int, input())
print(ceil((a+b)/2))

### FIXED CODE ###

from math import ceil
a, b = map(int, input().split())
print(ceil((a+b)/2))
def binaryinsertion(A,x):
    left=0;right=len(A)-1;centre = len(A)//2
    while(True):
        if(left == right):
            if(x[0]<A[left][0]):
                A.insert(left,x)
                break
            else :
                A.insert(left+1,x)
                break
        else:
            if(x[0] < A[centre][0]) :
                right = centre - 1
            elif(A[centre][0] < x[0]) :
                left = centre + 1
            else : 
                A.insert(centre,x)
                break
            centre = left + (right-left + 1)//2

[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
sweep = A[:L]
sweep = sorted(sweep)
ans = [str(sweep[0][0])]
for i in range(L,N) :
    sweep.remove(A[i-L])
    binaryinsertion(sweep,A[i])
    ans.append(str(sweep[0][0]))
print(" ".join(ans))

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
c, a, b = map(int, input(),split())
print(int(c * a / 2))


### FIXED CODE ###

c, a, b = map(int, input().split())
print(int(c * a / 2))
def calc(x):
    if x not in dp:
        divs = [5, 3, 2]
        costs = [c, b, a]
        values = lambda div, cost: [calc(x // div) + cost + x % div * d, calc((x + div - 1) // div) + cost + (-x) % div * d]
        dp[x] = min(x * d, *[value for div, cost in zip(divs, costs) for value in values(div, cost)])
    return dp[x]

for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    dp = {0: 0, 1: d}
    print(calc(n))


### FIXED CODE ###

t = int(input())

import sys
sys.setrecursionlimit(10 ** 6)

def calc(x):
    if x in dp:
        return dp[x]
    
    divs = [5, 3, 2]
    costs = [c, b, a]
    res = d * x
    for div, cost in zip(divs, costs):
        dived = x//div
        res = min(res, calc(dived) + cost + abs(x-dived*div) * d)
        if x > div:
            dived = x//div+1
            res = min(res, calc(dived) + cost + abs(x-dived*div) * d)
    dp[x] = res
    return res

for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    dp = {}
    dp[0] = 0
    dp[1] = d
    print(calc(n))
n,k=map(int,input().split())
s=list(input())
l,tmpl,cnt0,tmp,flag=[],0,0,s[0],0
if tmp=="0":cnt0+=1;flag=1
for i in s:
    if i==tmp:tmpl+=1
    else:
        if i=="0":cnt0+=1
        tmp=i
        l.append(tmpl)
        tmpl=1
l.append(tmpl)
if cnt0<=k:print(n);exit()
ans=max(sum(l[:2*k]),sum(l[::-1][:2*k]))
suml,tmp=[0],0
if flag==1:l=l[1:]
for i in l:
    tmp+=i
    suml.append(tmp)
for i in range((len(suml)-2*k-1)//2+1):
    tmp=suml[2*k+2*i+1]-suml[2*i]
    if tmp>ans:ans=tmp
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
s=list(input())
l,tmpl,cnt0,tmp,flag1,flag2=[],0,0,s[0],0,0
if tmp=="0":cnt0+=1;flag1=1
for i in s:
    if i==tmp:tmpl+=1
    else:
        if i=="0":cnt0+=1
        tmp=i
        l.append(tmpl)
        tmpl=1
if tmp=="0":flag2=1
l.append(tmpl)
if cnt0<=k:print(n);exit()
ans=max(sum(l[:2*k]),sum(l[::-1][:2*k]))
suml,tmp=[0],0
if flag1==1:l=l[1:]
if flag2==1:l=l[:len(l)-1]
for i in l:
    tmp+=i
    suml.append(tmp)
for i in range((len(suml)-2*k-1)//2+1):
    tmp=suml[2*k+2*i+1]-suml[2*i]
    if tmp>ans:ans=tmp
print(ans)