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

import sys
from collections import deque



readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

def bfs(start,ex_kyori):
    tansaku = deque()
    tansaku.append(start)
    visited = {i:set() for i in range(h)}
    kyori = ex_kyori
    while tansaku:
        pre_y,pre_x = tansaku.popleft()
        if pre_x in visited[pre_y]:
            continue
        for i in range(pre_x-1,pre_x+2,2):
            if 0 <= i <= w-1 and tizu[pre_y][i] == '.':
                tansaku.append([pre_y,i])
                kyori[pre_y][i] = min(kyori[pre_y][i],kyori[pre_y][pre_x]+1)
        for j in range(pre_y-1,pre_y+2,2):
            if 0 <= j <= h-1 and tizu[j][pre_x] == '.':
                tansaku.append([j,pre_x])
                kyori[j][pre_x] = min(kyori[j][pre_x],kyori[pre_y][pre_x]+1)
        visited[pre_y].add(pre_x)
    return kyori

h,w = nm()
tizu = []
sharp = []
saitan = [[10**10]*w for _ in range(h)]
for i in range(h):
    temp = list(input())
    s_temp = [[i,j] for j in range(w)  if temp[j] == '#' ]
    tizu.append(temp)
    sharp += s_temp
for i,j in sharp:
    saitan[i][j] = 0 
for i in sharp:
    saitan = bfs(i,saitan)
print(max((max(i) for i in saitan)))

### FIXED CODE ###

import sys
from collections import deque



readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

def bfs(start):
    tansaku = deque(start)
    visited = {i:set() for i in range(h)}
    res = 0
    black = len(start)
    while black != h*w:
        for _ in range(len(tansaku)):
            pre_y,pre_x = tansaku.popleft()
            if pre_x in visited[pre_y]:
                continue
            for i in range(pre_x-1,pre_x+2,2):
                if 0 <= i <= w-1 and tizu[pre_y][i] == '.':
                    tansaku.append([pre_y,i])
                    tizu[pre_y][i] = '#'
            for j in range(pre_y-1,pre_y+2,2):
                if 0 <= j <= h-1 and tizu[j][pre_x] == '.':
                    tansaku.append([j,pre_x])
                    tizu[j][pre_x] = '#'
            visited[pre_y].add(pre_x)
        black += len(tansaku)
        res += 1
    return res

h,w = nm()
tizu = []
sharp = []
for i in range(h):
    temp = list(input())
    s_temp = [[i,j] for j in range(w)  if temp[j] == '#' ]
    tizu.append(temp)
    sharp += s_temp
ans = bfs(sharp)
print(ans)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]

ses = list(set(s))
setnums = []
for i in ses:
    setnums.append(s.count(i))

num = max(setnums)
pl = []
for i in ses:
    if num == s.count(i):
        pl.append(i)

pl = sorted(pl)
for i in pl:
    print(i)

### FIXED CODE ###

import collections


n = int(input())
s = [input() for i in range(n)]
c = collections.Counter(s)

sss = set(s)
mx = 0
pl = []
for ss in sss:
    if c[ss] > mx:
        mx = c[ss]
        pl = [ss]
    elif c[ss] == mx:
        pl.append(ss)
pl = sorted(pl)
for i in pl:
    print(i)
### BUGGY CODE ###

def main():
  n,k,q = [int(x) for x in raw_input().split()]
  answers = [int(raw_input())-1 for x in xrange(q)]
  scores = [k,] * n
  
  for answer in answers:
    for i in xrange(n):
      if i != answer:
        scores[i] -= 1
  
  for score in scores:
    print("Yes" if score > 0 else "No")

main()


### FIXED CODE ###

def main():
  n,k,q = [int(x) for x in raw_input().split()]
  memo = {}

  for _ in xrange(q):
      pid = int(raw_input()) - 1
      if pid not in memo:
          memo[pid] = 0
      memo[pid] += 1

  for pid in xrange(n):
      score = k - q + memo.get(pid, 0)
      print("Yes" if score > 0 else "No")

main()
### BUGGY CODE ###

n = int(input())
data = [int(x) for x in input().split()]
cnt = [0]*(n+1)

# ボールに書かれた整数を集計する
for x in data:
    cnt[x] += 1

