Harryxun/stf_run huggingface dataset:
'''Author- Akshit Monga'''
n=int(input())
x=input()
x=x[::-1]
ans1=0
ans2=0
c=x.count('1')
for i in range(0,n):
    if x[i]:
        ans1=(ans1+pow(2,i,c+1))%(c+1)
        ans2=(ans2+pow(2,i,c-1))%(c-1)
to_print=[]
for i in range(0,n):
    if x[i]=='1':
        if c==1:
            to_print.append(0)
            continue
        var=(ans2%(c-1)-pow(2,i,c-1))%(c-1)
        a = 1
        while var:
            var = var % bin(var).count('1')
            a += 1
        to_print.append(a)
    else:
        # print(ans1)
        var = (ans1%(c+1) + pow(2, i, c +1))%(c+1)
        # print(c+1)
        # print(var)
        a = 1
        while var:
            var = var % bin(var).count('1')
            a += 1
        to_print.append(a)
for i in to_print[::-1]:
    print(i)

### FIXED CODE ###

'''Author- Akshit Monga'''
n=int(input())
x=input()
x=x[::-1]
ans1=0
ans2=0
c=x.count('1')
for i in range(0,n):
    if x[i]=='1':
        ans1=(ans1+pow(2,i,c+1))%(c+1)
        if c!=1:
            ans2=(ans2+pow(2,i,c-1))%(c-1)
to_print=[]
for i in range(0,n):
    if x[i]=='1':
        if c==1:
            to_print.append(0)
            continue
        var=(ans2%(c-1)-pow(2,i,c-1))%(c-1)
        a = 1
        while var:
            var = var % bin(var).count('1')
            a += 1
        to_print.append(a)
    else:
        # print(ans1)
        var = (ans1%(c+1) + pow(2, i, c +1))%(c+1)
        # print(c+1)
        # print(var)
        a = 1
        while var:
            var = var % bin(var).count('1')
            a += 1
        to_print.append(a)
for i in to_print[::-1]:
    print(i)
import numpy as np
import copy

N = int(input())
A = [int(i) for i in input().split()]
A = list(set(A))

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

if N<=2:
    print(max(A))
else:
    gcdss = []
    for i,a in enumerate(A):
        A_temp = copy.deepcopy(A)
        A_temp.pop(i)
        gcds = []
        for i in range(len(A_temp)-1):
            gcd_temp = gcd(A_temp[i],A_temp[i+1])
            gcds.append(gcd_temp)
            if gcd_temp == 1:
                break
        gcdss.append(min(gcds))
    print(max(gcdss))

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a  
lgcds = [A[0]]
rgcds = [A[N-1]]
for n in range(N-2):
    lgcds.append(gcd(lgcds[-1],A[n+1]))
    rgcds.append(gcd(rgcds[-1],A[-2-n]))
gcds = [lgcds[-1],rgcds[-1]]
for i in range(N-2):
    gcds.append(gcd(lgcds[i],rgcds[-2-i]))
print(max(gcds))
a=map(int,input().split())
print(max([2*a[0]-1,2*a[1]-1,a[0]+a[1]]))

### FIXED CODE ###

a=list(map(int,input().split()))
print(max([2*a[0]-1,2*a[1]-1,a[0]+a[1]]))
L, N = map(int,input().split())
S = [input() for i in range(N)]

S.sort()

A=''.join(S)

print(A)

### FIXED CODE ###

N, L = map(int,input().split())
S = [input() for i in range(N)]

S.sort()


print("".join(S))
import math

end = 0

n = input().split(" ")
ato = n[0]

for i in range(int(ato)):   #すべて変数に入れる
    x = input().split(" ")
    exec("intX%d = %d" % (i,int(x[0])))
    exec("intY%d = %d" % (i,int(x[1])))

for i in range(int(ato)):
    answer = math.sqrt(pow(eval("intX" + str(i),2)) + pow(eval("intY" + str(i))))
    if answer <= n[1]:
        end = end + 1

print(end)

### FIXED CODE ###

from math import sqrt
 
n, d = map(int, input().split())
xy = [list(map(int, input().split()))for _ in range(n)]
 
ans = 0
for x, y in xy:
    s = sqrt(x ** 2 + y ** 2)
    if s <= d:
        ans += 1
