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

n=int(input())
s=input()
w=list(map(int,list(s.replace('W','1').replace('E','0'))))
e=list(map(int,list(s.replace('E','1').replace('W','0'))))
ans=10**6
for i in range(n):
  mukihenko=sum(w[:i])+sum(e[i+1:])
  ans=min(mukihenko,ans)
print(ans)

### FIXED CODE ###

import collections
n=int(input())
s=list(input())
ans=10**6
tmp=collections.Counter(s[1:])['E']
ans=min(tmp,ans)
i=1
while i<n:
  if s[i-1]=='W':
    tmp+=1
  if s[i]=='E':
    tmp-=1
  ans=min(tmp,ans)
  i+=1

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

h,w,m = map(int,input().split())
hw = [list(map(int,input().split())) for _ in range(m)]

gh = {i:[] for i in range(h)}
gw = {i:[] for i in range(w)}

for _h, _w in hw:
    gh[_h-1].append(_w-1)
    gw[_w-1].append(_h-1)
    
ansh = 0
posh = {}
answ = 0
posw = {}
for k,v in gh.items():
    if len(v) >= ansh:
        ansh = len(v)
        
for k,v in gh.items():
    if len(v) == ansh:
        posh[k]=k
        
for k,v in gw.items():
    if len(v) >= answ:
        answ = len(v)
        
for k,v in gw.items():
    if len(v) == answ:
        posw[k]=k
        
hoge = True
for i in posh:
    for j in posw:
        if i not in gw[j]:
            hoge = False
            
if hoge:
    print(ansh+answ-1)
else:
    print(ansh+answ)

### FIXED CODE ###

h,w,m = map(int,input().split())
hw = [list(map(int,input().split())) for _ in range(m)]

hc = [0]*h
wc = [0]*w
d={}
for _h, _w in hw:
    hc[_h-1]+=1
    wc[_w-1]+=1
    d[(_h-1,_w-1)]=1
    
maxh = max(hc)
maxw = max(wc)
    
        
hoge = True
wi = [i for i in range(w) if wc[i]==maxw]
for h in [i for i in range(h) if hc[i]==maxh]:
    for w in wi:
        if (h,w) not in d:
            hoge=False
            break
            
if hoge:
    print(maxh+maxw-1)
else:
    print(maxh+maxw)
### BUGGY CODE ###