for k in range(n):
    # k番目のボールの個数を減らす
    cnt_copy = cnt[:]
    cnt_copy[data[k]] -= 1

    answer = 0
    for x in cnt_copy:
        answer += int(x*(x-1)/2)

    print(answer)

### FIXED CODE ###

n = int(input())
data = [int(x) for x in input().split()]
cnt = [0]*(n+1)

# ボールに書かれた整数を集計する
for x in data:
    cnt[x] += 1

total = int(sum([x*(x-1)/2 for x in cnt]))

for k in range(n):
    answer = total - cnt[data[k]] + 1
    print(answer)
### BUGGY CODE ###

N = int(input())
A = [input() for i in range(N)]
B = list(set(A))
C = [0]*len(B)
for i in range(len(B)):
  C[i] = A.count(B[i])
D = max(C)
for s in sorted([B[i] for i, x in enumerate(C) if x == D]):
    print(s)


### FIXED CODE ###

N = int(input())

d = {}
for _ in range(N):
    S = input()
    if S in d:
        d[S] += 1
    else:
        d[S] = 1

m = max(d.values())
for s in sorted(k for k in d if d[k] == m):
    print(s)
### BUGGY CODE ###

from functools import reduce
N = int(input())

L = [v for v in range(2, 2*N)]

while L:
    cur = L.pop(0)
    L = list(filter(lambda x: x % cur != 0, L))
    if cur >= N:
        print(cur)
        exit()


### FIXED CODE ###

N = int(input())


def is_prime(N):
    i = 2
    while i*i <= N:
        if N % i == 0:
            return False
        i += 1
    return True


while True:
    if is_prime(N):
        print(N)
        exit()
    N += 1
### BUGGY CODE ###

N, M, K = map(int, input().split(' '))
A_ls = [0] + list(map(int, input().split(' ')))
for i in range(N):
    A_ls[i + 1] += A_ls[i]
B_ls = [0] + list(map(int, input().split(' ')))
for i in range(M):
    B_ls[i + 1] += B_ls[i]

a_cnt, b_cnt, rst = 0, M, 0
for a_cnt in range(N + 1):
    if A_ls[a_cnt] > K:
        break
    while A_ls[a_cnt] + B_ls[b_cnt] > K and b_cnt > 0:
        b_cnt -= 1
    rst = max(rst, a_cnt + b_cnt)
    b_cnt = M
print(rst)

### FIXED CODE ###

n, m, k = map(int, input().split(' '))
ans = 0

a_ls = [0] + list(map(int, input().split(' ')))
b_ls = [0] + list(map(int, input().split(' ')))

for i in range(1, n+1):
    a_ls[i] += a_ls[i-1]
for i in range(1, m+1):
    b_ls[i] += b_ls[i-1]

b_cnt = m
for a_cnt in range(0, n+1):
    if a_ls[a_cnt] > k:
        continue
    while a_ls[a_cnt] + b_ls[b_cnt] > k:
        b_cnt -= 1
    ans = max(ans, a_cnt + b_cnt)

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

N=int(input())
S = []
for i in range(N):
  data=input()
  if data in S:
    pass
  else:
    S.append(data)
print(len(S))

### FIXED CODE ###

N = int(input())
S = list()
for i in range(N):
  x = input()
  S.append(x)
  
A = set(S)
print(len(A))
### BUGGY CODE ###

from collections import deque
import sys
def longest_subsequence(sequence):
  table = [(1, sequence[0])]
  for x in sequence[1:]:
    maxlen = 0
    for (L, z) in table:
      if z < x: # strict increasing
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
  return max(L for (L, _) in table)
def dfs(vertex):
  visited[vertex] = True
  node_sequence.append(a[vertex])
  ans[vertex] = longest_subsequence(node_sequence)
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  node_sequence.pop()
  return
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
node_sequence = list()
visited = [False]*n
ans = [0]*n
dfs(0)
[print(value) for value in ans]

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
from bisect import bisect, bisect_left
def longest_subsequence(sequence):
  subsequence = [float("inf") for _ in range(len(sequence)+1)]
  subsequence[0] = float("-inf")
  for value in sequence:
    j = bisect(subsequence, value)
    if subsequence[j-1] != value: # strict increasing
      subsequence[j] = value
  return bisect_left(dp, float("inf"))-1
