Harryxun/stf_run huggingface dataset:
n,a,b,k=[int(i) for i in input().split()]
c=a+b
mod=998244353
ans=0

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

for i in range(2,300000):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#以下のcom関数を用いて組み合わせを計算
def com(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

#test=2*3*com(4, 2, mod) + com(4,3,mod)
#print(test)

for i in range(n+1):
    if (k-b*i)%a==0 and k-b*i>=0:
        n_a=(k-b*i)//a
        n_b=i
#        print(n_a, n_b)
        
        n_c=min(n_a,n_b)
        n_a, n_b=n_a-min(n_a,n_b), n_b-min(n_a,n_b)
#        print(n_a, n_b, n_c)

        while n_a + n_b + n_c <=n and n_c>=0 and n_b>=0 and n_a>=0:
            ans+=com(n, n_c, mod) * com(n-n_c, n_b, mod) * com(n-n_c-n_b, n_a, mod)
            n_c-=1
            n_b+=1
            n_a+=1
print(ans%mod)

### FIXED CODE ###

n,a,b,k=[int(i) for i in input().split()]
c=a+b
mod=998244353
ans=0

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

for i in range(2,300003):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#以下のcom関数を用いて組み合わせを計算
def com(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

for i in range(n+1):
    if (k-b*i)%a==0 and k-b*i>=0:
        n_a=(k-b*i)//a
        n_b=i
        if  max(n_a, n_b) <=n:
            ans+=com(n, n_a, mod) * com(n, n_b, mod)  %mod

print(ans%mod)
A, B, C = map(int, input().split())
if A + B*2 >= C:
    print('Yes')
else:
    print(No)


### FIXED CODE ###

A, B, C = map(int, input().split())
if A + B >= C:
    print('Yes')
else:
    print('No')
n = raw_input()
print (n*(n-1)/2)


### FIXED CODE ###

n = int(raw_input())
print (n*(n+1)/2)
N = int(input)
n = N / 2
print(str(n / N))

### FIXED CODE ###

N = int(input())
if(N % 2 == 0):
  n = N // 2
else:
  n = (N + 1) // 2
print(str(n / N))
n=int(input())
s=input()
x=ans=0
for i in range(n):
    if s[i]=='I':
        x=x+1
    elif s[i]=='D':
        x=x-1
    ans=max(ans,x)
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
x=ans=0
for i in range(n):
    if s[i]=='I':
        x=x+1
    elif s[i]=='D':
        x=x-1
    ans=max(ans,x)
print(ans)
# -*- coding: utf-8 -*-

a = raw_input()
if a<1200:
    print"ABC"
else:
    if a<2800:
    print"ARC"
    else:
        print"AGC"


### FIXED CODE ###

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

a = raw_input()
r=int(a)
if r<=1199:
    print'ABC'
elif r<=2799:
    print'ARC'
else:
    print'AGC'
import str
print(input().translate(str.maketrans({"1":9,"9":1})))

### FIXED CODE ###

print(input().translate(str.maketrans({"1":"9","9":"1"})))
def print_solve(ans):
    if "negative" in ans:
        print("NEGATIVE CYCLE")
    else:
        for l in ans:
            for c in l[:-1]:
                if c == float("inf"):
                    print("INF",end=" ")
                else:
                    print(c,end=" ")
            print(l[-1])

def solve(graph_data, num_v):
    ans = []

    for i in range(num_v):
        ans.append(partial_solve(graph_data, i, num_v))

    return ans

def partial_solve(graph_data, source, num_v):
    ans = [0 if i == source else float('inf') for i in range(num_v)]

    i = 0
    while (ans != solver_iteration(graph_data, ans)):
        ans = solver_iteration(graph_data, ans)
        i += 1
        if i >= num_v:
            return "negative"

    return ans

def solver_iteration(graph_data, prev_ans):
    new_ans = prev_ans[0:]

    for i, v in enumerate(new_ans):
        if v == float('inf'):
            continue

        for t, w in graph_data[i]:
                new_ans[t] = min(new_ans[t], v + w)

    return new_ans

def main():
    l = input().split()
    V = int(l[0])
    E = int(l[1])

    graph = {}
    for i in range(E):
        l = input().split()
        s = int(l[0])
        t = int(l[1])
        d = int(l[2])

        if s in graph:
            graph[s].append((t,d))
        else:
            graph[s] = [(t,d)]

    print_solve(solve(graph, V))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def print_solve(ans):
    if "negative" in ans:
        print("NEGATIVE CYCLE")
    else:
        for l in ans:
            for c in l[:-1]:
                if c == float("inf"):
                    print("INF",end=" ")
                else:
                    print(c,end=" ")
            if l[-1] == float("inf"):
                print("INF")
            else:
                print(l[-1])

def solve(graph_data, num_v):
    ans = []

    for i in range(num_v):
        ans.append(partial_solve(graph_data, i, num_v))

    return ans

def partial_solve(graph_data, source, num_v):
    ans = [0 if i == source else float('inf') for i in range(num_v)]

    i = 0
    while (ans != solver_iteration(graph_data, ans)):
        ans = solver_iteration(graph_data, ans)
        i += 1
        if i >= num_v:
            return "negative"

    return ans

def solver_iteration(graph_data, prev_ans):
    new_ans = prev_ans[0:]

    for i, v in enumerate(new_ans):
        if v == float('inf') or i not in graph_data:
            continue

        for t, w in graph_data[i]:
                new_ans[t] = min(new_ans[t], v + w)

    return new_ans

def main():
    l = input().split()
    V = int(l[0])
    E = int(l[1])

    graph = {}
    for i in range(E):
        l = input().split()
        s = int(l[0])
        t = int(l[1])
        d = int(l[2])

        if s in graph:
            graph[s].append((t,d))
        else:
            graph[s] = [(t,d)]

    print_solve(solve(graph, V))

if __name__ == "__main__":
    main()
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    s = list(input())
    q = int(input())
    s.pop(-1)
    a = [''] * (10**5*2)
    a.append(*s)
    a.extend([''] * (10**5*2))
    start = 10**5*2
    end = start + len(s) - 1
    for i in range(q):
        query = input().split()
        if query[0] == '1':
            tmp = a[start]
            a[start] = a[end]
            a[end] = tmp
        elif query[0] == '2':
            if query[1] == '1':
                a[start-1] = query[2]
                start -= 1
            elif query[1] == '2':
                a[end+1] = query[2]
                end += 1
    print(''.join(a[start:end+1]))


main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    s = str(input())
    q = int(input())
    s = s.strip()
    a = [''] * (10**5*2)
    a.extend(list(s))
    a.extend([''] * (10**5*2))
    start = 10**5*2
    end = start + len(s) - 1
    frip = False
    for i in range(q):
        query = input().split()
        if query[0] == '1':
            frip = not frip
        elif query[0] == '2':
            if (query[1] == '1' and frip == False) or (query[1] == '2' and frip == True):
                a[start-1] = query[2]
                start -= 1
            else:
                a[end+1] = query[2]
                end += 1
    if frip:
        a.reverse()
        tmp = end
        end = len(a)-start-1
        start = len(a)-tmp-1
    print(''.join(a[start:end+1]))


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

#Y = len(S.replace('ABC',''))
#print((N-Y)//3)

print(S.count('ABC'))


### FIXED CODE ###

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

if 500* K >= X:
    print('Yes')
else:
    print('No')
k, n = map(int, input().split())
list_a = list(map(int, input().split()))

x = 0
longest = 0
for a in list_a:
  if a - x > longest:
    longest = a - x
    x = a - x
if longest < a[0] + (k - a[n-1]):
  longest = a[0] + (k - a[n-1]):
print(k-longest)

### FIXED CODE ###

k, n = map(int, input().split())
list_a = list(map(int, input().split()))
 
x = 0
longest = 0
for a in list_a:
  if a - x > longest:
    longest = a - x
  x = a
if longest < list_a[0] + (k - list_a[n-1]):
  longest = list_a[0] + (k - list_a[n-1])
print(k-longest)
a, b, c, x = map(int, open(0).read().split())
ans = 0
for i in range(a + 1):
  for j in range(b + 1):
    if (x - (i * 500 + j * 100)) % (c * 50) == 0:
      ans += 1
print(ans)

### FIXED CODE ###

a, b, c, x = map(int, open(0).read().split())
ans = 0
for i in range(a + 1):
  for j in range(b + 1):
    for k in range(c + 1):
      if 500 * i + 100 * j + 50 * k == x:
        ans += 1
print(ans)
def acinput():
    return list(map(int,input().split(" ")))


N,M=acinput()
a=[0]*(N+1)
for i in range(N):
    a[int(input())]=1


M=1000000007

def solve(x):
    global dp,M
    if dp[x]>=0:
        return dp[x]

    res=0
    zeroflg=True
    if  a[x-1]!=1:
        res+=solve(x-1)%M
        zeroflg=False
    if a[x-2]!=1:
        res+=solve(x-2)%M
        zeroflg=False
    
    if zeroflg:
        return 0
    dp[x]=res
    return res

dp=[-1]*(N+1)
dp[0]=1
dp[1]=1

print(solve(N)%M)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def acinput():
    return list(map(int, input().split(" ")))


N, M = acinput()
a = [0]*(N+1)
for i in range(M):
    a[int(input())] = 1


Mod = 1000000007


def solve(x):
    global dp, Mod
    if dp[x] >= 0:
        return dp[x]

    if x < 0:
        return 0

    res = 0
    zeroflg = True

    if  a[x-2] != 1:
        res += solve(x-2) 
        zeroflg = False

    if a[x-1] != 1:
        res += solve(x-1)
        zeroflg = False

    if zeroflg:
        return 0
    dp[x] = res% Mod
    return res


dp = [-1]*(N+1)
dp[0] = 1
dp[1] = 1

print(solve(N) % Mod)


'''
5 1
1
'''
N,M=map(int,input().split())
# N:売店数
# M:買う数
AB=[]
for i in range(N):
  ab=list(map(int,input().split()))
  AB.append(ab)
#AB[0]:A円，AB[1]:最大B本まで買える

list.sort(AB,key=lambda x:x[0])
#print(AB)

m=0 #買う数
cost=0 #かかる値段
for i in range(N):
 
 if M-m==A[i][1]
 m+=A[i][1]
 cost+=AB[i][0]*AB[i][1]
 break

 elif M-m<A[i][1] :
      for j in range(AB[i][1]+1):
         cost=cost+AB[i][0]*j
         m=m+j
         if m==M:
             break

 cost+=AB[i][0]*AB[i][1]
 m+=A[i][1]
    
print(cost)

### FIXED CODE ###

N,M=map(int,input().split())
# N:売店数
# M:買う数
AB=[]
for i in range(N):
  ab=list(map(int,input().split()))
  AB.append(ab)
#AB[0]:A円，AB[1]:最大B本まで買える

list.sort(AB,key=lambda x:x[0])
#print(AB)

m=0 #買う数
cost=0 #かかる値段
for i in range(N):
 
 if M-m==AB[i][1]:
     m+=AB[i][1]
     cost+=AB[i][0]*AB[i][1]
     break
 elif M-m<AB[i][1] :
      for j in range(AB[i][1]+1):
         cost=cost+AB[i][0]*j
         m=m+j
         if m==M:
             break
         elif m<M:
             cost=cost-AB[i][0]*j
             m=m-j
 else:
      cost+=AB[i][0]*AB[i][1]
      m+=AB[i][1]
    
print(cost)
def main():
	# a,b,k = map(int,input().split())
	# n,k = map(int,input().split())
	s = list(str(input()))
	# a = list(map(int,input().split()))
	# rsp = list(str(input()))
	# l = [list(map(int, input().split())) for _ in range(n-1)]
	# s = list(s)
	avoid = 0
	ans = 0
	ans_rec = []
	for i in range(len(s)):
		if s[i] == "A" or s[i] == "T" or s[i] == "G" or s[i] == "C":
			# print("when i = {} is true".format(i))
			ans += 1
		else:
			ans_rec.append(ans)
			ans = 0
			
	print(max(ans_rec))

 
if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	# a,b,k = map(int,input().split())
	# n,k = map(int,input().split())
	s = list(str(input()))
	# a = list(map(int,input().split()))
	# rsp = list(str(input()))
	# l = [list(map(int, input().split())) for _ in range(n-1)]
	# s = list(s)
	avoid = 0
	ans = 0
	ans_rec = []
	for i in range(len(s)):
		if s[i] == "A" or s[i] == "T" or s[i] == "G" or s[i] == "C":
			# print("when i = {} is true".format(i))
			ans += 1
		else:
			ans_rec.append(ans)
			ans = 0
	ans_rec.append(ans)
			
	print(max(ans_rec))

 
if __name__ == '__main__':
	main()
A, B, K = map(int, input().split())
n = max(A, B)
list1 =[]
count = 0
for i in range(1, n):
  if A % i == 0 and B % i == 0:
    list1.append(i)
list1 = list1[::-1]
if K == 1:
  print("1")
else:
  print(list1[K-1])

### FIXED CODE ###

A, B, K = map(int, input().split())
n = min(A, B)
list1 =[]
for i in range(1, n+1):
  if A % i == 0 and B % i == 0:
    list1.append(i)
list1 = list1[::-1]
print(list1[K-1])
M = [int(input()) for i in range(5)]
T = M[:]
tmp = 10
for i in range(5):
  if tmp > M[i] % 10 > 0:
    tmp = M[i] % 10
    c = i
  if M[i] % 10 != 0:
    M[i] += 10 - (M[i] % 10)
M[c] = T[c]
print(sum(M))

### FIXED CODE ###

M = [int(input()) for i in range(5)]

a = [((i - 1) // 10 + 1) * 10 for i in M]
b = [(i - 1) % 10 for i in M]

ans = sum(a) + min(b) - 9
print(ans)
from math import gcd


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


def counter(n, a):
    return n // a


a, b, c, d = map(int, input().split())
l = lcm(c, d)
print(b - a + 1 - (counter(b, c) - counter(a - 1, c) +
                   counter(b, d) - counter(a - 1, d) -
                   (counter(b, l) - counter(a - 1, l))))


### FIXED CODE ###

from fractions import gcd


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


def counter(n, a):
    return n // a


a, b, c, d = map(int, input().split())
l = lcm(c, d)
print(b - a + 1 - (counter(b, c) - counter(a - 1, c) +
                   counter(b, d) - counter(a - 1, d) -
                   (counter(b, l) - counter(a - 1, l))))
X, Y, Z, K = map(int, input().split())
candy = [[],[],[]]
for i in range(3):
    temp = list(map(int, input().split()))
    candy[i] = temp

for i in range(3):
    candy[i] = sorted(candy[i], reverse=True)
i, j, k = 0, 0, 0
heap = [(-(candy[0][i] + candy[1][j] + candy[2][k]), i, j, k)]
cnt = 0
visit = {(i, j, k)}
while cnt < K:
    s, ii, jj, kk = heapq.heappop(heap)
    print(-s)
    cnt += 1
    if ii < len(candy[0]) - 1 and (ii+1, jj, kk) not in visit:
        heapq.heappush(heap, (-(candy[0][ii + 1] + candy[1][jj] + candy[2][kk]), ii + 1, jj, kk))
        visit.add((ii+1, jj, kk))
    if jj < len(candy[1]) - 1 and (ii, jj+1, kk) not in visit:
        heapq.heappush(heap, (-(candy[0][ii] + candy[1][jj + 1] + candy[2][kk]), ii, jj + 1, kk))
        visit.add((ii, jj+1, kk))
    if kk < len(candy[2]) - 1 and (ii, jj, kk+1) not in visit:
        heapq.heappush(heap, (-(candy[0][ii] + candy[1][jj] + candy[2][kk + 1]), ii, jj, kk + 1))
        visit.add((ii, jj, kk+1))

### FIXED CODE ###

import heapq
X, Y, Z, K = map(int, input().split())
candy = [[],[],[]]
for i in range(3):
    temp = list(map(int, input().split()))
    candy[i] = temp

for i in range(3):
    candy[i] = sorted(candy[i], reverse=True)
i, j, k = 0, 0, 0
heap = [(-(candy[0][i] + candy[1][j] + candy[2][k]), i, j, k)]
cnt = 0
visit = {(i, j, k)}
while cnt < K:
    s, ii, jj, kk = heapq.heappop(heap)
    print(-s)
    cnt += 1
    if ii < len(candy[0]) - 1 and (ii+1, jj, kk) not in visit:
        heapq.heappush(heap, (-(candy[0][ii + 1] + candy[1][jj] + candy[2][kk]), ii + 1, jj, kk))
        visit.add((ii+1, jj, kk))
    if jj < len(candy[1]) - 1 and (ii, jj+1, kk) not in visit:
        heapq.heappush(heap, (-(candy[0][ii] + candy[1][jj + 1] + candy[2][kk]), ii, jj + 1, kk))
        visit.add((ii, jj+1, kk))
    if kk < len(candy[2]) - 1 and (ii, jj, kk+1) not in visit:
        heapq.heappush(heap, (-(candy[0][ii] + candy[1][jj] + candy[2][kk + 1]), ii, jj, kk + 1))
        visit.add((ii, jj, kk+1))
import numpy as np

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
table = np.zeros(w+1, dtype=np.int64)

for i in range(n):
    l = table[:-wv[i][0]]
    r = table[wv[i][0]:]
    np.maximum(l + wv[i][1], r, out = r)

print(table[w])

### FIXED CODE ###

import numpy as np

n, W = map(int, input().split())
w, v = [],[]
for i in range(n):
    temp = list(map(int, input().split()))
    w.append(temp[0])
    v.append(temp[1])

table = np.full(sum(v)+1, np.inf)
table[0] = 0

for i in range(n):
    l = table[:-v[i]]
    r = table[v[i]:]
    np.minimum(l + w[i], r, out = r)
    
print(np.max(np.where(table <= W)))
import numpy as np 

N=int(input())
t=[0]*N
x=[0]*N
y=[0]*N
for i in range(N):
  t[i],x[i],y[i]=map(int,input().split())
  
def traveling(t,x,y):
  time_i=0
  for i,time in enumerate(t):
    time_i=time-time_i
    z=x[i]+y[i]
    if (t-z)%2==0:
      return "Yes"
    else:
      return "No"
    time_i=time
    
print("{}".format(traveling(t,x,y)))
     
  

### FIXED CODE ###

N=int(input())
t=[0]*N
x=[0]*N
y=[0]*N
for i in range(N):
  t[i],x[i],y[i]=map(int,input().split())
  
def traveling(t,x,y):
  time_i=0
  x_i=0
  y_i=0
  for i,time in enumerate(t):
    time_i=time-time_i
    x_i=x[i]-x_i
    y_i=y[i]-y_i
    z=x_i+y_i
    if (time_i-z)%2!=0 or z>time_i:
      return "No"
    time_i=time
    x_i=x[i]
    y_i=y[i]
  return "Yes"
    
print("{}".format(traveling(t,x,y)))
from math import factorial as fc

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

for i in range(1,k+1):
    bl=n-k+1
    br=i
    b=fc(bl)//(fc(br)*fc(bl-br))
    rl=k-1
    rr=i-1
    r=fc(rl)//(fc(rr)*fc(rl-rr))
    print(b*r%(10**9+7))



### FIXED CODE ###

from math import factorial as fc

MOD=10**9+7
n,k=map(int,input().split())

for i in range(1,k+1):
    if n-k+1<i:
        print(0)
        continue
    b=fc(n-k+1)//fc(i)//fc(n-k+1-i)
    r=fc(k-1)//fc(i-1)//fc(k-1-(i-1))
    print(b%MOD*r%MOD)
a=[]

for i in range(6):
    a.append(int(input())

a=sort(a)
if(a[4]-a[0]>a[5]):
    print(':(')
else:
    print('Yay!')

### FIXED CODE ###

a=[]

for i in range(5):
    a.append(int(input()))

k=int(input())
for i in range(5):
    for j in range(5):
        if(i==j):
            continue
        else:
            if(abs(a[i]-a[j])>k):
                print(':(')
                exit()

print('Yay!')
def check(x, y, K, S):
  for z in range(K+1):
    if x + y + z == S:
      return true
  return false

K, S = list(map(int, input('').split()))
count = 0
for x in range(K+1):
  for y in range(K+1):
    if check(x, y, K, S):
      count += 1
print(count)

### FIXED CODE ###

K, S = list(map(int, input('').split()))
count = 0
for x in range(K+1):
  for y in range(K+1):
    if x + y <= S and x + y + K >= S:
      count += 1
print(count)
cand = list(set([2**x * 5**y for x in range(18) for y in range(8) if 2**x * 5**y <= 200000]))
cand.sort()


def f(n):
    cnt = 0
    while True:
        x = n * cand[cnt]
        if x.is_integer():
            return cand[cnt]
        else:
            cnt += 1


def div(n, bl=True):
    if bl and not n.is_integer():
        return (0, 0)
    else:
        n = int(n)
        two = format(n, 'b')[::-1].find('1')
        n = n >> two
        cnt = 0
        while n % 5 == 0:
            n //= 5
            cnt += 1
        return (two, cnt)


n = int(input())
arr = [float(input()) for _ in range(n)]
arr = [x for x in arr if min(x - int(x), math.ceil(x) - x) >= 0.000005 or x == int(x)]

x = [div(x) for x in arr]
y = [div(x, False) for x in [f(x) for x in arr]]
z = [div(x * 2**y1 * 5**z, False) for x, (y1, z) in zip(arr, y)]


ans = 0
for i in range(len(y)):
    for j in range(i + 1, len(y)):
        (a, b), (c, d) = y[i], y[j]
        if a == 0 and b == 0 and c == 0 and d == 0:
            ans += 1
        elif a + c <= z[i][0] + z[j][0] and b + d <= z[i][1] + z[j][1]:
            ans += 1

print(ans)

### FIXED CODE ###

def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]

ans = 0
for _ in range(n):
    x = round(float(input()) * pow(10, 9))
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

print(ans)
import math
L = []
N,X = map(int,input().split())
L = list(map(int,input().split()))
L.append(X)
L = sorted(L)
D = []
for i in range(len(L)) :
    d = abs(L[i-1] - L[i])
    D.append(d)

D = sorted(D)
if N != 1 :
    answer = math.gcd(D[0],D[1])
    for j in range(len(D)-1) :
        gcd = math.gcd(D[j],D[j+1])
        if answer > gcd :
            answer = gcd
else :
    answer = D[0]
print(answer)



### FIXED CODE ###

N, X = map(int, input().split())
A = list(map(int, input().split()))
diff = [abs(a - X) for a in A]

# 最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


while len(diff) > 1:
    a, b = diff.pop(), diff.pop()
    diff.append(gcd(a, b))

print(diff[0])
def get_lcs(S: str, T: str):
    N, M = len(S), len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    reversed_lcs = ""
    while N and M:
        if S[N - 1] == T[M - 1]:
            N -= 1
            M -= 1
            reversed_lcs += S[N]
        if dp[N - 1][M] > dp[N][M - 1]:
            N -= 1
        else:
            M -= 1
    return reversed_lcs[::-1]


def main():
    S, T = open(0).read().split()
    print(get_lcs(S, T))


if __name__ == "__main__":
    main()


### FIXED CODE ###

# dpF - LCS
def main():
    S, T = tuple(input().rstrip() for _ in range(2))
    n, m = len(S), len(T)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if S[i - 1] == T[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
    ans = []
    while n > 0 and m > 0:
        if dp[n][m] == dp[n - 1][m]:
            n -= 1
        elif dp[n][m] == dp[n][m - 1]:
            m -= 1
        else:
            n -= 1
            m -= 1
            ans += [S[n]]
    print(*ans[::-1], sep="")


if __name__ == "__main__":
    main()
#!/usr/bin/env python

S = raw_input()

def func(lst):
    if type(lst) == type(0):
        return True
    if len(lst) > 2:
        return False
    ret = True
    for l in lst:
        ret = (ret or func(l))
    return ret

S = S.replace('mew', '[1]')
S = S.replace('me', 'm[1]e')
S = S.replace('m', '[')
S = S.replace('e', ',')
S = S.replace('w', ']')

try:
    exec('piyo = ' + S)
except:
    print 'Rabbit'
    exit()
if func(piyo):
    print 'Cat'
else:
    print 'Rabbit'



### FIXED CODE ###

#!/usr/bin/env python

S = raw_input()

S = S.replace('mew', '[1]')
S = S.replace('me', 'm[1]e')
S = S.replace('ew', 'e[1]w')
S = S.replace('m', '[')
S = S.replace('e', ',')
S = S.replace('w', ']')

for i in range(500):
    S = S.replace('[[1],[1]]', '[1]')

if S == '[1]' or S == '':
    print 'Cat'
else:
    print 'Rabbit'
n = int(input())
li = list(int(input()) for i in range(n))

for i in range(n):
  li_copy = li.copy()
  del li_copy[i]
  print(max(li_copy))

### FIXED CODE ###

n = int(input())
li = list(int(input()) for i in range(n))

sorted_li = sorted(li)
a, b = sorted_li[-1], sorted_li[-2]

for i in li:
  if i == a:
    print(b)
  else:
    print(a)
a = int(input())

while math.sqrt(a) % 1 != 0:
  a -= 1
  
print(a)

### FIXED CODE ###

import math
a = int(input())

res = 1
for i in range(2, a):
    for j in range(2, a):
        if i ** j <= a:
            res = max(res, i**j)
        else:
            break
print(res)