Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

DIV_NUM = 1000000000 + 7

INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])

A = [int(x) for x in input().split()]
AA = np.array(A)
if N==1:
    print(0)
    exit()

tree = np.array([0] * (N+1) )

# https://atcoder.jp/contests/chokudai_S001/submissions/6789704
def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        x += x&(-x)
def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x&(-x)
    return s

answer = N*(N-1)//2
for x in AA:
    answer -= BIT_sum(tree,x)
    BIT_update(tree,x)

B = sorted(A)

q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r

# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)



### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

DIV_NUM = 1000000000 + 7

INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])

A = [int(x) for x in input().split()]
AA = np.array(A)
if N==1:
    print(0)
    exit()

# https://kira000.hatenadiary.jp/entry/2019/02/23/053917
def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                cnt += 1
    return cnt

answer = bubble_sort(AA)

B = sorted(A)
q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r

# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    H,W,M = LI()
    t = [LI() for _ in range(M)]

    hmax = [0] * (M+1)
    wmax = [0] * (M+1)

    for x,y in t:
        hmax[x] += 1
        wmax[y] += 1

    ans = 0
    for x,y in t:
        ans = max(ans,hmax[x] + wmax[y] - 1)

    hm = max(hmax)
    wm = max(wmax)

    for i in range(H):
        if hmax[i] == hm:
            for j in range(W):
                if wmax[j] == wm:
                    if [i,j] not in t:
                        print(hm+wm)
                        return
    print(hm+wm-1)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    H,W,M = LI()
    t = [LI() for _ in range(M)]

    hmax = [0] * (H+1)
    wmax = [0] * (W+1)

    for x,y in t:
        hmax[x] += 1
        wmax[y] += 1

    ans = 0

    hm = max(hmax)
    wm = max(wmax)

    xcnt = 0
    ycnt = 0
    for x in range(H+1):
        if hmax[x] == hm:
            xcnt += 1
    for y in range(W+1):
        if wmax[y] == wm:
            ycnt += 1

    cnt = 0
    for x,y in t:
        if hmax[x] == hm and wmax[y] == wm:
            cnt += 1
    if xcnt *  ycnt - cnt:
        print(hm + wm)
    else:
        print(hm+wm-1)


if __name__ == '__main__':
    main()
n = int(input())
h = [int(i) for i in input().split()]
count = 0
c_list = []
for i in range(n-1):
    if h[i]>=h[i+1]:
        count +=1
    else:
        c_list.append(count)
        count= 0
print(max(max(c_list), count))

### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split()]
count = 0
c_list = [0]
try:
    for i in range(n-1):
        if h[i]>=h[i+1]:
            count +=1
        else:
            c_list.append(count)
            count= 0
except:
    a =1
print(max(max(c_list), count))
# B - Frog2
import numpy as np

N, K = list(map(int, input().split()))
h = list(map(int, input().split()))
dp = [10**9]*N

dp[0] = 0

for i in range(N-1):
    if i+K+1 <= N-1:
        for j in range(i+1, i+K+1):
            dp[j] = min(dp[j], dp[i]+abs(h[j]-h[i]))
    else:
        for j in range(i+1, N):
            dp[j] = min(dp[j], dp[i]+abs(h[j]-h[i]))
print(dp[N-1])

### FIXED CODE ###

# B - Frog2
import numpy as np

N, K = list(map(int, input().split()))
h = np.array(list(map(int, input().split()))+[0]*K)

dp = np.array([10**9]*(N+K))
dp[0] = 0

for i in range(N):
    dp[i+1:i+K+1] = np.minimum(dp[i+1:i+K+1], dp[i]+abs(h[i+1:i+K+1]-h[i]))
print(dp[N-1])
dic = {}
h, w, d = map(int, input().split())
lis = [list(input().split()) for _ in range(h)]
for i in range(h):
    for j in range(w):
        dic[int(lis[i][j])] = (i, j)
#print(dic)
n = h * w
su = [0] * n
for k in range(1, n - d):
    x = dic[k + d][0] - dic[k][0]
    y = dic[k + d][1] - dic[k][1]
    su[k + d] = su[k] + abs(x) + abs(y)
