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

# https://drken1215.hatenablog.com/entry/2020/03/22/224200

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *A, = map(int, input().split())

    dp = [[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 1

    for i, a in enumerate(A):
        for j in range(S + 1):
            dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][0]) % MOD
            dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][1]) % MOD
            dp[i + 1][j][2] = (dp[i + 1][j][2] + dp[i][j][2]) % MOD
            if (nj := j + a) <= S:
                dp[i + 1][nj][1] = (dp[i + 1][nj][1] + dp[i][j][0] * (i + 1)) % MOD
                dp[i + 1][nj][2] = (dp[i + 1][nj][2] + dp[i][j][0] * (i + 1) * (N - i)) % MOD
                dp[i + 1][nj][1] = (dp[i + 1][nj][1] + dp[i][j][1]) % MOD
                dp[i + 1][nj][2] = (dp[i + 1][nj][2] + dp[i][j][1] * (N - i)) % MOD
    ans = dp[-1][-1][2]
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# https://atcoder.jp/contests/abc159/submissions/11139734

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

    dp = [0] * (S + 1)

    ret = 0
    for i, x in enumerate(a):
        dp[0] += 1
        if x > S: continue
        ret = (ret + dp[S - x] * (N - i)) % MOD
        for k in range(S - 1, x - 1, -1):
            dp[k] = (dp[k] + dp[k - x]) % MOD

    print(ret)


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

import heapq
S = input()
cum = []
dict = {}
for i in range(len(S)-1, -1, -1):
    n = int(S)
    n = n % 10**(i+1)
    cum.append(n % 2019)
    dict[n % 2019] = 0


for c in cum:
    dict[c] += 1
ans = 0
for k, v in dict.items():
    if k == 0:
        ans += v
    ans += v * (v-1) // 2

print(ans)

### FIXED CODE ###

import sys
import math
from collections import deque
from collections import Counter

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    S = SI()
    l = len(S)
    T = [0] * (l+1)
    inv_S = S[::-1]
    for i, s in enumerate(inv_S):
        s = int(s)
        T[i+1] = (T[i] + s * pow(10, i, 2019)) % 2019
    C = Counter(Counter(T).values())
    ans = 0
    for n, x in C.items():
        if n == 1: continue
        ans += cmb(n, 2) * x
    print(ans)


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

import sys,collections as cl,bisect as bs,copy
import sys
input = sys.stdin.readline
Max = 2000
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())
def s(x):
    a = []
    aa = x[i]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x):
    return " ".join(map(str,x))

h,w = m()

aa = [[] for i in range(h)]
aaa = []
ma = 0
for i in range(h):
    k = list(input())
    for j in range(w):
        if k[j] == "#":
            aa[i].append(0)
            aaa.append([i,j])
        else:
            aa[i].append(Max)
kk = []
while True:
    if len(aaa) == 0:
        break
    for i in range(len(aaa)):
        c,v = aaa.pop(0)
        if not c == 0:
            if aa[c-1][v] != min(aa[c][v]+1,aa[c-1][v]):
                aa[c-1][v] = min(aa[c][v]+1,aa[c-1][v])
                kk.append([c-1,v])
                ma = max(ma,aa[c-1][v])
        if not c == h-1:
            if aa[c+1][v] != min(aa[c][v]+1,aa[c+1][v]):
                aa[c+1][v] = min(aa[c][v]+1,aa[c+1][v])
                kk.append([c+1,v])
                ma = max(ma,aa[c+1][v])
        if not v == 0:
            if aa[c][v-1] != min(aa[c][v]+1,aa[c][v-1]):
                aa[c][v-1] = min(aa[c][v]+1,aa[c][v-1])
                kk.append([c,v-1])
                ma = max(ma,aa[c][v-1])
        if not v == w-1:
            if aa[c][v+1] != min(aa[c][v]+1,aa[c][v+1]):
                aa[c][v+1] = min(aa[c][v]+1,aa[c][v+1])
                kk.append([c,v+1])
                ma = max(ma,aa[c][v+1])
    aaa = kk
    kk = []
print(ma)
        


### FIXED CODE ###

import sys
input = sys.stdin.readline
Max = 2000
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())

h,w = m()