print(ans)
print(a*b if (a<10 and b<10) else -1)

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b if (a<10 and b<10) else -1)
from collections import deque
import numpy as np
N,M = map(int,input().split(' '))
#G = {i:[] for i in range(1,N+1)}

GM = np.zeros((N,N)).astype(np.int)

for j in [0]*M:
	u,v = map(int,input().split(' '))
	GM[u-1,v-1] = 1
	#G[u].append(v)
S,T = map(int,input().split(' '))

GM = np.dot(np.dot(GM,GM),GM)

G3 = {i: list(np.where(GM[i-1]==1)[0]+1) for i in range(1,N+1)}

#dq =deque([S])
st = [S]
visited = [S]
ans = 1
exist = True
while(exist):
	new_st = []
	exist = False
	for cand in st:
		for n in G3[cand]:
			if n == T:
				print(ans)
				exit()
			if not n in visited:
				exist = True
				visited.append(n)
				new_st.append(n)
	st = new_st
	ans += 1
print(-1)









### FIXED CODE ###

import sys
from collections import defaultdict, deque
input = sys.stdin.readline
N,M= map(int,input().split())
g = defaultdict(list)

for i in range(M):
    u,v = list(map(int,input().split()))
    g[u].append(N + v)
    g[N + u].append(2*N + v)
    g[2*N + u].append(v)
S,T= map(int,input().split())

dq = deque([S])
inf = 10**15
d = [inf for i in range(3*N+1)]
d[S] = 0

while dq:
    v = dq.popleft()
    for nv in g[v]:
        if d[nv] > d[v] + 1:
            d[nv] = d[v] + 1
            dq.append(nv)

if inf == d[T]:
    print(-1)