# print(longest_subsequence([9, 13, 2, 10, 4, 13, 11, 13]))
# sys.exit()
def dfs(vertex):
  visited[vertex] = True
  value = a[vertex]
  j = bisect(subsequence, value)
  previous = subsequence[j]
  if subsequence[j-1] != value: # strict increasing
    subsequence[j] = value
  ans[vertex] = bisect_left(subsequence, float("inf"))-1
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  subsequence[j] = previous
  return
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
visited = [False]*n
ans = [0]*n
subsequence = [float("inf") for _ in range(n+1)]
subsequence[0] = float("-inf")
dfs(0)
[print(value) for value in ans]
### BUGGY CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
X=[]
for a in P:
    X.append(a/2+0.5)

han=-32
for a in range(N-K+1):
    gou=0
    for b in range(K):
        i=a+b

        gou+=X[i]

    if gou>han:
        han=gou

print(han)

### FIXED CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
X=[]
for a in P:
    X.append(a/2+0.5)
gou=sum(X[0:K])

han=-32
saigou=sum(X[N-K:N])
han=saigou
for a in range(N-K-1):

    if gou>han:
        han=gou
    gou=gou-X[a]+X[a+K]

print(han)
### BUGGY CODE ###

n,c=map(int,input().split())
stc=[list(map(int,input().split())) for _ in range(n)]
cs_dc={}
dc={}
for s,t,c in stc:
  if c in dc:
    dc[c][s]+=1
    dc[c][t]-=1
  else:
    dc[c]=[0]*(10**5+2)
    dc[c][s]+=1
    dc[c][t]-=1
    cs_dc[c]=[0]*(10**5+2)

for i in range(10**5+1):
  for ci in dc:
    cs_dc[ci][i+1]=cs_dc[ci][i]+dc[ci][i+1]
ans=0
for i in range(10**5+1):
  tmp=0
  for ci in dc:
    tmp+=max(cs_dc[ci][i:i+2])
  ans=max(ans,tmp)
print(ans)

### FIXED CODE ###

n,c=map(int,input().split())
stc=[list(map(int,input().split())) for _ in range(n)]
cs_dc={}
dc={}
for s,t,c in stc:
  if c in dc:
    dc[c][s]+=1
    dc[c][t]-=1
  else:
    dc[c]=[0]*(10**5+2)
    dc[c][s]+=1
    dc[c][t]-=1
    cs_dc[c]=[0]*(10**5+2)

for i in range(10**5+1):
  for ci in dc:
    cs_dc[ci][i+1]=cs_dc[ci][i]+dc[ci][i+1]
ans=0
for i in range(10**5+1):
  tmp=0
  for ci in dc:
    tmp+=max(cs_dc[ci][i:i+2])
  ans=max(ans,tmp)
print(ans)
### BUGGY CODE ###

#ABC129C-TypicalStairs.py

#import list
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(10000)

#constant
#N = int(input())
N, M = list(map(int,input().split()))
A = [int(input()) for _ in range(M)]

#variable

#function
@lru_cache(maxsize=None)
def rootCount(position):
    if position < 0:
        return 0
    elif position == 0:
        return 1
    elif position in A:
        return 0
    else:
        return (rootCount(position-1)+rootCount(position-2)) % 1000000007
#class

#main function
def main():
    i = 1
    while i < N:
        rootCount(i)
        i += 1
    print(rootCount(N))

if __name__ == "__main__":
    main()


### FIXED CODE ###

#ABC129C-TypicalStairs.py

#import list
import numpy as np
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(1000)

#constant
#N = int(input())
N, M = list(map(int,input().split()))
A = {int(input()) for _ in range(M)}

#variable
rootList = np.array([1]+[0]*(N))

#function

#class

#main function
def main():
    for i in range(N):
        rootList[i+1] = (rootList[i]+rootList[i-1])%1000000007
        if i+1 in A:
            rootList[i+1] = 0
    print(rootList[N])

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

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

c = Counter(A)
minus = []
for i in c.items():
  if i[1] > 1:
    minus.append(i[0])