aa = [[] for i in range(h)]
aaa = []
ma = 0
for i in range(h):
    k = list(input())
    for j in range(w):
        if k[j] == "#":
            aa[i].append(0)
            aaa.append([i,j])
        else:
            aa[i].append(Max)
kk = []
while True:
    if len(aaa) == 0:
        break
    for i in range(len(aaa)):
        c,v = aaa[i]
        if not c == 0:
            if aa[c-1][v] > aa[c][v]+1:
                aa[c-1][v] = aa[c][v]+1
                kk.append([c-1,v])
                ma = max(ma,aa[c-1][v])
        if not c == h-1:
            if aa[c+1][v] > aa[c][v]+1:
                aa[c+1][v] = aa[c][v]+1
                kk.append([c+1,v])
                ma = max(ma,aa[c+1][v])
        if not v == 0:
            if aa[c][v-1] > aa[c][v]+1:
                aa[c][v-1] = aa[c][v]+1
                kk.append([c,v-1])
                ma = max(ma,aa[c][v-1])
        if not v == w-1:
            if aa[c][v+1] > aa[c][v]+1:
                aa[c][v+1] = aa[c][v]+1
                kk.append([c,v+1])
                ma = max(ma,aa[c][v+1])
    aaa = kk
    kk = []
print(ma)
### BUGGY CODE ###

n = int(input())
if n == 1:
    print(1, 1, 1)
    exit()
for i in range(1, 3500 + 1):
    for j in range(1, 3500 + 1):
        if 4 * i * j - n * i - n * j == 0:
            continue
        w = n * i * j / (4 * i * j - n * i - n * j)
        if w % 1 == 0 and w > 0:
            print(i, j, int(w))
            exit()

### FIXED CODE ###

n = int(input())
if n == 1:
    print(1, 1, 1)
    exit()
for i in range(1, 3500 + 1):
    for j in range(1, 3500 + 1):
        if 4 * i * j - n * i - n * j == 0:
            continue
        w = n * i * j / (4 * i * j - n * i - n * j)
        if w % 1 == 0 and w > 0:
            print(i, j, int(w))
            exit()
### BUGGY CODE ###

import heapq


def dijkstra(adj, start):
    ans = [float("inf")] * len(adj)
    q = [(0, start)]
    while len(q):
        cost, node = heapq.heappop(q)
        if cost > ans[node]:
            continue
        ans[node] = cost
        for nxt in adj[node]:
            heapq.heappush(q, (cost + adj[node][nxt], nxt))
    return ans


def main():
    n, m, s, t = map(int, input().split())
    adj1 = [{} for _ in range(n)]
    adj2 = [{} for _ in range(n)]
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        adj1[u-1][v-1] = a
        adj1[v-1][u-1] = a
        adj2[u-1][v-1] = b
        adj2[v-1][u-1] = b
    d1 = dijkstra(adj1, s-1)
    d2 = dijkstra(adj2, t-1)
    ans = [float("inf")] * n
    ans[n-1] = d1[n-1] + d2[n-1]
    for i in range(n-2, -1, -1):
        ans[i] = min(d1[i] + d2[i], ans[i+1])
    for i in range(n):
        print(10**15 - ans[i])


if __name__ == "__main__":
    main()


### FIXED CODE ###

from heapq import heappush, heappop


def dijkstra(N, adj, start=0):
    ans = [float("inf")] * N
    q = [(0, start)]
    while len(q):
        cost, i = heappop(q)
        if ans[i] <= cost:
            continue
        ans[i] = cost
        for nxt in adj[i]:
            if ans[nxt] == float("inf"):
                heappush(q, (cost + adj[i][nxt], nxt))
    return ans


def main():
    n, m, s, t = map(int, input().split())
    adj1 = [{} for _ in range(n)]
    adj2 = [{} for _ in range(n)]
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        adj1[u-1][v-1] = a
        adj1[v-1][u-1] = a
        adj2[u-1][v-1] = b
        adj2[v-1][u-1] = b
    d1 = dijkstra(n, adj1, s-1)
    d2 = dijkstra(n, adj2, t-1)
    ans = [float("inf")] * n
    ans[n-1] = d1[n-1] + d2[n-1]
    for i in range(n-2, -1, -1):
        ans[i] = min(d1[i] + d2[i], ans[i+1])
    for i in range(n):
        print(10**15 - ans[i])


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

