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

from math import sqrt
from copy import deepcopy
from functools import reduce
from operator import mul
n = int(input())
def pf(n):
    pfs = []
    while n % 2 == 0:
        pfs.append(2)
        n //= 2
    for i in range(3, int(sqrt(n)+1), 2):
        while n % i == 0:
            pfs.append(i)
            n //= i
    if n > 2:
        pfs.append(n)
    return pfs
def partition(pfs):
    subsets = [[]]
    for i in range(len(pfs)):
        for j in range(len(subsets)):
            c = deepcopy(subsets[j])
            subsets.append(c + [i])
    return subsets

pfs = pf(n)
Asubs = partition(pfs)
def digits(n):
    ans = 0
    while n > 0:
        ans += 1
        n //= 10
    return ans

def calculate(Asubs):
    minSoFar = 10
    for Asub in Asubs:
        if Asub == []:
            Asum = 1
        else:
            Asum = reduce(mul, [pfs[i] for i in Asub])
        Bsub = [pfs[i] for i in range(len(pfs)) if i not in Asub]
        if Bsub == []:
            Bsum = 1
        else:
            Bsum = reduce(mul, Bsub)
        if max(digits(Asum), digits(Bsum)) < minSoFar:
            minSoFar = max(digits(Asum), digits(Bsum))
    return minSoFar
print (calculate(Asubs))

### FIXED CODE ###

from math import sqrt
n = int (input())
nsqrt = int(sqrt(n))
for i in range(nsqrt, 0, -1):
    if n % i == 0:
        b = n // i
        a = i
        break
    if i == 1:
        b = 1
        a = n
def digits(n):
    ans = 0
    while n > 0:
        ans += 1
        n //= 10
    return ans
print (max(digits(a), digits(b)))
### BUGGY CODE ###

def main():
    # 入力
    n, m, r = map(int, input().split())
    abc = [list(map(int, input().split())) for _ in [0]*m]
    # グラフ
    g = [[] for _ in [0]*n]
    [g[a-1].append([b-1, c]) for a, b, c in abc]

    # 逆辺
    g2 = [[] for _ in [0]*n]
    [g2[b-1].append([a-1, c]) for a, b, c in abc]

    # 前処理用のDFS
    def remove_edge(graph, start):
        q = [start]
        memo = [True for _ in range(n)]
        memo[start] = False
        while q:
            qq = q.pop()
            for i, j in graph[qq]:
                if memo[i]:
                    q.append(i)
                    memo[i] = False
        return {i for i, j in enumerate(memo) if j == True}

    # 前処理
    rmv = remove_edge(g, 0) | remove_edge(g2, n-1)
    for i in rmv:
        g[i] = []
    for i in range(n):
        for j in g[i]:
            if j[0] in rmv:
                g[i].remove(j)

    # ベルマンフォード
    dist = [-10**15 for _ in [0]*n]
    dist[0] = 0

    for k in range(n):
        for p in range(n):
            for i, j in g[p]:
                dist[i] = max(dist[i], dist[p]+j-r)
        if k == n-2:
            d1 = [t for t in dist]
        if k == n-1:
            d2 = [t for t in dist]

    # 1からでもnの間に負の閉路があるときは-1
    if d1 == d2:
        print(max(d1[-1], 0))
    else:
        print(-1)
main()


### FIXED CODE ###

#入力
n,m,r=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
#グラフ
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]
#逆辺
g2=[[] for _ in [0]*n]
[g2[b-1].append([a-1,c]) for a,b,c in abc]

#ベルマンフォード
dist=[-10**15 for _ in [0]*n]
dist[0]=0
a,b=-10**15,-10**15

for k in range(n):
    for p in range(n):
        for i,j in g[p]:
            dist[i]=max(dist[i],dist[p]+j-r)
    if k==n-2:
        d1=[t for t in dist]
    if k==n-1:
        d2=[t for t in dist]
    