flag = True
A = sorted(set(A))
i = 0
j = len(A)-1

while i < j:
  if A[j] % A[i] == 0:
    A.pop(j)
  j -= 1
  if j == i:
    j = len(A)-1
    i += 1
  
cnt = 0
for n in minus:
  if n in A:
    cnt += 1
ans = len(A) - cnt
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
l = max(A)+1
li = [0]*(l)
A.sort()

for a in A:
  if li[a] == 0:
    li[a] = 1
    for i in range(a*2, l, a):
      li[i] = 2
  elif li[a] == 1:
    li[a] = 2
print(li.count(1))
### BUGGY CODE ###

N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
dp = [[1]+[0]*(len(T))for i in range(len(S)+1)]
dp[0] = [1]*(len(T)+1)
dp_sum = [[1]+[0]*(len(T))for i in range(len(S)+1)]
dp_sum[0] = [1]*(len(T)+1)
for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp_sum[i][j]
        dp_sum[i+1][j+1] = (dp[i+1][j+1]+dp_sum[i+1][j]+\
            dp_sum[i][j+1]-dp_sum[i][j])%(10**9+7)
print(dp_sum[-1][-1])

### FIXED CODE ###

N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
dp = [[1]+[0]*(len(T))for i in range(len(S)+1)]
dp[0] = [1]*(len(T)+1)
dp_sum = [[1]+[0]*(len(T))for i in range(len(S)+1)]
dp_sum[0] = [1]*(len(T)+1)
for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp_sum[i][j]
        dp_sum[i+1][j+1] = (dp[i+1][j+1]+dp_sum[i+1][j]+\
            dp_sum[i][j+1]-dp_sum[i][j])%(10**9+7)
print(dp_sum[-1][-1])
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    inp = input().split()
    if len(inp) == 1:
        S = S[::-1]
    else:
        f, c = inp[1:]
        if int(f) == 1:
            S = c + S
        else:
            S = S + c
print(S)

### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())

reverse = False
cnt = 0
for i in range(Q):
    inp = input().split()
    if inp[0] == "1":
        cnt += 1
        reverse = (cnt % 2 != 0)
        #S = S[::-1]
    else:
        f, c = inp[1:]
        if int(f) == 1:
            if reverse:
                S.append(c)
            else:
                S.appendleft(c)
        else:
            if reverse:
                S.appendleft(c)
            else:
                S.append(c)
S = "".join(S)
print(S[::-1] if reverse else S)
### BUGGY CODE ###

import math
from collections import Counter
N = int(input())

for i in range(N):
    flg = False
    count = 0
    if i < 5:
        print(count)
    else:
        x_min = 1
        x_max = int(math.sqrt(i + 1))
        for x in range(x_min, x_max + 1):
            x_count = 0
            for y in range(x, x_max + 1):
                y_count = 0
                for z in range(y, x_max + 1):
                    #print(i, x, y, z)
                    if x * x + y * y + z * z + x * y + y * z + z * x == i + 1:
                        x_count += 1
                        y_count += 1
                        numbers = Counter([x, y, z]).values()
                        count += math.factorial(3)
                        for number in numbers:
                            count /= math.factorial(number)
                    elif x * x + y * y + z * z + x * y + y * z + z * x > i + 1:
                        break
                    else:
                        x_count += 1
                        y_count += 1
                if y_count == 0:
                    flg = True
                    break
            if x_count == 0:
                break
            
        print(int(count))

### FIXED CODE ###

N = int(input())
answer = [0] * (10001)

for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            index = x * x + y * y + z * z + x * y + y * z + z * x - 1
            if index > N:
                break
            answer[index] += 1
            

for i in range(N):
    print(answer[i])
### BUGGY CODE ###

s = input()
n = len(s)
ans = [0 for i in range(n)]
used = [False for _ in range(n)]
for i in range(n):
    if used[i]:
        continue
    else:
        used[i] = True
        stand = [1,0]
        pre = -1
        now = i
        next = 0
        count = 1
        if s[now] == 'R':
            next = now+1
        else:
            next = now-1
        while pre != next:
            count *= -1
            pre = now
            now = next
            if s[now] == 'R':
                next = now + 1
            else:
                next = now - 1
            if not used[now]:
                if count == 1:
                    stand[0] += 1
                else:
                    stand[1] += 1
            used[now] = True
        used[next] = True
        if (pre-i)%2 == 1:
            ans[pre] += stand[1]
            ans[now] += stand[0]
        else:
            ans[pre] += stand[0]
            ans[now] += stand[1]