n = int(input())
s = input()
ans = 0
for i in range(n):
    for j in range(i,n):
        for k in range(j,n):
            if s[i] !=s[j] and s[i]!= s[k] and s[j] != s[k]:
                if j-i != k-j:
                    ans+=1
                   # print(s[i],s[j],s[k])
print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from numba import njit
 
MOD = 10**9 + 7
 
N = int(readline())
S = np.array(list(read().rstrip()), np.int8)
 
R = np.sum(S == ord('R'))
B = np.sum(S == ord('B'))
G = np.sum(S == ord('G'))
 
@njit
def f(S):
    N = len(S)
    ret = 0
    for i in range(N):
        for j in range(i + 1, N):
            k = j + j - i
            if k >= N:
                break
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                ret += 1
    return ret
 
answer = R * B * G - f(S)
print(answer)
### BUGGY CODE ###

def main():
    h, w, m = map(int, input().split())
    bombs_h = [0] * h
    bombs_w = [0] * w
    B = []
    for n in range(m):
        h1, w1 = map(int, input().split())
        B.append((h1-1, w1-1))
        bombs_w[w1-1] += 1
        bombs_h[h1-1] += 1
    h_maxindex = [i for i, x in enumerate(bombs_h) if x == max(bombs_h)]
    w_maxindex = [i for i, x in enumerate(bombs_w) if x == max(bombs_w)]
    max_h = max(bombs_h)
    max_w = max(bombs_w)
    cnt = 0
    k = len(h_maxindex) * len(w_maxindex)
    for i, j in B:
        if bombs_h[i] == max_h and bombs_w[j] == max_w:
            cnt += 1
    ans = max_h + max_w - (cnt == k)
    print(ans)
    
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    h, w, m = map(int, input().split())
    bombs_h = [0] * h
    bombs_w = [0] * w
    B = []
    for n in range(m):
        h1, w1 = map(lambda x: int(x)-1, input().split())
        B.append((h1, w1))
        bombs_w[w1] += 1
        bombs_h[h1] += 1
    max_h = max(bombs_h)
    max_w = max(bombs_w)
    h_maxindex = [i for i, x in enumerate(bombs_h) if x == max_h]
    w_maxindex = [i for i, x in enumerate(bombs_w) if x == max_w]
    cnt = 0
    k = len(h_maxindex) * len(w_maxindex)
    for i, j in B:
        if bombs_h[i] == max_h and bombs_w[j] == max_w:
            cnt += 1
    ans = max_h + max_w - (cnt == k)
    print(ans)
    
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

A=input()

ans=1

for i in range(len(A)):
  for j in range(i+1,len(A)):
    if A[i]!=A[j]:
      ans+=1

print(ans)

### FIXED CODE ###

A=input()

dict={}

for i in range(len(A)):
  if A[i] in dict:
    dict[A[i]]+=1
  else:
    dict[A[i]]=1

ans=len(A)*(len(A)-1)/2+1

for k,v in dict.items():
  ans-=(v*(v-1)/2)

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

n = int(input())
a = [0]
a.extend(list(map(int,input().split())))
a.append(0)

s = []
for i in range(n+1):
    s.append(abs(a[i]-a[i+1]))

for i in range(1,n+1):
    print(sum(s)+abs(a[i-1]-a[i+1])-(abs(a[i-1]-a[i])+abs(a[i]-a[i+1])))


### FIXED CODE ###

n = int(input())
a = [0]
a.extend(list(map(int,input().split())))
a.append(0)

s = []
for i in range(n+1):
    s.append(abs(a[i]-a[i+1]))
ss = sum(s)
for i in range(1,n+1):
    print(ss+abs(a[i-1]-a[i+1])-(abs(a[i-1]-a[i])+abs(a[i]-a[i+1])))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N = int(input())

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

mul = A[0]
for i in A[1:]:
    mul *= i

if mul > 1000000000000000000:
    print(-1)
else:
    print(mul)

### FIXED CODE ###

# -*- coding: utf-8 -*-

import numpy as np

N = int(input())

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