#負の経路上の頂点の一覧
loop=set()
for i in range(n):
    if d1[i]!=d2[i]:
        loop.add(i)    
ans=max(d2[n-1],0)

#1からの到達可能地点
q=[0]
memo=[True for _ in range(n)]
memo[0]=False
while q:
    qq=q.pop()
    for i,j in g[qq]:
        if memo[i]:
            q.append(i)
            memo[i]=False
            
#nからの逆辺による到達可能地点
q=[n-1]
memo2=[True for _ in range(n)]
memo2[n-1]=False
while q:
    qq=q.pop()
    for i,j in g2[qq]:
        if memo2[i]:
            q.append(i)
            memo2[i]=False
            
#1からでもnからでも行ける点でかつ負の閉路に入っているものがあるときは-1
for i in loop:
    if memo[i]==False and memo2[i]==False:
        ans=-1
        
print(ans)
### BUGGY CODE ###

from bisect import bisect_left,bisect_right
import string 

dic = {c:[] for c in string.ascii_lowercase}

n = int(input())
s = list(input())
q = int(input())

for i,c in enumerate(s,start=1):
  dic[c].append(i)
  
for i in range(q):
  p,l,r = map(str,input().split())
  if p =='1':
    j = int(l)
    c = s[j-1]
    dic[c].pop(bisect_left(dic[c],j))
    dic[r].insert(bisect_left(dic[r],j),j)
    s[j-1] = r
  else:
    ans = 0
    l = int(l)
    r = int(r)
    for c in string.ascii_lowercase:
      pl = bisect_left(dic[c],l)
      if pl < len(dic[c]):
        if dic[c][pl] <= r:
          ans += 1
    print(ans)

### FIXED CODE ###

from bisect import bisect_left,bisect_right
import string 

dic = {c:[] for c in string.ascii_lowercase}

n = int(input())
s = list(input())
q = int(input())

for i,c in enumerate(s,start=1):
  dic[c].append(i)
  
for i in range(q):
  p,l,r = map(str,input().split())
  if p =='1':
    j = int(l)
    if r == s[j-1]:
      continue
    c = s[j-1]    
    dic[c].pop(bisect_left(dic[c],j))
    dic[r].insert(bisect_left(dic[r],j),j)
    s[j-1] = r
  else:
    ans = 0
    l = int(l)
    r = int(r)
    for c in string.ascii_lowercase:
      pl = bisect_left(dic[c],l)
      if pl < len(dic[c]):
        if dic[c][pl] <= r:
          ans += 1
    print(ans)
### BUGGY CODE ###

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

def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] =min(d[i][j],d[i][k] + d[k][j])            
    return d

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

d = [[float("inf") for i in range(N)] for i in range(N)]

for i in range(M):
    A, B, C = map(int, input().split())
    if C <= L:
        d[A-1][B-1] = C
        d[B-1][A-1] = C

S = [[float("inf")] * N for _ in range(N)]
warshall_floyd(d)

for i in range(N):
    for j in range(N):
        if d[i][j] <= L:
            S[i][j] = 1
            S[j][i] = 1
            
warshall_floyd(S)

Q = int(input())

for i in range(Q):
    s, t = map(int, input().split())
    if S[s-1][t-1] == float("inf"):
        print(-1)
    else: 
        print(S[s-1][t-1]-1)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import floyd_warshall

"""
def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] =min(d[i][j],d[i][k] + d[k][j])            
    return d
"""
N, M, L = map(int, input().split())

d = [[0 for i in range(N)] for i in range(N)]

for i in range(M):
    A, B, C = map(int, input().split())
    d[A-1][B-1] = C
    d[B-1][A-1] = C

d = floyd_warshall(d, directed = False)
S = [[0 for i in range(N)] for i in range(N)]


for i in range(N):
    for j in range(N):
        if d[i][j] <= L:
            S[i][j] = 1
            S[j][i] = 1
            