#print(su)

q = int(input())
for i in range(q):
    s, g = map(int, input().split())
    print(su[g] - su[s])


### FIXED CODE ###

dic = {}
h, w, d = map(int, input().split())
lis = [list(input().split()) for _ in range(h)]
for i in range(h):
    for j in range(w):
        dic[int(lis[i][j])] = (i, j)
n = h * w
su = [0] * (n + 1)
for k in range(1, n - d + 1):
    x = dic[k + d][0] - dic[k][0]
    y = dic[k + d][1] - dic[k][1]
    su[k + d] = su[k] + abs(x) + abs(y)

q = int(input())
for i in range(q):
    s, g = map(int, input().split())
    print(su[g] - su[s])
import sys

if __name__ == "__main__":
    C1 = list(map(int, (input().split(' '))))
    C2 = list(map(int, (input().split(' '))))
    C3 = list(map(int, (input().split(' '))))

    for i in range(100, 101):
        for j in range(100, 101):
            for k in range(100, 101):
                col1 = C1[0] - i
                if col1 < 0:
                    break
                if col1 > 100:
                    break
                if (C2[0] - j) != col1:
                    break
                if (C3[0] - k) != col1:
                    break
                col2 = C1[1] - i
                if col2 < 0:
                    break
                if col2 > 100:
                    break
                if (C2[1] - j) != col2:
                    break
                if (C3[1] - k) != col2:
                    break
                col3 = C1[2] - i
                if col3 < 0:
                    break
                if col3 > 100:
                    break
                if (C2[2] - j) != col3:
                    break
                if (C3[2] - k) != col3:
                    break
                print('Yes')
                sys.exit()
    print('No')

### FIXED CODE ###

if __name__ == "__main__":
    N = int(input())
    A = int(input())
    remain = N % 500
    if remain <= A:
        print('Yes')
    else:
        print('No')
n,ma,mb=map(int,input().split())
abc=[]
for i in range(n):
    abc.append([int(j) for j in input().split()])

from operator import itemgetter
abc.sort(key=itemgetter(2))

dp=[[10**100 for i in range(401)]for j in range(401)]
dp[0][0]=0
from collections import deque
q=deque([(0,0)])
p=0
for a,b,c in abc:
    l=[]
    while q:
        i,j=q.popleft()
        l.append([i,j])
        l.append([i+a,j+b])
        dp[a+i][b+j]=min(dp[a+i][b+j],dp[i][j]+c)
    q=deque(l)

ans=1145141919
i=1
while ma*i<500 and mb*i<500:
    ans=min(ans,dp[ma*i][mb*i])
    i+=1
if ans==1145141919:
    print(-1)
else:
    print(ans)





### FIXED CODE ###

n,ma,mb=map(int,input().split())
abc=[]
for i in range(n):
    abc.append([int(j) for j in input().split()])
from operator import itemgetter
abc.sort(key=itemgetter(2))

dp=[[10**18 for i in range(401)]for j in range(401)]
dp[0][0]=0

p,q=0,0
for a,b,c in abc:
    for j in reversed(range(q+1)):
        for i in range(p+1):
            if dp[i][j]==10**18:
                continue
            else:
                dp[i+a][j+b]=min(dp[i+a][j+b],dp[i][j]+c)
    p+=a
    q+=b

ans=1145141919
i=1
while ma*i<401 and mb*i<401:
    ans=min(ans,dp[ma*i][mb*i])
    i+=1
if ans==1145141919:
    print(-1)
else:
    print(ans)
mport sys

while 1:
    H,W = map(int, raw_input().split())

    if H == 0 and W == 0:
        break

    for i in range(H):
        for j in range(W):

            if i%2 == 0:
                if j%2 == 0:
                    sys.stdout.write("#")
                else:
                    sys.stdout.write(".")

                if j == W-1:
                    print ""

            if i%2 != 0:
                if j%2 != 0:
                    sys.stdout.write("#")
                else:
                    sys.stdout.write(".")

                if j == W-1:
                    print ""

        if i == H-1:
            print ""