import sys
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
    def find(self,x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                self.table[s1] += -1
                self.table[s2] = s1
        return
n,k,l = map(int, sys.stdin.readline().split())
p = []
for i in range(k):
    p.append(list(map(int, input().split())))
do = [[] for i in range(n+1)]
for pi in p:  #0-originedに注意
    do[pi[0]].append(pi[1])
    do[pi[1]].append(pi[0])
p = []
for i in range(l):
    p.append(list(map(int, input().split())))
te = [[] for i in range(n+1)]
for pi in p:  #0-originedに注意
    te[pi[0]].append(pi[1])
    te[pi[1]].append(pi[0])
dou = UnionFind(n)
for i in range(n+1):
  a = do[i]
  for j in a:
    dou.union(i-1,j-1)
douro = [-1] * n
for i in range(n):
  douro[i] = dou.find(i)
tet = UnionFind(n)
for i in range(n+1):
  a = te[i]
  for j in a:
    tet.union(i-1,j-1)
tetu = [-1] * n
for i in range(n):
  tetu[i] = tet.find(i)
pair = [[0,0]for i in range(n)]
for i in range(n):
  pair[i] = (douro[i],tetu[i])
from collections import defaultdict
d = defaultdict(int)
for i in range(n):
  d[pair[i]] += 1
ans = []
for i in range(n):
  ans.append(d[pair[i]])
print(" ".join(map(str,ans)))

### FIXED CODE ###

import sys
from collections import defaultdict
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
    def find(self,x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                self.table[s1] += -1
                self.table[s2] = s1
        return
n,k,l = map(int, sys.stdin.readline().split())
p = []
for i in range(k):
    p.append(list(map(int, input().split())))
do = [[] for i in range(n+1)]
for pi in p:  #0-originedに注意
    do[pi[0]].append(pi[1])
p = []
for i in range(l):
    p.append(list(map(int, input().split())))
te = [[] for i in range(n+1)]
for pi in p:  #0-originedに注意
    te[pi[0]].append(pi[1])
dou = UnionFind(n)
for i in range(n+1):
  a = do[i]
  for j in a:
    dou.union(i-1,j-1)
douro = [-1] * n
for i in range(n):
  douro[i] = dou.find(i)
tet = UnionFind(n)
for i in range(n+1):
  a = te[i]
  for j in a:
    tet.union(i-1,j-1)
tetu = [-1] * n
for i in range(n):
  tetu[i] = tet.find(i)
d = defaultdict(int)
for i in range(n): 
  d[(douro[i],tetu[i])] += 1
ans = []
for i in range(n):
  ans.append(d[(douro[i],tetu[i])])
print(" ".join(map(str,ans)))
### BUGGY CODE ###

from functools import reduce


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


def lcm(a, b):
    return (a * b) // gcd(a, b)


def lcm_list(n):
    return reduce(lcm, n)


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

mod = 10 ** 9 + 7

L = lcm_list(a)
ans = 0
for i in a:
    ans = (ans + (L // i) % mod) % mod

print(ans % mod)

### FIXED CODE ###

import fractions
from functools import reduce


def lcm(a, b):
    return (a * b) // fractions.gcd(a, b)


def lcm_list(n):
    return reduce(lcm, n)


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

mod = 10 ** 9 + 7

L = lcm_list(a)
ans = 0
for i in a:
    ans += L // i

print(ans % mod)
### BUGGY CODE ###

import bisect
n, m = map(int, input().split())
a = list(map(int, input().split()))
l = len(a)
a.sort()

for i in range(m):
    x = a.pop(l-1)
    x = x / 2
    bisect.insort(a, x)



print(sum(map(int, a)))


### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))

heap = []
for i in a:
    heapq.heappush(heap, -i)


for i in range(m):
    x = - heapq.heappop(heap)
    x = x / 2
    heapq.heappush(heap, - x)



print(sum(map(lambda n: int (-n), heap)))
### BUGGY CODE ###

import math

def input_number():
    return int(input())

def input_1line_list(number_of_input):
    return [input() for i in range(number_of_input)]

def input_1line():
    return map(int, input().split())

# def print_unique_length(input_list):
#     print(len(set(input_list)))

def main():
    a, b, n = input_1line()
    ans = 0
    for i in range(n+1):
        ans = max(ans, math.floor(a*i/b) - a*math.floor(i/b))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import math

def input_number():
    return int(input())

def input_1line_list(number_of_input):
    return [input() for i in range(number_of_input)]

def input_1line():
    return map(int, input().split())

# def print_unique_length(input_list):
#     print(len(set(input_list)))

def f(a, b, x):
    return (a*(x%b))//b 

def main():
    a, b, n = input_1line()
    x = min(b-1, n)
    ans = f(a, b, x)
    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

K , S = map(int, input().split())
x = 0
y = 0
z = 0
sum = 0
cnt = 0
if K * 3 == S:
    cnt = 1
else :
    for i in range(K + 1):
        x = i
        if x + y + z == S :
    #        print(str(x) + str(y) + str(z))
            cnt += 1
        for j in range(K + 1):
            y = j
            if x + y + z == S :
    #            print(str(x) + str(y) + str(z))
                cnt += 1
            for k2 in range(K + 1) :
                z = k2
                if x + y + z == S:
    #                print(str(x) + str(y) + str(z))
                    cnt += 1

print(cnt)


### FIXED CODE ###

K , S = map(int, input().split())
x , y , z , cnt = 0 , 0 , 0 , 0
A = K + 1
if K * 3 == S:
    cnt = 1
else :
    for i in range(A):
        for j in range(A):
            if  S - (i + j) <= K :
                if 0 <= S - (i + j): 
                    cnt += 1
print(cnt)
### BUGGY CODE ###

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

p_list = []
y_list = []
shi_map = {}

for i in range(M):
    p, y = map(int, input().split())
    p_list.append(p)
    y_list.append(y)
    if p in shi_map:
        shi_map[p].append(y)
    else:
        shi_map[p] = [y]
shi_map2 = {}
for k, v in shi_map.items():
    v = sorted(v)
    shi_map2[k] = v

for i in range(M):
    p = p_list[i]
    y = y_list[i]
    j = shi_map2[p].index(y)
    p_str = str(p).zfill(6)
    j_str = str(j+1).zfill(6)
    print(p_str + j_str)



### FIXED CODE ###

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

shi_map = []

for i in range(M):
    p, y = map(int, input().split())
    shi_map.append([i, p, y])

shi_map = sorted(shi_map, key=lambda x: (x[1], x[2]))

result = {}
shi_count = {}
for i, p, y in shi_map:

    if p in shi_count:
        c = shi_count[p]
        count = c + 1
        shi_count[p] = count
    else:
        shi_count[p] = 1
        count = 1
    result[i] = [p, count]
result = list(sorted(result.items(), key=lambda x: x[0]))

for i, p in result:

    p2 = str(p[0]).zfill(6)

    y = str(p[1]).zfill(6)
    r = p2+y
    print(r)
### BUGGY CODE ###

n = int(input())
prod = 1
for i in range(1,n+1):
  prod *= i
print(int(prod%(10**9+7)))

### FIXED CODE ###

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


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n,w=n1()
WV=n3(n)

W=[0]
W.extend([x[0] for x in WV])
V=[0]
V.extend([x[1] for x in WV])

max_v=sum(V)
dp=[[0]+[float("inf")]*(max_v) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,max_v+1):
        if j-V[i]>=0:
            dp[i][j]=min(dp[i-1][j-V[i]]+W[i],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
#     print(dp[i])

for i in range(max_v+1):
    if dp[n][i]<=w:
        ans=i
print(ans)

### FIXED CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n,w=n1()
WV=n3(n)

W=[0]
W.extend([x[0] for x in WV])
V=[0]
V.extend([x[1] for x in WV])

max_v=sum(V)
dp=[[0]+[float("inf")]*(max_v) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,max_v+1):
        if j-V[i]>=0:
            dp[i][j]=min(dp[i-1][j-V[i]]+W[i],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
#     print(dp[i])

for i in range(max_v+1):
    if dp[n][i]<=w:
        ans=i
print(ans)
### BUGGY CODE ###

H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[10**8]*W for i in range(H)]
dy=[-1,1,0,0]
dx=[0,0,1,-1,]
ey=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ex=[0,1,2,-1,-2,1,2,-1,-2,2,-2,1,2,-1,-2,0,1,2,-1,-2]
for h in range(H):
  for w in range(W):
    if A[h][w]=='#':
      D[h][w]=10**5
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
def bfs(y,x):
  q=deque()
  q.append((y,x))
  
  while len(q):
    y,x=q.popleft()
    cnt=0
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W:
        if A[ny][nx]=='.' and D[y][x]<D[ny][nx]:
          q.appendleft((ny,nx))
          D[ny][nx]=D[y][x]

    for i in range(20):
      my=y+ey[i]
      mx=x+ex[i]
      if 0<=my<H and 0<=mx<W:
        if A[my][mx]=='.' and D[my][mx]==10**8:
          q.append((my,mx))
          D[my][mx]=D[y][x]+1
            
D[Ch-1][Cw-1]=0
bfs(Ch-1,Cw-1)
if D[Dh-1][Dw-1]==10**8:
  print(-1)
else:
  print(D[Dh-1][Dw-1])

### FIXED CODE ###

H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[10**8]*W for i in range(H)]
DD=[[-1]*W for i in range(H)]
dy=[-1,1,0,0]
dx=[0,0,1,-1,]
ey=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ex=[0,1,2,-1,-2,1,2,-1,-2,2,-2,1,2,-1,-2,0,1,2,-1,-2]
for h in range(H):
  for w in range(W):
    if A[h][w]=='#':
      D[h][w]=10**5
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
def bfs(y,x):
  q=deque()
  q.append((y,x))
  
  while len(q):
    y,x=q.popleft()
    cnt=0
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W:
        if A[ny][nx]=='.' and D[y][x]<D[ny][nx]:
          q.appendleft((ny,nx))
          D[ny][nx]=D[y][x]
          DD[ny][nx]=1

    for i in range(20):
      my=y+ey[i]
      mx=x+ex[i]
      if 0<=my<H and 0<=mx<W:
        if A[my][mx]=='.' and D[my][mx]==10**8 and DD[my][mx]==-1:
          q.append((my,mx))
          D[my][mx]=D[y][x]+1
            
D[Ch-1][Cw-1]=0
bfs(Ch-1,Cw-1)
if D[Dh-1][Dw-1]==10**8:
  print(-1)
else:
  print(D[Dh-1][Dw-1])
### BUGGY CODE ###

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

A.sort()
B.sort()
C.sort()

R=0
Y=[]
for b in B[::-1]:
    while (R<=N-1) and b<C[-(R+1)]:
        R+=1
    Y=[R]+Y
    
T=[0]
for i in range(N):
    T=[T[0]+Y[-(i+1)]]+T
T=T[:-1]

S=0
R=0
F=0
X=[]
for a in A[::-1]:
    while (R<=N-1) and a<B[-(R+1)]:
        F+=Y[-(R+1)]
        R+=1
    S+=F

print(S)


### FIXED CODE ###

def Binary_Search(A,x):
    L=0
    R=len(A)
    while R-L>1:
        C=(R+L-1)//2
        
        if A[C]<=x:
            L=C+1
        else:
            R=C+1
    return L
        
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort()
A.append(A[-1]+1)
B.sort()
C.sort()
C=[0]+C
C=[-c for c in C[::-1]]

S=0
for b in B:
    S+=Binary_Search(A,b-1)*Binary_Search(C,-(b+1))
print(S)
### BUGGY CODE ###

from math import gcd, sqrt
from functools import reduce

n, *A = map(int, open(0).read().split())
def f(A):
    sup = max(A)+1
    table = [set() for i in range(sup)]
    for i in range(2, sup):
        if not table[i]:
            for j in range(i, sup, i):
                table[j].add(i)
    D = set()
    for a in A:
        for b in table[a]:
            if b not in D:
                D.add(b)
            else:
                return False
    return True

if reduce(gcd, A) == 1:
    if f(A):
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

from math import gcd, sqrt
from functools import reduce

n, *A = map(int, open(0).read().split())
def f(A):
    sup = max(A)+1
    table = [set() for i in range(sup)]
    for i in range(2, sup):
        if not table[i]:
            for j in range(i, sup, i):
                table[j].add(i)
    D = set()
    for a in A:
        for b in table[a]:
            if b not in D:
                D.add(b)
            else:
                return False
    return True

if reduce(gcd, A) == 1:
    if f(A):
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

if __name__ == '__main__':
    a = [int(i) for i in input().split()]

    for i in range(1,10000000002):
        if i ==10000000001:
            print(-1)
            break
        if a[0]*i %a[1] >0:
            print(a[0]*i)
            break



### FIXED CODE ###

import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

if __name__ == '__main__':
    a = [int(i) for i in input().split()]

    for i in range(1,100000002):
        if a[0] % a[1]==0:
            print(-1)
            break

        if i ==10**9+1:
            print(-1)
            break
        if a[0]*i %a[1] >0:
            print(a[0]*i)
            break
        if a[0]*i >10**18 +1:
            print(-1)
            break
### BUGGY CODE ###

N = int(input())
A = input().split()

c = 1
i = 1
while i <= N-2:
	if int(A[i])-int(A[i-1]) > 0:
		if int(A[i+1])-int(A[i]) < 0:
			c += 1
			i += 2
		elif int(A[i+1])-int(A[i]) > 0:
			i += 1
		else:
			while int(A[i])-int(A[i-1]) == 0:
				i += 1
			if int(A[i])-int(A[i-1]) < 0:
				c += 1
				i += 2
	elif int(A[i])-int(A[i-1]) < 0:
		if int(A[i+1])-int(A[i]) > 0:
			c += 1
			i += 2
		else:
			while int(A[i])-int(A[i-1]) == 0:
				i += 1
			if int(A[i])-int(A[i-1]) > 0:
				c += 1
				i += 2
	else:
		i += 1

 
print(c)

### FIXED CODE ###

N = int(input())
A = input().split()

c = 1
i = 1

while i <= N-1:
	if int(A[i])-int(A[i-1]) == 0:
		del A[i-1]
		N -= 1
	else:
		i += 1

i = 1

while i <= N-2:
	if int(A[i])-int(A[i-1]) > 0:
		if int(A[i+1])-int(A[i]) < 0:
			c += 1
			i += 2
		else:
			i += 1
	else:
		if int(A[i+1])-int(A[i]) > 0:
			c += 1
			i += 2
		else:
			i += 1
 
print(c)
### BUGGY CODE ###

# C - GeT AC
# https://atcoder.jp/contests/abc122/tasks/abc122_c
import sys
n, q = list(map(int, sys.stdin.readline().split()))

s = input()

separators = [list(map(int, sys.stdin.readline().split())) for _ in range(q)]

# n = 8
# q = 3
# s = 'ACACTACG'
# separators = [[3, 7],[2, 3],[1, 8]]

cnt = []

for index in range(0, len(separators)):
    cnt.append(s[separators[index][0]-1:separators[index][1]].count('AC'))

for i in cnt:
    print(i)

### FIXED CODE ###

# C - GeT AC
# https://abc122.contest.atcoder.jp/tasks/abc122_c

"""
累積和を用いて実装しないと時間が足りない
"""

import sys
n, q = list(map(int, sys.stdin.readline().split()))
s = list(sys.stdin.readline())

cnt = [0] * (len(s)+1)

"""
ACを数えるために受けた文字列ｓを展開して数えていく
"""

for i in range(1, len(s)):
    """
    s = ACACTACG
    cnt = [0,0,1,1,2,2,2,3,3]
    i == 1, 2, 3……len(s)
    
    i == 1
    s[i] == C s[i-1] == A
    ここで代入されるべきなのはcntのindex2番である　
        なぜならば、cntは最初に0を代入するので、s[i]の位置に当たるのはcnt[i]+1であるため
    """

    if s[i] == "C" and s[i-1] == "A":
        cnt[i+1] = cnt[i] + 1
    else:
        cnt[i+1] = cnt[i]


r_and_l = [list(map(int, sys.stdin.readline().split())) for _ in range(q)]

for e in r_and_l:
    num = e[0]
    print(cnt[e[1]] - cnt[num] )
### BUGGY CODE ###

n,*l=map(int,open(0).read().split())
a=1
for i in l: a*=i
print([a,-1][a>10**18])

### FIXED CODE ###

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

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

result = 1

if 0 in Ai:
	result= '0'  
else:
  for i in range(N):
      result *= Ai[i]

  if result > 10**18:
    result = '-1'

print(result)

### FIXED CODE ###

import sys
n = int(input())
a = list(map(int,input().split()))
if 0 in a:
    print(0)
    sys.exit()
ans = 1
for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        print(-1)
        sys.exit()
print(ans)
### BUGGY CODE ###

L = input()
L = L[::-1]
len_L = len(L)
ans = 1
count = 0
for i, c in enumerate(L):
    if c == "1":
        ans *= 2
        ans += 3 ** i
        ans %= (10**9 + 7)

print(ans)


### FIXED CODE ###

M = 10**9 + 7

L = input()
L = L[::-1]
len_L = len(L)
ans = 1
count = 0
array_3 = [1]
for _ in range(len(L)):
    array_3.append((array_3[-1] * 3) % M)
for i, c in enumerate(L):
    if c == "1":
        ans *= 2
        ans += array_3[i]
        ans %= M

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

n = int(input())
a = list(map(int,input().split()))
ans = 1

for i in a:
  ans *= i
if ans > 1e18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
if 0 in a:
  print(0)

else:
  for i in a:
    ans *= i
    if ans > 1e18:
      print(-1)
      exit()
  print(ans)
### BUGGY CODE ###

import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

n = readInt()
aa = []
for i in range(n):
    aa.append(readInt())

memo = {}


def dfs(a, b, c, i):
    if i == len(aa):
        return 1 if c < a + b else 0
    if (a, b, c, i) in memo:
        return memo[(a, b, c, i)]

    ret = 0
    v0 = sorted([a + aa[i], b, c])
    ret = (ret + dfs(v0[0], v0[1], v0[2], i + 1)) % 998244353

    v1 = sorted([a, b + aa[i], c])
    ret = (ret + dfs(v1[0], v1[1], v1[2], i + 1)) % 998244353

    v2 = sorted([a, b, c + aa[i]])
    ret = (ret + dfs(v2[0], v2[1], v2[2], i + 1)) % 998244353

    memo[(a, b, c, i)] = ret
    return ret

print(dfs(0, 0, 0, 0))

### FIXED CODE ###

import sys

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret *= 3


L = (n * max(aa) + 1)
memo = [-1] * ((n+1) * L * 2)
def dfs(i, c):
    key = (i * L * 2) + 2 * c
    if 0 <= memo[key]:
        return memo[key: key+2]

    if i == n:
        memo[key + 0] = 3 if total <= (2 * c) else 0
        memo[key + 1] = 3 if total == (2 * c) else 0
        return memo[key: key + 2]

    v0 = dfs(i + 1, c)
    v1 = dfs(i + 1, c + aa[i])

    memo[key + 0] = (2 * v0[0] + v1[0]) % 998244353
    memo[key + 1] = (v0[1] + v1[1]) % 998244353
    return memo[key: key + 2]

a, b = dfs(0, 0)
ret = (ret - a + b) % 998244353
print(ret)