Harryxun/stf_run huggingface dataset:
N, M = map(int, input().split())

mod = 1000000007

f = [] # 素因数分解(指数部のみ)

for p in range(2, M): # 素因数分解
    e = 0
    while M%p == 0:
        e += 1
        M /= p
    
    if e>0:
        f.append(e)
    
    if M == 1:
        break

def pw(a, e):
    if e == 1:
        return a
    p = pw(a, e // 2)
    if e%2 == 1:
        return p * p * a % mod
    else:
        return p * p % mod

# fact, inv の計算
fact = [1] * 100040
inv = [1] * 100040
for k in range(1, 100040):
    fact[k] = fact[k-1] * k % mod
    inv[k] = pw(fact[k], mod-2)

ans = 1
for e in f:
    ans *= fact[e+N-1] * inv[e] * inv[N-1] % mod # N_H_e (重複組合せ)

print(ans)


### FIXED CODE ###

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

def ans1(): # 全ての組み合わせを調べる
    return max([
        10*A + B + C, # 10*A + C + B, 
        10*B + A + C, # 10*B + C + A, 
        10*C + A + B, # 10*C + B + A, 
    ])

def ans2():
    return A + B + C + 9*max([A, B, C])

#print(ans1())
print(ans2())
n = int(input())
xy = []
for i in range(n):
    xy.append(list(map(int, input().split())))
xy.sort(key = lambda x: x[1])
xy.sort()
dif = []
for i in range(n):
    for j in range(i + 1, n):
        dif.append((xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]))
count_dif = {}
for i in dif:
    count_dif.setdefault(i, 0)
    count_dif[i] += 1
print(n - max(count_dif.values()))

### FIXED CODE ###

n = int(input())
xy = []
for i in range(n):
    xy.append(list(map(int, input().split())))
xy.sort(key = lambda x: x[1])
xy.sort()
if n == 1:
    print(1)
else:
    dif = []
    for i in range(n):
        for j in range(i + 1, n):
            dif.append((xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]))
    count_dif = {}
    for i in dif:
        count_dif.setdefault(i, 0)
        count_dif[i] += 1
    print(n - max(count_dif.values()))
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))

if M == 0:
    arr = N
else:
    arr = [a[0] - 1]
    for i in range(M-1):
        print(a[i], a[i+1])
        diff = a[i+1] - a[i] - 1
        arr.append(diff)
        if diff == 0:
            print(0)
            exit()
    arr.append(N - a[-1] - 1)

count = [1, 1, 2]
for i in range(3, max(arr)+1):
    count.append(count[-1] + count[-2])

ans = 1
for value in arr:
    ans *= count[value]
    ans = ans % 1000000007

print(ans)




### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))

if M > 0:
    for i in range(M-1):
        if a[i+1] - a[i] == 1:
            print(0)
            exit()

check = set(a)
if 1 in check:
    dp = [0, 0, 1]
elif 2 in check:
    dp = [0, 1, 0]
else:
    dp = [0, 1, 2]
if N < 3:
    print(dp[N])
    exit()
for i in range(3, N+1):
    if i in check:
        dp.append(0)
    else:
        dp.append((dp[-1] + dp[-2])%1000000007)

print(dp[-1])
a=input()
b=input()
if len(a)>len(b):
  print("GREATER")
elif len(a)<len(b):
  print("LESS")