### FIXED CODE ###

import sys

while 1:
    H,W = map(int, raw_input().split())

    if H == 0 and W == 0:
        break

    for i in range(H):
        for j in range(W):

            if i%2 == 0:
                if j%2 == 0:
                    sys.stdout.write("#")
                else:
                    sys.stdout.write(".")

            if i%2 != 0:
                if j%2 != 0:
                    sys.stdout.write("#")
                else:
                    sys.stdout.write(".")

            if j == W-1:
                print ""

    print ""
import sys
from collections import deque
 
 
def bfs(H, W, maze, visited, sharp):
    queue = deque([[0, 0]])
    visited[0][0] = 0
    while queue:
        y, x = queue.popleft()
        if[y, x] == [H-1, W-1]:
            return ((H*W-sharp)-(visited[y][x]+1))
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if  new_y != -1 and new_y != H and  \
                new_x != -1 and new_x != W and  \
                maze[new_y][new_x] == "." and   \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
 
    return -1
 
 
def main():
    sharp = 0
 
    H, W = map(int,input().split())
    maze = [input() for i in range(H)]
    visited = [[-1]*W for j in range(H)]
 
    for k in range(H):
        

### FIXED CODE ###

import sys
from collections import deque


def bfs(H, W, maze, visited, sharp):
    queue = deque([[0, 0]])
    visited[0][0] = 0
    while queue:
        y, x = queue.popleft()
        if[y, x] == [H-1, W-1]:
            return ((H*W-sharp)-(visited[y][x]+1))
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if  new_y != -1 and new_y != H and  \
                new_x != -1 and new_x != W and  \
                maze[new_y][new_x] == "." and   \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])

    return -1












def main():
    sharp = 0

    H, W = map(int,input().split())
    maze = [input() for i in range(H)]
    visited = [[-1]*W for j in range(H)]

    for k in range(H):
        sharp += maze[k].count('#')

    print(bfs(H, W, maze, visited, sharp))

main()
n = int(input())
t = []
a = 0
b = 0
total = 0
for i in range(n):
	t.append(input())
    total += t[-1].count("AB")
    a += t[-1][-1] == "A"
    b += t[-1][0] == "B"
print(min(a,b) + total)

### FIXED CODE ###

n = int(input())
a = 0
b = 0
ab = 0
total = 0
t = []

for i in range(n):
	t.append(input())

for i in t:
	total += i.count("AB")
	if i[-1] == "A" and i[0] == "B":
		ab += 1
	else:
		a += i[-1] == "A"
		b += i[0] == "B"
if ab == 0:
	print(total + min(a,b))
elif a == 0 and b == 0:
	print(total + ab - 1)
elif a > 0 and b > 0:
	print(total + ab + min(a, b))
else:
	print(total + ab)
def exhaustive_search(start, Sum, answer):
    for i in range(start, n):
        Sum = Sum + A[i]
        if Sum == answer:
            return True
        elif Sum > answer:
            Sum = Sum - A[i]
            next
        else:
            r = exhaustive_search(i+1, Sum, answer)
            if r == True:
                return True
            else:
                Sum = Sum - A[i]
    return False


for i in M:
    r = exhaustive_search(0, 0, i)
    if r == True:
        print('yes')
    else:
        print('no')

### FIXED CODE ###

def solve(dp, a, i, m):
  if m in dp[i]:
    return dp[i][m]

  if m == 0:
    dp[i][m] = True
  elif i >= len(a):
    dp[i][m] = False
  elif solve(dp, a, i+1, m):
    dp[i][m] = True
  elif solve(dp, a, i+1, m-a[i]):
    dp[i][m] = True
  else:
    dp[i][m] = False

  return dp[i][m]

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

dp = {}
for i in range(N+1):
  dp[i] = {}

for m in M:
  if solve(dp, A, 0, m):
    print('yes')
  else:
    print('no')