if 0 in A:
    print(0)
    exit(0)

mul = A[0]

if np.sum(A < 0) % 2 == 1:
    for i in A[1:]:
        mul *= i
else:
    for i in A[1:]:
        if 1000000000000000000 / i < mul:
            print(-1)
            exit(0)
        mul *= i

if mul > 1000000000000000000:
    print(-1)
    exit(0)

print(mul)
### BUGGY CODE ###

s = input()
n = len(s)
s = s + ' '
k = int(input())
l = []
for i in range(1, n+1):
    for j in range(n-i+1):
        l.append(s[j:j+i])
ans = sorted(list(set(l)))[k-1]
print(ans)

### FIXED CODE ###

s = input()
n = len(s)
s = s + ' '
k = int(input())
l = []
for i in range(1, k+1):
    for j in range(n - i + 1):
        l.append(s[j:j + i])
ans = sorted(list(set(l)))[k - 1]
print(ans)
### BUGGY CODE ###

def cf(x1, x2):
    ret = []
    for i in range(2, min(x1, x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            ret.append(i)
    return ret


def is_prime_number(num):
    if num == 1:
        return False

    i = 2
    while i*i <= num:
        if num % i == 0:
            return False
        i += 1
    return True


def main():
    a, b = map(int, input().split())
    common_divisor_list = cf(a, b)

    count = 0
    for num in common_divisor_list:
        if is_prime_number(num):
            count += 1

    print(count + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


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


def main():
    a, b = map(int, input().split())
    gcd_num = gcd(a, b)
    c = collections.Counter(prime_factorize(gcd_num))
    # print(prime_factorize(gcd_num))
    # cには１が含まれていないので、その分カウントを増やす
    print(len(c) + 1)


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

input_line1 = input()
N = int(input_line1)
input_line2 = input()
numbers = input_line2.split()
num_sum = 1


for i in range(N):
    num_sum *= int(numbers[i])

if num_sum > 10 ** 18:
    num_sum = -1

print(num_sum)

### FIXED CODE ###

input_line1 = input()
N = int(input_line1)
input_line2 = input()
numbers = input_line2.split()
num_sum = 1
 
if '0' in numbers:
    print(0)

else:
    for i in range(N):
        num_sum *= int(numbers[i])
        if num_sum > 10 ** 18:
            num_sum = -1
            break
 
    print(num_sum)
### BUGGY CODE ###

import itertools

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


def mindist(XLIST):
    dist = float('Inf')
    for i in itertools.permutations(XLIST, len(XLIST)):
        dist_ = 0
        curx = 0
        for j in range(len(i)):
            dist_ += abs(i[j]-curx)
            curx = i[j]
        if (dist_ < dist):
            dist = dist_
    return(dist)

dist = float('Inf')
for i in itertools.combinations(X, K):
    dist_ = mindist(i)
    if (dist_ < dist):
        dist = dist_

print(dist)


### FIXED CODE ###

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

dist = []
for i in range(N-K+1):
    dist.append(abs(X[i]) + abs(X[K+i-1]-X[i]))
    dist.append(abs(X[K+i-1]) + abs(X[i]-X[K+i-1]))

if not len(dist) == 0:
    print(min(dist))
else:
    print(0)
### BUGGY CODE ###

n = int(input())
nums = [int(x) for x in input().split()]
total = 0

for i in range(0,n-1):
    total += nums[i]*sum(nums[i+1:n])

print(total%(10**9+7))

### FIXED CODE ###

n = int(input())
nums = [int(x) for x in input().split()]
multinums = [0]
total = 0

for i in range(0,n):  #累積和配列を作成する
    multinums.append(multinums[i]+nums[i])

#print(multinums)

for i in range(0,n):
    #print(nums[i],multinums[n]-multinums[i+1],nums[i] * (multinums[n]-multinums[i+1]))
    total += nums[i] * (multinums[n]-multinums[i+1])

print(total%(10**9+7))
### BUGGY CODE ###

n, m, q = map(int, input().split())
lr_array = [[int(x) for x in input().split()] for y in range(m)]
pq_array = [[int(x) for x in input().split()] for y in range(q)]


def solve1():
    table = [[0 for x in range(n+1)] for y in range(n+1)]
    for l, r in lr_array:
        table[l][r] += 1

    return 0


# 横軸：スタート
# 縦軸：ゴール
# 2次元累積和で解く
def solve2():
    cumulative_lr = [[0 for x in range(n + 1)] for y in range(n + 1)]
    for l, r in lr_array:
        for i in range(1, l + 1):
            for j in range(r, n + 1):
                cumulative_lr[i][j] += 1

    for p, q in pq_array:
        print(cumulative_lr[p][q])


if __name__ == '__main__':
    solve2()


### FIXED CODE ###

n, m, q = map(int, input().split())
lr_array = [[int(x) for x in input().split()] for y in range(m)]
pq_array = [[int(x) for x in input().split()] for y in range(q)]


def solve1():
    table = [[0 for x in range(n + 1)] for y in range(n + 1)]
    for l, r in lr_array:
        table[l][r] += 1
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            table[i][j] = table[i][j - 1] + table[i][j]
    for p, q in pq_array:
        res = 0
        for i in range(p, q + 1):
            # print(i)
            res += table[i][q]
        print(res)

    return 0


# 横軸：スタート
# 縦軸：ゴール
# 2次元累積和で解く
def solve2():
    cumulative_lr = [[0 for x in range(n + 1)] for y in range(n + 1)]
    for l, r in lr_array:
        for i in range(1, l + 1):
            for j in range(r, n + 1):
                cumulative_lr[i][j] += 1

    for p, q in pq_array:
        print(cumulative_lr[p][q])


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

n,w=map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
t=[[0 for i in range(n+1)] for j in range(w+1)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(weight[j-1]<=i):
            t[i][j]=max(value[j-1]+t[i-weight[j-1]][j-1],t[i][j-1])
        else:
            t[i][j]=t[i][j-1]
print(t[-1][-1])


### FIXED CODE ###

import array
n,w=map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
t=[[0 for i in range(n+1)] for j in range(w+1)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(weight[j-1]<=i):
            t[i][j]=max(value[j-1]+t[i-weight[j-1]][j-1],t[i][j-1])
        else:
            t[i][j]=t[i][j-1]
print(t[-1][-1])
### BUGGY CODE ###

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

c = [0 for i in range(n)]

for i in range(1, n):
    l = max(0, i-k)
    c[i] = min([c[x] + abs(h[x] - h[i]) for x in range(l, i)])

print(c[n-1])


### FIXED CODE ###

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

c = [0 for i in range(n)]

for i in range(1, n):
    l = max(0, i-k)
    c[i] = min(cj + abs(hj - h[i]) for hj, cj in zip(h[l:i], c[l:i]))

print(c[n-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
p = tuple(p)

chk = 0
for i in range(n-k+1):
  m = sum(p[i:k+i])
  chk = max(chk,m)

print((chk+k)/2)

### FIXED CODE ###

def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  import numpy as np #pypy不可
  n,k = map(int,readline().split())
  p =  np.array(read().split(),np.int32)
  np.cumsum(p,out=p)
  chk = p[k-1]
  for i in range(n-k):
    c = p[i+k]-p[i]
    chk = max(c,chk)
  print((chk+k)/2)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

A, B, K = map(int, input().split())

for i in range(K):
	if A > 0:
		A -= 1
	elif B > 0:
		B -= 1
	else:
		pass
		
print(A, B)

### FIXED CODE ###

A, B, K = map(int, input().split())


	
if K <= A:
	print(A - K, B)
elif K <= A + B:
	print(0, A + B - K)
else:
	print(0, 0)
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]

ans = 1
for i in range(N):
  ans *= A[i]
if ans > 10 ** 18:
  print('-1')
else:
  print(ans)


### FIXED CODE ###


N = int(input())
A = [int(a) for a in input().split()]
if 0 in A:
  print(0)
  exit() 
ans = 1
for i in range(N):
  ans *= A[i]
  if ans > 10 ** 18:
    print('-1')
    exit()
print(ans)
### BUGGY CODE ###

from fractions import Fraction
def main():
    N = int(input())
    checked = [[False for _ in range(3500)] for _ in range(3500)]
    for h in range(1, 3501):
        for n in range(1,3501):
            if checked[h-1][n-1] == False:

                checked[h-1][n-1] = True
                checked[n-1][h-1] = True
                
                a = N*h*n
                b = 4*n*h - N*n - N*h 
                if a >= b and b >  0 and a%b == 0:
                    w = Fraction(N*h*n, 4*n*h - N*n - N*h)
                    if Fraction(4, N) == Fraction(1, h) + Fraction(1, n) + Fraction(1, w):
                        print(h,n,w)
                        exit()
                else:
                    continue
            else:
                continue

if __name__ == "__main__":
    main()

### FIXED CODE ###

from fractions import Fraction
def main():
    N = int(input())

    for h in range(1, 3501):
        for n in range(h,3501):
            a = N*h*n
            b = 4*n*h - N*n - N*h 
            if a >= b and b >  0 and a%b == 0:
                w = Fraction(N*h*n, 4*n*h - N*n - N*h)
                if Fraction(4, N) == Fraction(1, h) + Fraction(1, n) + Fraction(1, w):
                    print(h,n,w)
                    exit()
            else:
                continue

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

N = int(input())
S = list(input())
Q = []
for i in range(0,N) :
    if i == 0 :
        A = S[0:i]
        B = S[i+1:N]
        Q.append(A.count("W")+B.count("E"))
    elif S[i-1] == "E" and S[i] == "E" :
        A = S[0:i]
        B = S[i+1:N]
        Q.append(A.count("W")+B.count("E"))
print(min(Q))



### FIXED CODE ###

N = int(input())
S = list(input())
ANS = []
ans = 0
for i in range(0,N) :
    if i == 0 :
        ans += S[1:].count("E")
        ANS.append(ans)
    elif S[i-1] == "E" and S[i] == "E" :
        ans -= 1
        ANS.append(ans)
    elif S[i-1] == "W" and S[i] == "W" :
        ans += 1
        ANS.append(ans)
print(min(ANS))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)

a,b,c,d = map(int,input().split())
ans = 0
for i in range(a,b+1):
  if i % c != 0:
    if i % d != 0:
      ans += 1
print(ans)


### FIXED CODE ###

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

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

def F(N,C,D):
  x = N
  x -= N//C
  x -= N//D
  lcm = C*D//gcd(C,D)
  x += N//lcm
  return x

answer = F(B,C,D) - F(A-1,C,D)
print(answer)
### BUGGY CODE ###

N = int(input())
A_ = list(map(int, input().split()))
A = []
mod = 10 ** 9 + 7
for a_ in A_:
    a = a_ % mod
    A.append(a)

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        ans += A[i] * A[j] % mod
        ans %= mod

print(ans)

### FIXED CODE ###

N = int(input())
A_ = list(map(int, input().split()))
A = []
mod = 10 ** 9 + 7
for i, a_ in enumerate(A_[::-1]):
    if i == 0:
        A.append(a_ % mod)
    else:
        a = (a_ + A[-1]) % mod
        A.append(a)
A = A[::-1]
A = A[1:]
ans = 0
for i, a in enumerate(A_[:-1]):
    ans += A[i] * a % mod
    ans %= mod

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

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

suma = [0 for i in range(len(a)+1)]
sumb = [0 for i in range(len(b)+1)]

for i in range(1, len(a)+1):
    suma[i] = suma[i-1] + a[i-1]

for i in range(1, len(b)+1):
    sumb[i] = sumb[i-1] + b[i-1]

mnum = 0
for i in range(len(suma)):
    num = 0
    for j in range(len(sumb))[::-1]:
        if suma[i] + sumb[j] <= k:
            num = i + j
            break
    if num > mnum:
        mnum = num

print(mnum)

### FIXED CODE ###

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

suma = [0 for i in range(len(a)+1)]
sumb = [0 for i in range(len(b)+1)]

for i in range(1, len(a)+1):
    suma[i] = suma[i-1] + a[i-1]

for i in range(1, len(b)+1):
    sumb[i] = sumb[i-1] + b[i-1]

mnum = 0
best = len(sumb)
for i in range(len(suma)):
    for j in range(best)[::-1]:
        if suma[i] + sumb[j] <= k:
            mnum = max(mnum, i+j)
            best = j+1
            break

print(mnum)