else:
    print(d[T]//3)
import numpy as np
N = int(input())
A = tuple(map(int,input().split()))

R = N
L = np.zeros((N,N), dtype='bool')
L[0,:] = 1
for i in range(1,N):
    t = 0
    L[i,:] = np.array( [L[i-1][j] and L[i-1][j+1] and A[j]^A[i+j] == A[j]+A[i+j] for j in range(N-i)] + [False]*(i) )
    t = L[i].sum()
    R += t
    if t == 0:
        break
print(R)

### FIXED CODE ###

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

result = 0
Right = 0
tmp = 0
for left in range(N):
    for right in range(Right,N):
        if not (tmp & A[right]):
            tmp += A[right]
            Right = right + 1
        else:
            break
    tmp -= A[left]
    result += Right - left
print(result)
a = int(input())
b = int(input())
c = a*b
if (c%2) == 0:
    print("Even")
else:
    print("Odd")


### FIXED CODE ###

a, b = map(int, input().split())
if ((a*b) % 2) == 0:
    print("Even")
else:
    print("Odd")
import math

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

# 足場iに到るコスト
dp = [math.inf] * n
dp[0] = 0

for i in range(1, n):
    for j in range(1, k + 1):
        if i < j:
            continue
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

print(dp[-1])


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


n, k = map(int, input().split())
H = list(map(int, input().split()))

INF = 10 ** 9
dp = [INF] * n
dp[0] = 0
for i in range(n - 1):
    for j in range(1, k + 1):
        if j >= n - i:
            break
        dp[i + j] = min(dp[i + j], dp[i] + abs(H[i + j] - H[i]))
print(dp[-1])
h = int(input())
def Count(a):
  if a==1:
    return 1
  return 1+2*count(a//2)
print(Count(a))

### FIXED CODE ###

h = int(input())
def Count(a):
  if a==1:
    return 1
  return 1+2*Count(a//2)
print(Count(h))
#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print(calc(H))



if __name__ == "__main__":
    resolve()



### FIXED CODE ###

#!python3
import sys
sys.setrecursionlimit(1000000)

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print(calc(H))



if __name__ == "__main__":
    resolve()
H,W = map(int,input().split())
Grid = [[1 if g == "." else 0 for g in input()] for _ in range(H)]
dp = [[10**5]*(W) for _ in range(H)]
dp[0][0] = 0
black = 0
flag = Grid[H-1][W-1]

for g in Grid:
    for gg in g:
        if not(gg):
            black += 1

a = [-1,1]
def bfs(grid,h,w,Q):
    if h == H - 1 and w == W - 1:
        return dp[h][w]
    for aa in a:
        if 0 <= h + aa <= H -1:
            if grid[h+aa][w]:
                grid[h+aa][w] = 0
                dp[h+aa][w] = dp[h][w] + 1
                Q.append([h+aa,w])
        if 0 <= w + aa <= W - 1:
            if grid[h][w+aa]:
                grid[h][w+aa] = 0
                dp[h][w+aa] = dp[h][w] + 1
                Q.append([h,w + aa])
    if len(Q) == 0:
        return -1
    else:
        nexth,nextw = Q.pop(0)
        return bfs(grid,nexth,nextw,Q)
queue = []
if Grid[0][0] and flag:
    ans = bfs(Grid,0,0,queue)
    if ans == -1:
        print(-1)
    else:
        print(H*W - ans - 1 - black)
else:
    print(-1)


### FIXED CODE ###

H,W = map(int,input().split())
Grid = [[1 if g == "." else 0 for g in input()] for _ in range(H)]
dp = [[10**5]*(W) for _ in range(H)]
dp[0][0] = 0
black = 0
flag = Grid[0][0]

for g in Grid:
    for gg in g:
        if not(gg):
            black += 1

a = [-1,1]

import sys
sys.setrecursionlimit(10**4)
def bfs(grid,h,w,Q):
    if h == H - 1 and w == W - 1:
        return dp[h][w]
    for aa in a:
        if 0 <= h + aa <= H -1:
            if grid[h+aa][w]:
                grid[h+aa][w] = 0
                dp[h+aa][w] = dp[h][w] + 1
                Q.append([h+aa,w])
        if 0 <= w + aa <= W - 1:
            if grid[h][w+aa]:
                grid[h][w+aa] = 0
                dp[h][w+aa] = dp[h][w] + 1
                Q.append([h,w + aa])
    if len(Q) == 0:
        return -1
    else:
        nexth,nextw = Q.pop(0)
        return bfs(grid,nexth,nextw,Q)
queue = []
Grid[0][0] = 0
if  flag:
    ans = bfs(Grid,0,0,queue)
    if ans == -1:
        print(-1)
    else:
        print(H*W - ans - 1 - black)
else:
    print(-1)
N = int(input())
A = list(map(int, input().split()))
A.sort()
if N % 2 == 0:
    for i in range(0,N//2+1,2):
        if A[i] == A[i+1]:
            continue
        else:
            print(0)
            exit(0)
else:
    for i in range(1,N//2+2,2):
        if A[i] == A[i+1]:
            continue
        else:
            print(0)
            exit(0)
print(2**(N//2)%(10**9+7))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
if N == 1:
    print(1)
    exit(0)

elif N % 2 == 0:
    for i in range(0,N//2+1,2):
        if A[i] == A[i+1]:
            continue
        else:
            print(0)
            exit(0)
else:
    for i in range(1,N//2+2,2):
        if A[i] == A[i+1]:
            continue
        else:
            print(0)
            exit(0)
print(2**(N//2)%(10**9+7))
# -*- coding: utf-8 -*-
# 整数の入力
import math
import numpy as np

if __name__ == "__main__":
    N = int(input())
    A = []
    B = []
    for i in range(N):
        t = list(map(int, input().split()))
        A.append(t[0])
        B.append(t[1])
    A.sort()
    B.sort()

    a = 0
    if N % 2 == 0:
        i = N // 2
        j = N // 2 - 1
        a = AB[j][0] + AB[i][0]
        b = AB[j][1] + AB[i][1]
        print(b - a + 1)
    else:
        i = N // 2
        a = AB[i][1] - AB[i][0] + 1

        print(a)
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
import math
import numpy as np

N = int(input())
A = []
B = []
for i in range(N):
    t = list(map(int, input().split()))
    A.append(t[0])
    B.append(t[1])
A.sort()
B.sort()

if N % 2 == 0:
    i = N // 2
    j = N // 2 - 1
    a = A[j] + A[i]
    b = B[j] + B[i]
    print(b - a + 1)
else:
    i = N // 2
    a = B[i] - A[i] + 1

    print(a)
A,B = map(int , input().split())

if (A<=8) and (B<=8):
  print('Yay!')
else:
  pront(':(')

### FIXED CODE ###

a,b = map(int,input().split())
if (a <= 8) and (b <= 8):
    print('Yay!')
else:
    print(':(')
n = int(input())
    s = []
    for i in range(n):
      s.append(input())
     
    ab = 0
    ab_ = 0
    a = 0
    b = 0
    for i in s:
      ab += i.count("AB")
      if i[0] == "B" and i[-1] == "A":
        ab_ += 1
      if i[0] == "B":
        b += 1
      if i[-1] == "A":
        a += 1
    if ab_ == a and ab_ == b and not ab_ == 0:
      print(ab+ab_-1)
    else:
      print(ab+min([a,b]))

### FIXED CODE ###

n = int(input())
s = []
for i in range(n):
  s.append(input())
     
ab = 0
ab_ = 0
a = 0
b = 0
for i in s:
  ab += i.count("AB")
  if i[0] == "B" and i[-1] == "A":
    ab_ += 1
  if i[0] == "B":
    b += 1
  if i[-1] == "A":
    a += 1
if ab_ == a and ab_ == b and not ab_ == 0:
  print(ab+ab_-1)
else:
  print(ab+min([a,b]))
n=int(input())
list=[int(input()) for x in range(n)]
a=0
def m(list,k):
  t=max(list[:k])
  return t
for j in range(n):
  if m(list,j)<=list[j]:
    a=a+1
  else:
    pass
print(a)

### FIXED CODE ###

n=int(input())
list=list(map(int,input().split()))
a=1
for j in range(n-1):
  if max(list[:j+1])<=list[j+1]:
    a=a+1
  else:
    pass
print(a)
import sys
ab = sys.stdin.readline().split(' ')
print(max(ab[0]*int(ab[1]), ab[1]*int(ab[0]))

### FIXED CODE ###

ab = input().split(' ')
print(min(ab[0]*int(ab[1]), ab[1]*int(ab[0])))
n,k,s=map(int,input().split())
ans=[]
if s==10**9:
    ans=[s]*k+[1]*[n-k]
else:
    ans=[s]*k+[s+1]*(n-k)
print(*ans)

### FIXED CODE ###

n,k,s=map(int,input().split())
ans=[]
if s==10**9:
    ans=[s]*k+[1]*(n-k)
else:
    ans=[s]*k+[s+1]*(n-k)
print(*ans)
a,b= int(input( )).split()
if (a*b)%2=0:
  print("Even")
else :
  print("Odd")


### FIXED CODE ###

a,b= map(int, (input()).split())
if (a*b)%2==0:
  print("Even")
else :
  print("Odd")
N = input()
N = int(S)
A = N / 2
B = (N + 1) / 2
if N % 2 == 0:
  print(A)
else:
  print(B)


### FIXED CODE ###

N = int(input())
A = N / 2
A = int(A)
B = (N + 1) / 2
B = int(B)
if N % 2 == 0:
  print(A)
else:
  print(B)
"""
E.
"""
from functools import reduce
from collections import deque


def prod(x, y):
    return x * y % MOD

    
N, K = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
# abs_a_list = sorted(a_list, key=abs, reverse=True)
MOD = 10**9 + 7

if K%2 == 1:
    flg = True
    for a in a_list:
        if a >= 0:
            flg = False
            break
    if flg:
        print(reduce(prod, a_list[:K]))
        exit()

S = []
i = 0
a_list = deque(a_list)
while i < K:
    if a_list[0]*a_list[1] > a_list[-1]*a_list[-2]:
        S.append(a_list.popleft())
        i += 1
    elif a_list[0]*a_list[1] <= a_list[-1]*a_list[-2] and i <= K-2:
        S.append(a_list.pop())
        S.append(a_list.pop())
        i += 2
    else:
        S.append(a_list.popleft())
        i += 1

ans = reduce(prod, S)
print(ans)

### FIXED CODE ###

"""
E.
"""
from functools import reduce
from collections import deque


def prod(x, y):
    return x * y % MOD

    
N, K = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
# abs_a_list = sorted(a_list, key=abs, reverse=True)
MOD = 10**9 + 7

if K%2 == 1:
    flg = True
    for a in a_list:
        if a >= 0:
            flg = False
            break
    if flg:
        print(reduce(prod, a_list[:K]))
        exit()

S = []
a_list = deque(a_list)
i = 0
while i < K:
    if len(a_list)>=2:
        if a_list[0]*a_list[1] > a_list[-1]*a_list[-2]:
            S.append(a_list.popleft())
            i += 1
        elif a_list[0]*a_list[1] <= a_list[-1]*a_list[-2] and i <= K-2:
            S.append(a_list.pop())
            S.append(a_list.pop())
            i += 2
        else:
            S.append(a_list.popleft())
            i += 1
    else:
        S.append(a_list.popleft())
        i += 1
        
ans = reduce(prod, S)
print(ans)
n = int(input())
print(n)


### FIXED CODE ###

n = str(input())
if n == "Sunny":
  print("Cloudy")
elif n== "Cloudy":
  print("Rainy")
else:
  print("Sunny")
import sys
input = sys.stdin.readline

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

from collections import Counter

CA=Counter(A)
CB=Counter(B)

H=[]

for ca in CA:
    if CA[ca]>0 and CB[ca]>0:
        if CA[ca]+CB[ca]>N:
            print("No")
            sys.exit()
        H.append((-(CA[ca]+CB[ca]),ca))

import heapq
heapq.heapify(H)

ANSDICT=dict()

while len(H)>=2:
    c1,x1=heapq.heappop(H)
    c1=-c1

    c2,x2=heapq.heappop(H)
    c2=-c2

    if x1 in ANSDICT:
        ANSDICT[x1].append(x2)
    else:
        ANSDICT[x1]=[x2]

    if x2 in ANSDICT:
        ANSDICT[x2].append(x1)
    else:
        ANSDICT[x2]=[x1]

    CA[x1]-=1
    CA[x2]-=1
    CB[x1]-=1
    CB[x2]-=1

    if CA[x1]>0 and CB[x1]>0:
        heapq.heappush(H,(-(c1-2),x1))

    if CA[x2]>0 and CB[x2]>0:
        heapq.heappush(H,(-(c2-2),x2))

ANS=[-1]*N

for i in range(N):
    a=A[i]
    if a in ANSDICT and len(ANSDICT[a])!=0:
        
        x=ANSDICT[a].pop()
        ANS[i]=x

if H:
    cc,xx=H[0]
    cc=-cc

for i in range(N):
    if ANS[i]==-1 and A[i]!=xx:
        ANS[i]=xx
        CA[xx]-=1
        CB[xx]-=1

        if CA[xx]==0 or CB[xx]==0:
            break

ind=0
for cb in CB:
    while CB[cb]!=0:
        while ANS[ind]!=-1:
            ind+=1
        ANS[ind]=cb
        CB[cb]-=1

print("Yes")
print(*ANS)
    
        
            
        





### FIXED CODE ###

import sys
input = sys.stdin.readline

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

from collections import Counter

CA=Counter(A)
CB=Counter(B)

H=[]

for ca in CA:
    if CA[ca]>0 and CB[ca]>0:
        if CA[ca]+CB[ca]>N:
            print("No")
            sys.exit()
        H.append((-(CA[ca]+CB[ca]),ca))

import heapq
heapq.heapify(H)

ANSDICT=dict()

while len(H)>=2:
    c1,x1=heapq.heappop(H)
    c1=-c1

    c2,x2=heapq.heappop(H)
    c2=-c2

    if x1 in ANSDICT:
        ANSDICT[x1].append(x2)
    else:
        ANSDICT[x1]=[x2]

    if x2 in ANSDICT:
        ANSDICT[x2].append(x1)
    else:
        ANSDICT[x2]=[x1]

    CA[x1]-=1
    CA[x2]-=1
    CB[x1]-=1
    CB[x2]-=1

    if CA[x1]>0 and CB[x1]>0:
        heapq.heappush(H,(-(c1-2),x1))

    if CA[x2]>0 and CB[x2]>0:
        heapq.heappush(H,(-(c2-2),x2))

ANS=[-1]*N

for i in range(N):
    a=A[i]
    if a in ANSDICT and len(ANSDICT[a])!=0:
        
        x=ANSDICT[a].pop()
        ANS[i]=x

if H:
    cc,xx=H[0]
    cc=-cc

    for i in range(N):
        if ANS[i]==-1 and A[i]!=xx:
            ANS[i]=xx
            CB[xx]-=1

            if CB[xx]==0:
                break

ind=0
for cb in CB:
    while CB[cb]!=0:
        while ANS[ind]!=-1:
            ind+=1
        ANS[ind]=cb
        CB[cb]-=1

print("Yes")
print(*ANS)
a, b = map(int, input().split())
if a * b mod 2 == 1:
  print('Odd')
else:
  print('Even')

### FIXED CODE ###

a, b = map(int, input().split())
if a * b % 2 == 1:
  print('Odd')
else:
  print('Even')
A=input().strip()
B=input().strip()
C=input().strip()
D=input().strip()
a=int(A)
b=int(B)
c=int(C)
d=int(D)

max=0
min=0

if a < c :
    max=c
else :
    max=a
    
if b > d :
    min=d
else :
    min=b
if ( min - max ) > 0 :
    print( min - max )
else :
    print(0)



### FIXED CODE ###



a,b,c,d=[int(i) for i in input().strip().split(' ')]

'''
入力は他の人のを見た
'''

max=0
min=0

if a < c :
    max=c
else :
    max=a
    
if b > d :
    min=d
else :
    min=b
if ( min - max ) > 0 :
    print( min - max )
else :
    print(0)
X, N = map(int, input().split())  
A = [int(x) for x in input().split()]

index = 0
value = abs(A[0] - X)
up_list = [0]*(N+1)
down_list = [0]*(N+1)

for i in range(N):
  if abs(A[i] - X ) < N+1:
    if A[i] - X >= 0:
      up_list[A[i]-X] = 1
    if A[i] - X <= 0:
      down_list[abs(A[i]- X)] = 1

j = 0
while True:
  if down_list[j] == 0:
    print(X-j)
    break
  if up_list[j] ==0:
    print(X+j)
    break
  if j>N+1:
    print('fail')
    break
  j+=1
  
    

### FIXED CODE ###

X, N = map(int, input().split())
if not N ==0:
  A = [int(x) for x in input().split()]
  index = 0
  value = abs(A[0] - X)
  up_list = [0]*(N+1)
  down_list = [0]*(N+1)

  for i in range(N):
    if abs(A[i] - X ) < N+1:
      if A[i] - X >= 0:
        up_list[A[i]-X] = 1
      if A[i] - X <= 0:
        down_list[abs(A[i]- X)] = 1

  j = 0
  while True:
    if down_list[j] == 0:
      print(X-j)
      break
    if up_list[j] ==0:
      print(X+j)
      break
    if j>N+1:
      print('fail')
      break
    j+=1

else:
  print(X)
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

# import math
# import numpy as np
# import copy
# from collections import defaultdict, Counter
# from itertools import product
# from bisect import bisect_left, bisect_right
def inpl(): return list(map(int, input().split()))

S = list(input())
N = len(S)
while True:
    flag = False
    for i in range(1, len(S)-2):
        l = S[i-1]
        mid = S[i:i+2]
        r = S[i+2]
        if mid == ["0", "1"] or mid == ["1", "0"]:
            if (l == "0" and r == "1") or (l == "1" and r == "0"):
                del S[i:i+2]
                i += 2
                flag = True
                if i >= len(S)-3:
                    break


    if flag:
        continue

    for i in range(0, len(S)-1):
        mid = S[i:i+2]
        if mid == ["0", "1"] or mid == ["1", "0"]:
            del S[i:i+2]
            if i >= len(S)-2:
                break

    break
print(N-len(S))

### FIXED CODE ###

# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

# import math
# import numpy as np
# import copy
# from collections import defaultdict, Counter
# from itertools import product
# from bisect import bisect_left, bisect_right
def inpl(): return list(map(int, input().split()))

S = input()
N = len(S)
c0 = S.count("0")
c1 = S.count("1")

print(2*min(c0, c1))
for i in range(1, 100):
    if a*i % b == c:
        print('YES')
        break
else:
    print('NO')

### FIXED CODE ###

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

for i in range(1, 100):
    if a*i % b == c:
        print('YES')
        break
else:
    print('NO')