for i in range(n):
    print(ans[i],end=' ')
print()


### FIXED CODE ###

s = input()
n = len(s)
ans  =[0 for i in range(n)]
i = 0
while i < n:
    le = i
    while i+1 < n and s[i] == s[i+1]:
        i += 1
    length = i - le + 1
    if s[i] == 'L':
        ans[le]+=(length+1)//2
        ans[le-1] += length//2
    else:
        ans[i] += (length+1)//2
        ans[i+1] += length//2
    i += 1

for i in range(n):
    print(ans[i],end=' ')

print()
### BUGGY CODE ###

from collections import defaultdict

S = input()
T = input()

AS = defaultdict(list)
AT = defaultdict(list)

isok = True
for i in range(len(S)):
    AS[S[i]].append(i)
    AT[T[i]].append(i)
    if AS[S[i]]!=AT[T[i]]:
        isok = False
        break
        
if isok:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from collections import defaultdict

S = input()
T = input()

A = {}
B = {}

isok = True
for i in range(len(S)):
    if S[i] in A:
        if T[i] != A[S[i]]:
            isok = False
            break
    else:
        A[S[i]] = T[i]
    if T[i] in B:
        if S[i] != B[T[i]]:
            isok = False
            break
    else:
        B[T[i]] = S[i]
        
if isok:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

H,N=map(int,input().split())
ABC=[]
for _ in range(N):
  a,b=map(int,input().split())
  ABC.append((a,b,a/b))
ABC=sorted(ABC, key=lambda x:x[2], reverse=True)
A=[ABC[i][0] for i in range(N)]
B=[ABC[i][1] for i in range(N)]
dp=[[float('inf')]*(H+1) for i in range(N+1)]
for i in range(N+1):
  dp[i][0]=0
  
for i in range(N):
  for j in range(1,H+1):
    if j-A[i]>=0:
      dp[i+1][j]=min(dp[i][j],dp[i+1][j-A[i]]+B[i])
    else:
      dp[i+1][j]=min(dp[i][j],dp[i+1][0]+B[i])
print(dp[N][H])
#print(dp)

### FIXED CODE ###

H,N=map(int,input().split())
ABC=[]
for _ in range(N):
  a,b=map(int,input().split())
  ABC.append((a,b,a/b))
ABC=sorted(ABC, key=lambda x:x[2], reverse=True)
A=[ABC[i][0] for i in range(N)]
B=[ABC[i][1] for i in range(N)]
dp=[[float('inf')]*(H+1) for i in range(N+1)]
for i in range(N+1):
  dp[i][0]=0
  
for i in range(N):
  for j in range(1,H+1):
    if j-A[i]>=0:
      dp[i+1][j]=min(dp[i][j],dp[i+1][j-A[i]]+B[i])
    else:
      dp[i+1][j]=min(dp[i][j],dp[i+1][0]+B[i])
print(dp[N][H])
#print(dp)
### BUGGY CODE ###

arr = input().split()
K = int(arr[0])
A = int(arr[1])
B = int(arr[2])

x = 1
a = 0
n = 1 + K

while K > 0:
	if a > 0 and B > A:
		x += B
		a -= 1
		K -= 1
		continue

	if x >= A and B > A and K != 1:
		x -= A
		a += 1
		K -= 1
		continue

	x += 1
	K -= 1

print(max(x, n))


### FIXED CODE ###

arr = input().split()
K = int(arr[0])
A = int(arr[1])
B = int(arr[2])

n = 1 + K
x = 1
if K > A:
	x = B
	K -= A+1

	temp = int(K / 2)

	x += temp * (B-A)
	K -= temp * 2

	while K > 0:
		K -= 1
		x += 1

print(max(x, n))
### BUGGY CODE ###

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

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

INF = 10**18
dp = [[INF] * N for _ in range(N)]