else:
  i=0
  while 1:
    if int(a[i])>int(b[i]):
      f=1
    elif int(a[i]<int(b[i]):
      f=2
    i+=1
  if f==1:
    print("GREATER")
  else:
    print("LESS")


### FIXED CODE ###

a=input()
b=input()
if len(a)>len(b):
  print("GREATER")
elif len(a)<len(b):
  print("LESS")
else:
  i=0
  f=0
  while len(a)>i:
    if int(a[i])>int(b[i]):
      f=1
      break
    elif int(a[i])<int(b[i]):
      f=2
      break
    i+=1
  if f==0:
    print("EQUAL")
  elif f==1:
    print("GREATER")
  else:
    print("LESS")
a,b,h = list(map(int, input().split()))
print((a+b)*h / 2)

### FIXED CODE ###

a = int(input())
b = int(input())
h = int(input())
print(int((a+b)*h / 2))
n,m=map(s,input().split())
if(len(n)<=1 and len(m)<=1):
	print(int(n)*int(m))
else:
	print(-1)

### FIXED CODE ###

n,m=map(str,input().split())
if(len(n)<=1 and len(m)<=1):
	print(int(n)*int(m))
else:
	print(-1)
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, k = LI()
dp = [[[0] * (n * (n + 1)) for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(i+1):
        for l in range(k + 1):
            dp[i + 1][j + 1][l+2*(j + 1)] += dp[i][j][l]
            dp[i + 1][j][l+2*j] += dp[i][j][l]*(j*2+1)
            if j != 0:
                dp[i+1][j-1][l+(j-1)*2] += dp[i][j][l]*j*j


print(dp[n][0][k]%mod)


### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, k = LI()
dp = [[[0]*n**2*4 for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(i+1):
        for l in range(k+1):
            dp[i+1][j+1][l+2*(j+1)] += dp[i][j][l]
            dp[i+1][j+1][l+2*(j+1)]%=mod
            dp[i+1][j][l+2*j] += dp[i][j][l]*(j*2+1)
            dp[i+1][j][l+2 * j] %= mod
            if j!= 0:
                dp[i+1][j-1][l+(j-1)*2] += dp[i][j][l]*j*j
                dp[i+1][j-1][l+(j-1)*2]%=mod



print(dp[n][0][k]%mod)
N,K = map(int, input().split())
A = list(map(int, input().split()))

now = 1
toLoop = 0 #1の町からループに入るまでのワープ数
towns = list()
townList = list()
for i in range(1,K+1):
	now = A[now-1]
	loop_num = i
	if not now in towns:
		towns.append(now)
	else:
		start = now
		count = 1
		now = A[now-1]
		while start != now:
			count += 1
			now = A[now-1]
		toLoop = loop_num - count
		loop_num = count
		break

if K <= loop_num:
	print(now)
else:
	warp_num = (K-toLoop)%loop_num
	for _ in range(warp_num): now = A[now-1]
	print(now)

### FIXED CODE ###

S = input()
T = input()

if S == T[:-1] and len(S) == len(T)-1:
	print('Yes')
else:
	print('No')
import math
A,B = map(int,input().split())
def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

GCD = math.gcd(A,B)

prime_list = get_sieve_of_eratosthenes(GCD)
counter = 1
for p in prime_list:
    if GCD % p == 0:
        counter += 1
        while(GCD % p == 0):
            GCD = GCD // p
        
print(counter)


### FIXED CODE ###

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

A,B = map(int,input().split())
GCD = fractions.gcd(A,B)
pf = prime_factorize(GCD)
print(len(set(pf))+1)
S = str(input())
i, ans = 0, 0
if len(S) <= 1:
    print(0)
    exit()

while i < abs(len(S)-S.count("1")):
    if S[i] != S[i+1]:
        S = S[:i]+S[i+2:]
        i = -1
        ans += 2
    i += 1
print(ans)


### FIXED CODE ###

S = str(input())
x = S.count("0")
y = S.count("1")
print(2*min(x, y))
from collections import deque

INF = 1001001001
n, m = map(int, input().split())

to = [[] for _ in range(n)]
for i in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

q = deque([0])
dist = [-1] * n
dist[0] = 0
# print(to)

while q:
    v = q.popleft()

    for u in to[v]:
        if dist[u] != -1:
            continue
        dist[u] = v
        q.append(u)

print("Yes")
# print(dist)

for i in range(n):
    if i == 0:
        continue
    print(dist[i] + 1)


### FIXED CODE ###

from collections import deque

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

to = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    to[a].append(b)
    to[b].append(a)

q = deque([1])
dist = [-1] * (n + 1)
# print(to)

while q:
    v = q.popleft()

    for u in to[v]:
        if dist[u] != -1:
            continue
        q.append(u)
        dist[u] = v

print("Yes")
# print(dist)

for i in range(2, n + 1):
    print(dist[i])
n=int(input())
s=input()
t=input()
if s==t:
    print(n)
else:
    ans=2*n
    f=True
    for i in range(n):
        for j in range(i+1):
            if t[j]==a[n-1-i+j]:
                f=False
        if not f:
            break
        ans-=1
    print(ans)

### FIXED CODE ###

n=int(input())
s=input()
t=input()
i=0
while n>i:
    if i==0 and s==t:
        break
    if t[:-i]==s[i:]:
        break
    i+=1
print(n+i)
n, m = map(int, input().split())
ab = [tuple(int(x) for x in input().split()) for _ in range(m)]

ans = [n * (n - 1) // 2 for _ in range(m + 1)]

u = [-1 for _ in range(n)]

def root(x):
    if u[x] < 0:
        return x
    else:
        u[x] = root(u[x])
        return u[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    if size(x) < size(y):
        x, y = y, x
    u[x] += u[y]
    u[y] = x

def size(x):
    return - u[root(x)]

i = m - 1
for a, b in list(reversed(ab)):
    if root(a - 1) == root(b - 1):
        ans[i] = ans[i + 1]
    else:
        ans[i] = ans[i + 1] - size(a - 1) * size(b - 1)
        unite(a - 1, b - 1)
    i -= 1

for i in range(1, m + 1):
    print(ans[i])

### FIXED CODE ###

n, m = map(int, input().split())
ab = [tuple(int(x) for x in input().split()) for _ in range(m)]

class UnionFind:
    def __init__(self, size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]

    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x

    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]

uft = UnionFind(n)
ans = [0 for _ in range(m)]
temp = n * (n - 1) // 2
ans[m - 1] = temp
for i in range(m-1, 0, -1):
    ra = uft.find(ab[i][0] - 1)
    rb = uft.find(ab[i][1] - 1)
    if ra != rb:
        temp -= uft.number[ra] * uft.number[rb]
        uft.union(ra, rb)
    ans[i - 1] = temp

for x in ans:
    print(x)
import sys
import numpy as np
N = int(input())
D = list(map(int,input().split()))
M = max(D)
countlist=np.zeros(M+1)
ans=1

for i in D:
    countlist[i]+=1

if countlist[0]!=1 :
    print(0)
    sys.exit()
elif countlist[1]==0 and M==1:
    print(1)
    sys.exit()

for i in range(2,M+1):
    if countlist[i]>0:
        ans *= countlist[i-1]**countlist[i]
    elif i<M:
        ans=0
    else:
        break


print(int(ans%998244353)) 

### FIXED CODE ###

import sys
import numpy as np
N = int(input())
D = list(map(int,input().split()))
M = max(D)
countlist=list(map(int,np.zeros(M+1)))
ans=1

for i in D:
    countlist[i]+=1

if 0 in countlist or countlist[0]!=1 :
    print(0)
    sys.exit()
elif M<2:
    print(1)
    sys.exit()

if D[0]!=0 :
    print(0)
    sys.exit()

for i in range(2,M+1):
    if countlist[i]>0:
        ans *= countlist[i-1]**countlist[i]
    elif i<M:
        ans=0
    else:
        break


print(ans%998244353)
import heapq
N = int(input())
V = list(map(int, input().split()))
heapq.heapify(V)
for i in range(N-2):
  heapq.heappush((heapq.heappop(V)+heapq.heappop(V))/2)
print(sum(V)/2)

### FIXED CODE ###

import heapq
N = int(input())
V = list(map(int, input().split()))
 
heapq.heapify(V)
for i in range(N-2):
  heapq.heappush(V, (heapq.heappop(V)+heapq.heappop(V))/2)
print(sum(V)/2)
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]
v=[[]for _ in q]
z=0
for a,b in t:
	if a<=M:v[a-1]+=[b]
for i in v:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

### FIXED CODE ###

from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in range(M)]
for i in range(N):
	if t[2*i]<=M:
		v[t[2*i]-1].append(t[2*i+1])
z=0
q=[]
for i in range(M):
	for j in v[i]:
		heappush(q,-j)
	b=0
	if len(q):
		b=heappop(q)
	z-=b
print(z)
def actual(n, m, a_list):
    a_sum = sum(a_list)

    if n >= a_sum:
        return n - a_sum

    return -1

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

print(actual(n, m, a_list))

### FIXED CODE ###

def actual(n, m, a_list):
    a_sum = sum(a_list)

    if n >= a_sum:
        return n - a_sum

    return -1

n, m = map(int, input().split())
a_list = map(int, input().split())

print(actual(n, m, a_list))
n=int(input())
if n%2==0:
  print(1/2)
else:
  print((n+1)/2)/n

### FIXED CODE ###

n=int(input())
if n%2==0:
  print(1/2)
else:
  print(((n+1)/2)/n)
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
r = "Yes"
for i in range(1, h-1):
    for j in range(1, w-1):
        if a[i][j] == "#" and a[i - 1][j] == "." and a[i + 1][j] == "." and a[i][j - 1] == "." and a[i][j + 1] == ".":
          r = "No"
print(r)


### FIXED CODE ###

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
r = "Yes"
for i in range(1, h-1):
    for j in range(1, w-1):
        if s[i][j] == "#" and s[i - 1][j] == "." and s[i + 1][j] == "." and s[i][j - 1] == "." and s[i][j + 1] == ".":
          r = "No"
print(r)
from  collections import deque
 
N, M, K =map(int, input().split())
A  = list(map(int, input().split()))
B  = list(map(int, input().split()))
 
A = deque(A)
B = deque(B)
 
def check(n, A_, B_):
  if len(A_) >= n and len(B_) >= n:
    if A_[n-1] > B_[n-1]:
      return 'B'
    elif A_[n-1] < B_[n-1]:
      return 'A'
    else:
      check(n+1, A_, B_)
  elif len(A_) < n and len(B_) <  n:
    return 'A'
  elif len(A_) < n:
    return 'B'
  else:
    return 'A'
  
#print(check(1, A, B))


ans = 0
while True:
  if A:
    a = A[0]
  else:
    a = 10**9+7
  if B:
    b = B[0]
  else:
    b = 10**9+7
  if min(a, b) > K:
    break
  else:
    j =check(1, A, B)
    if j ==  'A':
      K -= A.popleft()
      ans += 1
    else:
      K -= B.popleft()
      ans += 1
      
print(ans)

### FIXED CODE ###

from bisect import *
 
N, M, K =map(int, input().split())
A  = list(map(int, input().split()))
B  = list(map(int, input().split()))

A_= [0]
for a in A:
  A_.append(A_[-1] + a)
#print(A_)

b_sum = 0
ans = 0
b_cnt = 0

while True:
  if b_sum > K:
    break
  else:
    k = K - b_sum
    ans = max(bisect_right(A_, k)-1 + b_cnt, ans)
    #print(bisect_right(A_, k)-1 + b_cnt, ans,  b_cnt)
    if b_cnt == M:
      break
    b_sum += B[b_cnt]
    b_cnt += 1
    

print(ans)
a,b = map(int,input().split())
x = a + b
y = a-b
z = a* b
print(max(x,y,z))

### FIXED CODE ###

a,b,c = map(int,input().split())
ans = c - a + b
if  ans < 0:
  print(0)
else:
  print(ans)
X = map(int, input())

happy = ((X // 500) * 1000 ) + ((X % 5) * 5)
print(happy)

### FIXED CODE ###

X = int(input())
 
num_500 = X // 500
num_5 = (X - (X // 500) * 500 ) // 5
 
print(1000*num_500 + 5 * num_5)
x = input()

counter = 0

a = [counter +=1 for i in x if i == '1']

print(counter)



### FIXED CODE ###

x = input()

counter = 0
for i in x:
    if i == '1':
        counter += 1

print(counter)
a,b=map(int,input().split())
if a>b:print(1)
  elif a==b:print(1)
    elif a<b and b%a==0:print(b//a)
      elif b==0:print(0)
        else:print(b//a+1)

### FIXED CODE ###

a,b=map(int,input().split())
if b==1:print(0)
elif a==b:print(1)
else:
    if (b-1)%(a-1)>0:print((b-1)//(a-1)+1)
    else:print((b-1)//(a-1))
S = str(input())
T = str(input())
S_d = {}
T_d = {}
for i,j in zip(S,T):
    if i in S_d and j in T_d:
        if S_d[i] == T_d[j]:
            pass
        else:
            print("No")
            break
    else:
        if i in S_d or j in T_d:
            print("No")
            break
        else:
            S_d[i] = S.count(S)
            T_d[j] = T.count(T)
        
else:
    print("Yes")

### FIXED CODE ###

a = list(map(int,input().split()))
 
print(max(a) * 9 + sum(a))
n=int(input())
num=round(n/1.08)
check=round(num*1.08)
if check==n
    print(num)
else:
    print(':(')

### FIXED CODE ###

import math
n=int(input())
num=math.ceil(n/1.08)
check=int(num*1.08)
if check==n:
    print(num)
else:
    print(':(')
import numpy as np
import sys
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

mat = np.zeros((n,n))
for x in ab:
    mat[x[0]][x[1]] = 1
    mat[x[1]][x[0]] = 1
vec = np.zeros(n)
vec[0] = 1
vec[-1] = 1
if list(mat.dot(vec)).count(2) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

ab = list(filter(lambda x:x[0]==0 or x[1]==n-1, ab))
ab0 = list(filter(lambda x:x[0]==0,ab))
abn = list(filter(lambda x:x[1]==n-1,ab))

ab0_bin = ["0"]*n
abn_bin = ["0"]*n
for x in ab0:
    ab0_bin[x[1]] = "1"
for x in abn:
    abn_bin[x[0]] = "1"

ab0_bin = "".join(ab0_bin)
abn_bin = "".join(abn_bin)

if bin(int(ab0_bin,2) & int(abn_bin, 2))[2:].count("1") > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
from scipy import misc

def cnk(n,k):
    return int(misc.comb(n,k))


# import scipy.special
# def cnk(n,k):
#     return int(scipy.special.comb(n,k))

def calculate(n,k):
    # 1. 在n+1个缝隙上，选择i个地方 Cn+1,i

    # 2. 在i个地方，放入k个球 C(k-1),(i-1)

    for i in range(1,k+1):

        a1 = cnk(n-k+1,i)
        a2 = cnk(k-1,i-1)
        print((a1 * a2) % (1000000000+7))


S = input().split(" ")

N = int(S[0])
K = int(S[1])

calculate(N,K)

### FIXED CODE ###

from scipy import misc

def cnk(n,k):
    return misc.comb(n,k,exact=True)


# import scipy.special
# def cnk(n,k):
#     return int(scipy.special.comb(n,k))

def calculate(n,k):
    # 1. 在n+1个缝隙上，选择i个地方 Cn+1,i

    # 2. 在i个地方，放入k个球 C(k-1),(i-1)

    for i in range(1,k+1):

        a1 = cnk(n-k+1,i)
        a2 = cnk(k-1,i-1)
        print((a1 * a2) % (1000000000+7))


S = input().split(" ")

N = int(S[0])
K = int(S[1])

calculate(N,K)
# -*- coding: utf-8 -*-
"""
Created on Sun May 10 21:34:02 2020

@author: shinba
"""


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

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

data = [0]*n
data[0] = 1

li = [0]

while k > 0:
    b = a[li[-1]]-1
    if data[b] == 0:
        data[b] = 1
        li.append(b)
        k -= 1
    else:
        break

if k != 0:
    for i in range(len(li)-1,-1,-1):
        if li[i] == b:
            s = b
            break
    newli = li[b:]
    l = (k-1) % len(newli)
    print(li[l]+1)
else:
    print(li[-1]+1)
    

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun May 10 21:34:02 2020

@author: shinba
"""
import sys
sys.setrecursionlimit(500000)

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

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

data = [0]*n
data[0] = 1

li = [0]

while k > 0:
    b = a[li[-1]]-1
    if data[b] == 0:
        data[b] = 1
        li.append(b)
        k -= 1
    else:
        break

if k != 0:
    for i in range(len(li)-1,-1,-1):
        if li[i] == b:
            s = i
            break
    newli = li[s:]
    l = (k-1) % len(newli)
    print(newli[l]+1)
else:
    print(li[-1]+1)
n=int(input())
v=list(map(int,input().split()))
V=v.sort()
cnt=(V[0]+V[1])/2
for i in range(2,n):
  cnt=(cnt+V[i])/2
print(cnt)

### FIXED CODE ###

n=int(input())
v=list(map(int,input().split()))
v.sort()
cnt=(v[0]+v[1])/2
if n==2:
  print((v[0]+v[1])/2)
else:
  for i in range(2,n):
    cnt=(cnt+v[i])/2
  print(cnt)
n, m = map(int, input().split())
li = []
for i in range(m):
  li.append(list(input().split()))
li_a = [0 for i in range(m)]
li_b = [0 for i in range(m)]
a = 0
b = 0
for j in range(m):
  if li[j][1] == "WA":
    li_b[int(li[j][0])] += 1
  elif li[j][1] == "AC" and li_a[j] == 0:
    a += 1
    b += li_b[int(li[j][0])]
    li_a[j] += 1
print(a, b)

### FIXED CODE ###

n, m = map(int, input().split())
li = []
for i in range(m):
  li.append(list(input().split()))
li_a = [0 for i in range(n)]
li_b = [0 for i in range(n)]
a = 0
b = 0
for j in range(m):
  if li[j][1] == "WA":
    li_b[int(li[j][0])-1] += 1
  elif li[j][1] == "AC" and li_a[int(li[j][0])-1] == 0:
    a += 1
    b += li_b[int(li[j][0])-1]
    li_a[int(li[j][0])-1] += 1
print(a, b)
n, m = map(int, input().split())
a = [input() for _ in range(n)]
b = [input() for _ in range(m)]

h = len(b)
w = len(b[0])

for i in range(h):
    for j in range(w):
        tmp = []
        for k in range(h):
            tmp.append(a[i + k][j : j + w])
        if b == tmp:
            print("Yes")
            break
    else:
        continue
    break
else:
    print("No")

### FIXED CODE ###

n, m = map(int, input().split())
a = [input() for _ in range(n)]
b = [input() for _ in range(m)]

ah = len(a)
aw = len(a[0])
bh = len(b)
bw = len(b[0])

for i in range(ah - bh + 1):
    for j in range(aw - bw + 1):
        tmp = []
        for k in range(bh):
            tmp.append(a[i + k][j : j + bw])
        if b == tmp:
            print("Yes")
            break
    else:
        continue
    break
else:
    print("No")
import pandas
import math
import numpy
import collections

x = input()
TF =  x.isupper() and x.isalpha()
flg  = 0
if(TF):
    li = [i for i in x]
    count_dict = collections.Counter(li)
    list = [v for k, v in count_dict.items()]
    
    if(list == [2,2]):
        print("Yes")
        flg = 1

if(flg == 0):
    print("No")

### FIXED CODE ###

import collections

x = input()
TF =  x.isupper() and x.isalpha()
flg  = 0
if(TF):
    li = [i for i in x]
    count_dict = collections.Counter(li)
    list = [v for k, v in count_dict.items()]
    if(list == [2,2]):
        print("Yes")
        flg = 1
if(flg == 0):
    print("No")
ef D(argN = None):
	answer = 0
	N = argN or int(input())
	if N==1:
		print(answer)
	else:
		# 素因数pを見つける。範囲は2から√Nまででよい。
		for p in range(2, int(N**0.5)+2):
			e = 0
			while (N % p == 0):
				N /= p
				e += 1
			# z=p**eが見つかった
			if e>0:
				# eを1, 2, 3, 4...に分けられる回数カウント
				for i in range(1, e+1):
					if e >= 1:
						e -= i
						answer += 1
		# もし素因数が見つからなかった場合、N自身を素数ととらえて1回カウント
		if answer==0:
			answer = 1
		print(answer)
        
D()

### FIXED CODE ###

def resolve():
	answer = 0
	N = int(input())
	if N==1:
		print(answer)
	else:
		# 素因数pを見つける。範囲は2から√Nまででよい。
		for p in range(2, int(N**0.5)+2):
			e = 0
			while (N % p == 0):
				N /= p
				e += 1
			# z=p**eが見つかった
			if e>0:
				# eを1, 2, 3, 4...に分けられる回数カウント
				for i in range(1, e+1):
					if e >= i:
						e -= i
						answer += 1
		# √Nまでで割り切れなかった場合、N自身が素数
		if N!=1:
			answer += 1
		print(answer)
        
resolve()