N, K  = map(int,input().split())
L =list(map(int,input().split()))
Lzero = list(filter(lambda x:x==0,L))
Lright = list(filter(lambda x:x>0,L))
Lleft = list(map(lambda x:abs(x),filter(lambda x:x<0,L)))[::-1]
K -= len(Lzero)
if K <= 0:
    print(0)
    quit()

dis = []
if len(Lright) == 0:
    print(Lleft[K-1])
    quit()
if len(Lleft) == 0:
    print(Lright[K-1])
    quit()
dis.append(Lright[K-1])
dis.append(Lleft[K-1])


for i in range(len(Lright)):
    remain = K
    if i+1 >K:
        break
    elif i+1 == K:
        dis.append(Lright[i])
        break
    d = 2*Lright[i]
    remain -= (i+1)
    d += Lleft[remain-1]
    dis.append(d)
for i in range(len(Lleft)):
    remain = K
    if i+1 >K:
        break
    elif i+1 == K:
        dis.append(Lleft[i])
        break
    d = 2*Lleft[i]
    remain -= (i+1)
    d += Lright[remain-1]
    dis.append(d)
print(min(dis))


### FIXED CODE ###

N, K  = map(int,input().split())
L =list(map(int,input().split()))
Lzero = list(filter(lambda x:x==0,L))
Lright = list(filter(lambda x:x>0,L))
Lleft = list(map(lambda x:abs(x),filter(lambda x:x<0,L)))[::-1]
K -= len(Lzero)
if K <= 0:
    print(0)
    quit()

dis = []
if len(Lright) == 0:
    print(Lleft[K-1])
    quit()
if len(Lleft) == 0:
    print(Lright[K-1])
    quit()
try :
    dis.append(Lright[K-1])
    dis.append(Lleft[K-1])
except:
    pass


for i in range(len(Lright)):
    remain = K
    if i+1 >K:
        break
    elif i+1 == K:
        dis.append(Lright[i])
        break
    d = 2*Lright[i]
    remain -= (i+1)
    try :
        d += Lleft[remain-1]
        dis.append(d)
    except:
        pass
for i in range(len(Lleft)):
    remain = K
    if i+1 >K:
        break
    elif i+1 == K:
        dis.append(Lleft[i])
        break
    d = 2*Lleft[i]
    remain -= (i+1)
    try:
        d += Lright[remain-1]
        dis.append(d)
    except:
        pass
print(min(dis))
n=int(input())
a=list(map(int,input().split()))
cnt=0
for i range(n):
  if a[i]%2==0:
    cnt+=1
ans=(3*n)-2*cnt
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt=0
for i in range(n):
  if a[i]%2==0:
    cnt+=1
ans=(3**n)-2**cnt
print(ans)
N, M = map(int, input().split())
As = list(map(int, input().split()))
ones = [1 for _ in range(N)]
for _ in range(M):
  b, c = map(int, input().split())
  Bs.append(b)
  Cs.append(c)
both = list(zip(As, ones))
both.append(list(zip(Cs, Bs)))
both.sort()
a, b = zip(*both)
cnt = 0
out = 0
for k in reversed(range(N+M)):
  if N - cnt > b[k]:
    out += a[k] * b[k]
    cnt += b[k]
  else:
    out += a[k] * (N - cnt)
    break
print(out)

### FIXED CODE ###

N, M = map(int, input().split())
As = list(map(int, input().split()))
ones = [1 for _ in range(N)]
Bs = []
Cs = []
both = list(zip(As, ones))
for _ in range(M):
  b, c = map(int, input().split())
  both.append((c, b))
both.sort()
a, b = zip(*both)
cnt = 0
out = 0
for k in reversed(range(N+M)):
  if N - cnt > b[k]:
    out += a[k] * b[k]
    cnt += b[k]
  else:
    out += a[k] * (N - cnt)
    break
print(out)
def load_balls():
	LINE_NUM, TOTAL = 0, 0
	balls = []
	i = 0
	for line in sys.stdin:
		line = line.strip()
		LINE_NUM += 1
		if LINE_NUM == 1:
			TOTAL = int(line.strip())
			continue
		balls.append([int(i) for i in line.split(" ")])
		if LINE_NUM == TOTAL+1: break
	return balls