def calc(i, j):
    if dp[i][j] != INF:
        return dp[i][j]
    if i == j:
        dp[i][j] = a[i]
    else:
        dp[i][j] = max(a[i] - calc(i+1, j), a[j] - calc(i, j-1))
    return dp[i][j]

print(calc(0, N-1))

### FIXED CODE ###

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

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

INF = 10**18
dp = [[INF] * N for _ in range(N)]

# def calc(i, j, t):
#     if dp[i][j] != INF:
#         return dp[i][j]
#     if t == 0:
#         if i == j:
#             dp[i][j] = a[i]
#         else:
#             dp[i][j] = max(calc(i+1, j, 1) + a[i], calc(i, j-1, 1) + a[j])
#     else:
#         if i == j:
#             dp[i][j] = -a[i]
#         else:
#             dp[i][j] = min(calc(i+1, j, 0) - a[i], calc(i, j-1, 0) - a[j])
#     return dp[i][j]

# print(calc(0, N-1, 0))

for l in range(N):
    t = (N-l) % 2
    for i in range(N-l):
        j = i + l
        if t == 1:
            if l == 0:
                dp[i][j] = a[i]
            else:
                dp[i][j] = max(dp[i+1][j] + a[i], dp[i][j-1] + a[j])
        else:
            if l == 0:
                dp[i][j] = -a[i]
            else:
                dp[i][j] = min(dp[i+1][j] - a[i], dp[i][j-1] - a[j])
print(dp[0][N-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
a = int(input())
count = 0
first = 2
def num_div(num):
  a = 2
  while num!=1:
    if num % a == 0:
      num /= a
      while True:
        if num % a ==0:
          num /= a
        elif num == 1:
          return 0
        else:
          return -1
    a += 1

#print(num_div(2))
#sys.exit(0)

while a!=1:
  #素因数は一つ？
  if a % first == 0:
    if num_div(first) == -1:
      first += 1
      continue
    else:
      a /= first
      count += 1
  first += 1
print(count)


### FIXED CODE ###

from collections import Counter

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

def get_count(c):
  ans = 0
  _max = c
  for i in range(1,c+1):
    if i <= _max:
      ans += 1
      _max -= i
    else:
      break
  return ans
a = int(input())
counter = Counter(prime_factor(a))
ans = 0
for i in counter:
  ans += get_count(counter[i])
print(ans)
### BUGGY CODE ###

a = int(input())
ans = 1
flag = 0
d = list(map(int,input().split()))
for i in d:
    ans *= i 
    if ans > 10**18 and (0 not in d):
        flag = 1
        break
    else:
        continue
if flag == 0:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

a = int(input())
ans = 1
flag = 0
d = list(map(int,input().split()))
if 0 in d:
    print(0)
else:    
    for i in d:
        ans *= i 
        if ans > 10**18:
            flag = 1
            break
        else:
            continue
    if flag == 0:
        print(ans)
    else:
        print(-1)
### BUGGY CODE ###

from collections import Counter
import math

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

a.sort()

is_prime = [True]*(10**6 + 1)

is_prime[0] = False

for i in set(a):
    for j in range(2 * i, max(a)+1, i):
        is_prime[j] = False

result = 0
c = Counter(a)

for e in set(a):
        if is_prime[e] and c[e] == 1:
    #        print('e = {}'.format(e))
             result += 1

print(result)



### FIXED CODE ###

from collections import Counter
import math

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

a.sort()

is_prime = [True]*(10**6 + 1)

is_prime[0] = False

maxA = max(a)

for i in set(a):
    for j in range(2 * i, maxA+1, i):
        is_prime[j] = False

result = 0
c = Counter(a)

for e in set(a):
        if is_prime[e] and c[e] == 1:
    #        print('e = {}'.format(e))
             result += 1

print(result)
### BUGGY CODE ###

n,m = map(int, input().split())
a = n**m%1000000007
print(a)

### FIXED CODE ###

def power(n,m):
    if m == 0:
        return 1
    if m % 2 == 0:
        return power(n*n%1000000007,m//2)
    else:
        return n * power(n,m-1) % 1000000007
        
n,m = map(int, input().split())
print(power(n,m))