S = floyd_warshall(S, directed = False)

Q = int(input())

for i in range(Q):
    s, t = map(int, input().split())
    if S[s-1][t-1] == float("inf"):
        print(-1)
    else: 
        print(int(S[s-1][t-1]-1))
### BUGGY CODE ###

n = int(input())
a = list(map(int, 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 = list(map(int, input().split()))

if 0 in a:
    print(0)
else:

    ans = 1
    i = 0
    while (i <= n - 1):
        if ans <= 10 ** 18:
            ans *= a[i]
            i += 1
        else:
            break

    #print(i)
    if ans <= 10 ** 18:
        print(ans)
    else:
        print(-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
dic = dict()
dic[0] = 0
def dfs(uno,dos,tres):
  if uno < 0 or dos < 0 or tres < 0:
    return 0
  if uno + dos*301 + tres*90601 in dic:
    return dic[uno + dos*301 + tres*90601]
  t = uno + dos + tres
  res = n
  res += uno*dfs(uno-1,dos,tres)
  res += dos*dfs(uno+1,dos-1,tres)
  res += tres*dfs(uno,dos+1,tres-1)
  res /= t
  dic[uno + dos*301 + tres*90601] = res
  return res
print(dfs(a.count(1),a.count(2),a.count(3)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
uno = a.count(1)
dos = a.count(2)
tres = n - uno - dos
dp = [[[0]*(n+1) for _ in range(dos+tres+1)] for j in range(tres+1)]
for k in range(tres+1):
  for j in range(dos+tres-k+1):
    for i in range(n+1-j-k):
      if i+j+k == 0: continue
      v = i+j+k
      res = n
      if i: res += i * dp[k][j][i-1]
      if j: res += j * dp[k][j-1][i+1]
      if k: res += k * dp[k-1][j+1][i]
      dp[k][j][i] = res / v
print(dp[tres][dos][uno])
### BUGGY CODE ###

def wf(this_graf):
    s = len(graf)
    for k in range(s):
        for i in range(s):
            for j in range(s):
                this_graf[i][j] = min(this_graf[i][j], this_graf[i][k] + this_graf[k][j])
    return this_graf

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
graf = [[10 ** 10 for i in range(n)] for j in range(n)]

for i, j in ab:
    graf[i - 1][j - 1] = 1
    graf[j - 1][i - 1] = 1

import copy
cnt = 0

for i, j in ab:
    this_graf = copy.deepcopy(graf)
    tmp = 0
    this_graf[i - 1][j - 1] = 10 ** 10
    this_graf[j - 1][i - 1] = 10 ** 10
    this_graf = wf(this_graf)
    for i in range(n):
        for j in range(n):
            if this_graf[i][j] == 10 ** 10:
                tmp = 1
                break
        if tmp:
            break
    cnt += tmp

print(cnt)

### FIXED CODE ###

def wf(this_graf):
    s = len(graf)
    for k in range(s):
        for i in range(s):
            for j in range(s):
                this_graf[i][j] = min(this_graf[i][j], this_graf[i][k] + this_graf[k][j])
    return this_graf

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
graf = [[10 ** 10 for i in range(n)] for j in range(n)]

for i, j in ab:
    graf[i - 1][j - 1] = 1
    graf[j - 1][i - 1] = 1

import copy
cnt = 0

for i, j in ab:
    this_graf = copy.deepcopy(graf)
    tmp = 0
    this_graf[i - 1][j - 1] = 10 ** 10
    this_graf[j - 1][i - 1] = 10 ** 10
    this_graf = wf(this_graf)
    for i in range(n):
        for j in range(n):
            if this_graf[i][j] == 10 ** 10:
                tmp = 1
                break
        if tmp:
            break
    cnt += tmp

print(cnt)
### BUGGY CODE ###

# ABC067-C
N = int(input())
a = list(map(int, input().split()))
a_sum = sum(a)
x = 0
y = 0
diff = []
for i in range(0, N-1):
    x_a = a[0:i+1]
    x = sum(x_a)
    y = a_sum - x
    diff.append(abs(x-y))
print(min(diff))    

### FIXED CODE ###

import numpy as np
N = int(input())
a = list(map(int, input().split()))

res = np.cumsum(a)
# print(res)
sum_a = np.sum(a)
ans = 100000000000
for i in range(N - 1):
    tmp = abs((sum_a - res[i]) - res[i])
    # print(tmp)
    if tmp < ans:
        ans = tmp

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

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

mod = 10**9+7
ans = 0
for C in itertools.combinations(a, 2):
    ans += (C[0]^C[1])%mod
    ans %= mod
    
print(ans)

### FIXED CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))

    mod = 10**9+7
    ans = 0

    for k in range(60):
        x, y = 0, 0
        for a in A:
            x += 1 & a>>k
        tmp = x*(n-x)%mod
        tmp *= pow(2, k, mod)
        ans += tmp
        ans %= mod
    print(ans)


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

S = input()
Q = int(input())
t = []
f = []
c = []
for i in range(Q):
    in_ = list(input().split())
    if in_[0] == "1":
        t.append(1)
        f.append(0)
        c.append(0)
    else:
        t.append(2)
        f.append(int(in_[1]))
        c.append(in_[2])
        
acc = [0 for _ in range(Q)]
if t[-1] == 1:  acc[-1] = 1
for i in reversed(range(Q - 1)):
    if t[i] == 1:
        acc[i] = acc[i + 1] + 1
    else:
        acc[i] = acc[i + 1]
        
if acc[0] % 2 == 0:
    ans = S
else:
    ans = S[::-1]
    
for i in range(Q):
    if t[i] == 2:
        if (f[i] + acc[i]) % 2 == 1:
            ans = c[i] + ans
        else:
            ans += c[i]
print(ans)

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
t = []
f = []
c = []
for i in range(Q):
    in_ = list(input().split())
    if in_[0] == "1":
        t.append(1)
        f.append(0)
        c.append(0)
    else:
        t.append(2)
        f.append(int(in_[1]))
        c.append(in_[2])
acc = [0 for _ in range(Q)]
if t[-1] == 1:  acc[-1] = 1
for i in reversed(range(Q - 1)):
    if t[i] == 1:
        acc[i] = acc[i + 1] + 1
    else:
        acc[i] = acc[i + 1]
        
if acc[0] % 2 == 0:
    ans = deque(S)
else:
    ans = deque(S[::-1])
    
for i in range(Q):
    if t[i] == 2:
        if (f[i] + acc[i]) % 2 == 1:
            ans.appendleft(c[i])
        else:
            ans.append(c[i])
print("".join(ans))
### BUGGY CODE ###

from operator import itemgetter
import numpy as np
import bisect


def is_input(node, path):
    for i in range(len(path)):
        if path[i][node]:
            return True
    return False


def topological_sort(path):
    S = []
    path = np.array(path)
    for i in range(len(path[0])):
        if any(path[:, i]):
            pass
        else:
            S.append(i)
    res = []
    while len(S) > 0:
        now = S.pop()
        res.append(now)
        for i, f in enumerate(path[now]):
            if f:
                path[now][i] = False
                if not is_input(i, path):
                    S.append(i)
    return res

N, M = map(int, input().split(" "))
path = [[False for i in range(N)] for i in range(N)]


for i in range(N+M-1):
    a, b = map(int, input().split(" "))
    path[a-1][b-1] = True

sorted_nodes = topological_sort(path)

input_nodes_list = [[] for i in range(N)]
for i, line in enumerate(path):
    temp = []
    for j, f in enumerate(line):
        if f:
            input_nodes_list[j].append(i)
ans = []
dict_sorted_nodes = {}
for i, v in enumerate(sorted_nodes):
    dict_sorted_nodes[v] = i

for input_nodes in input_nodes_list:
    if len(input_nodes) == 0:
        print(0)
        continue
    if len(input_nodes) == 1:
        print(input_nodes[0]+1)
        continue
    temp_i = 0
    for i in input_nodes:
        temp_i = max(temp_i, dict_sorted_nodes[i])

    print(sorted_nodes[temp_i]+1)



### FIXED CODE ###

from collections import deque
from operator import itemgetter


def topolo():
    q = deque(v1 for v1 in range(N) if ins[v1] == 0)
    res = []
    popleft, append = q.popleft, q.append
    res_append = res.append
    while q:
        v1 = popleft()
        res_append(v1)
        for v2 in edges[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                append(v2)
    return res


N, M = map(int, input().split(" "))
edges = [[] for _ in [0]*N]
rev = [[] for _ in [0]*N]

ins = [0]*N

for a, b in (map(int, input().split(" ")) for _ in [0]*(N+M-1)):
    edges[a-1].append(b-1)
    rev[b-1].append(a-1)
    ins[b-1] += 1

sorted_nodes = topolo()
order = [i for i, v in sorted(enumerate(sorted_nodes), key=itemgetter(1))]

for input_nodes in rev:
    l = len(input_nodes)
    if l == 0:
        print(0)
        continue
    elif l == 1:
        print(input_nodes[0] + 1)
        continue
    temp = 0
    for node in input_nodes:
        temp = max(temp, order[node])
    print(sorted_nodes[temp] + 1)
### BUGGY CODE ###

from itertools import permutations


def solve(n, m, r):
    ans = float('inf')
    d = [[float("inf") for i in range(n)] for i in range(n)]
    rx = list(map(int, input().split()))
    rx = list(map(lambda x: x-1, rx))

    for i in range(m):
        s, t, length = map(int, input().split())
        d[s-1][t-1] = length
        d[t-1][s-1] = length

    for i in range(n):
        d[i][i] = 0

    d = warshall_floyd(d)

    for p in permutations(rx, r):
        from_p1_to_pr = 0
        for j in range(r-1):
            from_p1_to_pr += d[p[j]][p[j+1]]
        ans = min(ans, from_p1_to_pr)

    return ans


def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


if __name__ == '__main__':
    n, m, r = map(int, input().split())
    print(solve(n, m, r))


### FIXED CODE ###

from itertools import permutations


def solve(n, m, r):
    ans = 10**18
    d = [[10**18]*n for _ in range(n)]
    rx = list(i-1 for i in map(int, input().split()))

    for i in range(m):
        s, t, length = map(int, input().split())
        d[s-1][t-1] = length
        d[t-1][s-1] = length

    for i in range(n):
        d[i][i] = 0

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dt = d[i][k] + d[k][j]
                if dt < d[i][j]:
                    d[i][j] = dt

    for p in permutations(rx):
        from_p1_to_pr = 0
        for p_j,  p_next in zip(p, p[1:]):
            from_p1_to_pr += d[p_j][p_next]
        if from_p1_to_pr < ans:
            ans = from_p1_to_pr

    return ans


if __name__ == '__main__':
    n, m, r = map(int, input().split())
    print(solve(n, m, r))
### BUGGY CODE ###

from collections import defaultdict
from bisect import bisect_right
INF = float('inf')
N, Ma, Mb = map(int, input().split())
a, b, c = [None] * N, [None] * N, [None] * N
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())
hN = N // 2
dic1 = defaultdict(lambda : INF)
for i in range(1 << hN):
    _a, _b, _c = 0, 0, 0
    for j in range(hN):
        if (i >> j) & 1:
            _a += a[j]
            _b += b[j]
            _c += c[j]
    if _c < dic1[(_a, _b)]:
        dic1[(_a, _b)] = _c
dic2 = defaultdict(lambda : INF)
for i in range(1 << (N - hN)):
    _a, _b, _c = 0, 0, 0
    for j in range(N - hN):
        if (i >> j) & 1:
            _a += a[hN+j]
            _b += b[hN+j]
            _c += c[hN+j]
    if _c < dic2[(_a, _b)]:
        dic2[(_a, _b)] = _c
ans = INF
for k in dic1:
    _a, _b = k
    v = dic1[k]
    for i in range(1, N+1):
        ans = min(ans, v + dic2[(Ma*i-_a,Mb*i-_b)])
ans = ans if ans < INF else -1
print(ans)

### FIXED CODE ###

from collections import defaultdict
N, Ma, Mb = map(int, input().split())
INF, MAX = 1000000000, 10 * N + 1
dp = defaultdict(lambda : INF)
dp[(0, 0)] = 0
for i in range(N):
    a, b, c = map(int, input().split())
    predp = dp.copy()
    for ab, v in predp.items():
        _a, _b = ab
        dp[(_a+a, _b+b)] = min(dp[(_a+a, _b+b)], v+c)
ans = INF
for i in range(1, N+1):
    ans = min(ans, dp[(Ma*i, Mb*i)])
ans = -1 if ans == INF else ans
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
cards = list(map(int,input().split()))

from collections import deque

cards = deque(cards)

for _ in range(m):
    b,c = map(int,input().split())

    cards+=[c]*b

cards = sorted(cards,reverse=True)

total = 0
for i in range(n):
    total += cards[i]

print(total)


### FIXED CODE ###

n,m = map(int,input().split())
cards = list(map(int,input().split()))

from collections import Counter

d = dict(Counter(cards))

for _ in range(m):
    b,c = map(int,input().split())

    if c in d:
        d[c]+=b
    else:
        d[c]=b

d= sorted(d.items(),key=lambda x: x[0],reverse=True)

ans = 0
cnt = 0
for j in d:
    cnt +=j[1]
    ans +=j[0] * j[1]



    if cnt>n:
        ans -=j[0]*(cnt-n)
        print(ans)
        exit(0)

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

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

w = 0
s = 0
ratio = 0

for i in range(31):
    for j in range(31):
        water = a*i + b*j
        for k in range(1501):
            l = 0
            hoge = 1024
            while hoge:
                nl = l+hoge
                sugar = k*c+nl*d
                if 0 < water and water*100 + sugar <= f and sugar <= water*e:
                    l = nl
                hoge /= 2
            sugar = k*c+nl*d
            if ratio <= sugar / (water*100+sugar):
                w = water*100
                s = sugar
                ratio = sugar / (water*100+sugar)

print("%d %d"%(w+s,s))


### FIXED CODE ###

a,b,c,d,e,f = map(int, input().split(' '))

w = 0
s = 0
ratio = 0

for i in range((f // (b*100))+1):
    for j in range(((f-(i*b*100))//(a*100))+1):
        if i == 0 and j == 0:
            continue
        smax = min(f-(j*a+i*b)*100,(j*a+i*b)*e)
        sm = 0
        for k in range((smax//d)+1):
            sm = max(sm, k*d+c*((smax-(k*d))//c))
        if ratio <= sm/((j*a+i*b)*100+sm):
            ratio = sm/((j*a+i*b)*100+sm)
            w = (j*a+i*b)*100
            s = sm


print("%i %i" %(w+s,s))
### BUGGY CODE ###

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

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

### FIXED CODE ###

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

A.sort()

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

def choose(n,a,mod):
    x, y = 1, 1
    for i in range(a):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    return x * pow(y, mod - 2, mod) % mod

k = int(input())
n = len(input())
mod = pow(10,9)+7
start = 1
ans = start*pow(26,k,mod)
for i in range(1,k+1):
    start *= (i+n-1)*pow(i,mod-2,mod)
    start %= mod
    ans += (start*pow(25,i,mod)*pow(26,k-i,mod))
    ans %= mod
print(ans)

### FIXED CODE ###

def choose(n,a,mod):
    x, y = 1, 1
    for i in range(a):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    return x * pow(y, mod - 2, mod) % mod

k = int(input())
n = len(input())
mod = pow(10,9)+7
start = 1
ans = start*pow(26,k,mod)
for i in range(1,k+1):
    start *= (i+n-1)*pow(i,mod-2,mod)
    start %= mod
    ans += (start*pow(25,i,mod)*pow(26,k-i,mod))
    ans %= mod
print(ans)
### BUGGY CODE ###

from collections import Counter
s = input()
MOD = 2019
ts = [0]
cur = 0
for i, j in enumerate(s[::-1], 1):
    cur = (cur + 10**i % MOD * int(j)) % MOD
    ts.append(cur)
ct = Counter(ts)
res = 0
for k, v in ct.items():
    if v > 1:
        res += v * (v-1) // 2
print(res)

### FIXED CODE ###

from collections import Counter
s = input()
MOD = 2019
ts = [0]
cur = 0
for i, j in enumerate(s[::-1], 1):
    cur = (cur + pow(10, i, MOD) * int(j)) % MOD
    ts.append(cur)
ct = Counter(ts)
res = 0
for k, v in ct.items():
    if v > 1:
        res += v * (v-1) // 2
print(res)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

N = int(input())

if N%2 != 0 : 
    print(0)
    
else : 
    global_cnt = 0
    
    for i in range(10, N+1, 10) : 
        mod = 0
        local_cnt = 0
        while(mod == 0) : 
            if i % 5 == 0 : 
                i = int(i/5)
                local_cnt += 1
            else : 
                mod = i % 5
        global_cnt += local_cnt
        
    print(global_cnt)

### FIXED CODE ###

# coding: utf-8
# Your code here!

N = int(input())

if N%2 != 0 : 
    global_cnt = 0
else : 
    n = 1
    while 2*(5**n) <= N : 
        n += 1
        
    global_cnt = 0
    
    for i in range(1, n) : 
        local_cnt = N // (2*(5**i))
        global_cnt += local_cnt
        
print(global_cnt)
### BUGGY CODE ###


a,s,d,f=map(int,input().split())
dp=[[0]*(f+1) for i in range(d+1)]
dp[a][s]=1
mod=998244353

for x in range(a,d+1):
    for y in range(s,f+1):
        if x==a and y==s:continue
        dp[x][y]=(dp[x-1][y]*y+dp[x][y-1]*x-dp[x-1][y-1]*(x-1)*(y-1))%mod
        
print(dp[d][f])


### FIXED CODE ###


a,s,d,f=map(int,input().split())
dp=[[0]*(f+1) for i in range(d+1)]
dp[a][s]=1
mod=998244353

for x in range(a,d+1):
    for y in range(s,f+1):
        if x==a and y==s:continue
        dp[x][y]=(dp[x-1][y]*y+dp[x][y-1]*x-dp[x-1][y-1]*(x-1)*(y-1))%mod
        
print(dp[d][f])
### BUGGY CODE ###

N = int(input())
S = input()

rtn = N 

def count_change(func, s): 
    return len(list(filter(func, s)))

for i in range(N):
    west_change = count_change(lambda x: x=="W", S[:i]) 
    east_change = count_change(lambda x:x=="E", S[i+1:])
    change_num = west_change + east_change
    if change_num < rtn and change_num!=0:    
        rtn = change_num

print(rtn)

### FIXED CODE ###

N = int(input())
S = input()

lE = [0] * N
lW = [0] * N
le = lw = 0
for i in range(N):
    if S[i] == "E":
        le += 1
    else:
        lw += 1
    lE[i] = le
    lW[i] = lw

rtn = lE[-1] - lE[0]

for i in range(1, N):
    tmp = lW[i-1] + lE[-1] - lE[i]
    if tmp <= rtn:
        rtn = tmp


print(rtn)