class VesselClass:

	def __init__(self):
		self.BALL_NUM = 10
		self.tmp = []
		self.left = [0]
		self.right = [0]

	def fill(self, balls:list):
		self.tmp = balls

	def DFS(self):
		if len(self.tmp) == 0: print("Yes")
		elif self.left[-1] < self.tmp[0]:
			self.left.append(self.tmp[0])
			self.tmp.pop(0)
			self.DFS()
		elif self.right[-1] < self.tmp[0]:
			self.right.append(self.tmp[0])
			self.tmp.pop(0)
			self.DFS()
		else: print("No")

balls_list = load_balls()
Vessel = VesselClass()
for balls in balls_list:
	Vessel.fill(balls)
	Vessel.DFS()

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def load_balls():
	balls = []
	LINE_NUM, TOTAL = 0, 0
	while True:
		line = sys.stdin.readline().strip()
		LINE_NUM += 1
		if LINE_NUM == 1:
			TOTAL = int(line)+1
			continue
		balls.append([int(i) for i in line.split(" ")])
		if LINE_NUM == TOTAL: break
	return balls
balls_list = load_balls()
for balls in balls_list:
	left, right = [0], [0]
	for ball in balls:
		if left[-1] < ball: left.append(ball)
		elif right[-1] < ball: right.append(ball)
	print("YES" if len(left)-1 + len(right)-1 == 10 else "NO")
from functools import lru_cache
N,Q = map(int,input().split())
S = list(input())
LR = [list(map(int,input().split())) for _ in range(Q)]
lis = []

@lru_cache(maxsize=None)
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        lis.append(i)
for i in range(Q):
    ans = 0
    for j in lis:
        if LR[i][0]-1 <= j and j+1 <= LR[i][1]-1:
            ans += 1
        if LR[i][1]-1<j+1:
            break
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
S = list(input())
LR = [list(map(int,input().split())) for _ in range(Q)]
lis = []
s = [0]*N
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        s[i] = 1

L = [0]*(N+1)
R = [0]*N

tmp = 0
for ind,i in enumerate(s):
    if i == 1:
        tmp += 1
    L[ind+1] = tmp

tmp = 0
for i in range(N-2,-2,-1):
    if s[i] == 1:
        tmp += 1
    R[i+1] = tmp

R.append(0)
sums =sum(s)
for i in range(Q):
    ans = sums-L[LR[i][0]-1]-R[LR[i][1]]
    print(ans)
x = input()


if x < 1200:
    print("ABC")

else:
    print("ARC")


### FIXED CODE ###

x = int(input())


if x < 1200:
    print("ABC")

else:
    print("ARC")
n, m = map(int, input().split())
l = [[] for _ in range(m)]
for i in range(m):
  a, b  = map(int, input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

import itertools
ans = 0
for p in itertools.permutations(range(n)):
    if p[0] == 0:
        flag = True
        for i in range(n-1):
            if not p[i+1] in l[p[i]]:
                flag = False
        if flag:
            ans += 1
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
L = [[] for i in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
    
import itertools
count = 0
for p in itertools.permutations(range(N)):
    if p[0] == 0:
#         print("p",p)
        flag = True
        for i in range(N-1):
#             print(p[i+1], L[p[i]])
            if not p[i+1] in L[p[i]]:
                flag = False
#             print(flag)
        if flag:
            count += 1
print(count)
N, W = [int(i) for i in input().split()]
noValue = [[W+1 for j in range(10001)] for i in range(N)]
w,v = [int(i) for i in input().split()]
maxValue = v
noValue[0][v] = w

for i in range(1,N) :
	noValue[i][0] = 0
	w, v = [int(i) for i in input().split()]
	for j in range(1,maxValue+v+1) :
		if j < v  :
			noValue[i][j] = noValue[i-1][j]
		else :
			if noValue[i-1][j - v] == W + 1 :
				if j == v :
					noValue[i][j] = w
					maxValue = max(maxValue, j)
				else :
					noValue[i][j] = noValue[i-1][j]
			elif noValue[i-1][j-v] + w > W :
				noValue[i][j] = noValue[i-1][j]
			else :
				noValue[i][j] = min(noValue[i-1][j - v] + w, noValue[i-1][j])
				maxValue = max(maxValue, j)
print(maxValue)

### FIXED CODE ###

N, W = [int(i) for i in input().split()]
noValue = [[W+1 for j in range(100001)] for i in range(N)] # 重さ[番号][価値]
w,v = [int(i) for i in input().split()]
maxValue = v
noValue[0][v] = w

for i in range(1,N) :	
	noValue[i][0] = 0
	w, v = [int(i) for i in input().split()] # w, v = w_i, v_i
	for j in range(1,min(maxValue+v+1, 100001)) : # 現在の価値の最大+今の入力の価値 or 価値の最大値 の小さいほう
		if j < v  :
			noValue[i][j] = noValue[i-1][j]
		else :
			if noValue[i-1][j - v] == W + 1 :
				if j == v :
					noValue[i][j] = w
					maxValue = max(maxValue, j)
				else :
					noValue[i][j] = noValue[i-1][j]
			elif noValue[i-1][j-v] + w > W :
				noValue[i][j] = noValue[i-1][j]
			else :
				noValue[i][j] = min(noValue[i-1][j - v] + w, noValue[i-1][j])
				maxValue = max(maxValue, j)
print(maxValue)
x = int(input())
print(max(i ** j for i in range(2, 34) for j in range(2, 11) if i ** j <= x))

### FIXED CODE ###

x = int(input())
print(max(i ** j for i in range(1, 34) for j in range(2, 11) if i ** j <= x))
class UnionFind:
    pairs = {}
    def __init__(self, n):
        for i in range(n):
            self.pairs[i] = i

    def set(self, s, t):
        if s in self.pairs and self.pairs[s] == s:
            self.pairs[s] = t
        else:
            self.pairs[t] = s

    def root(self, x):
        if self.pairs[x] == x:
            return x
        self.pairs[x] = self.root(self.pairs[x])
        return self.pairs[x]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry :
            return
        self.pairs[rx] = ry
def main():
    n, m = map(int, input().split())

    uf = UnionFind(n)
    pairs =[]
    for i in range(m):
        s, t = map(int,input().split())
        #uf.unite(s-1, t-1)
        #uf.set(s - 1, t - 1)
        pairs.append([s-1,t-1])

    pairs.sort()
    for pair in pairs:
        uf.set(pair[0], pair[1])
    #
    # for pair in pairs:
    #     uf.set(pair[0], pair[1])

    root = []
    for i in range(n):
        root.append(uf.root(i))
 #       print(i, uf.root(i))
    single_root = set(root)

    print(len(single_root)-1)
main()


### FIXED CODE ###

class UnionFind:
    pairs = {}
    def __init__(self, n):
        for i in range(n):
            self.pairs[i] = i

    def set(self, s, t):
        if s in self.pairs and self.pairs[s] == s:
            self.pairs[s] = self.root(t)
        else:
            self.pairs[t] = self.root(s)

    def root(self, x):
        if self.pairs[x] == x:
            return x
        self.pairs[x] = self.root(self.pairs[x])
        return self.pairs[x]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry :
            return
        self.pairs[rx] = ry
    def same(self, x, y ):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return True
        else:
            return False
        
def main():
    n, m = map(int, input().split())

    uf = UnionFind(n)
    pairs =[]
    for i in range(m):
        s, t = map(int,input().split())
        if uf.same(s-1, t-1) == False:
            uf.unite(s-1,t-1)
        #pairs.append([s-1,t-1])

    # pairs.sort()
    # for pair in pairs:
    #     uf.set(pair[0], pair[1])
    #
    # for pair in pairs:
    #     uf.set(pair[0], pair[1])

    root = []
    for i in range(n):
        root.append(uf.root(i))
 #       print(i, uf.root(i))
    single_root = set(root)

    print(len(single_root)-1)
main()