Harryxun/stf_run huggingface dataset:
num = (10 ** 9) + 7

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

if n == 1:
    print(1)
    exit()

prime_upper = int(m ** (1/2) + 50)
prime_dict = {}

check = [False] * prime_upper
prime = [2]

while m % 2 == 0:
    m //= 2
    if not 2 in prime_dict.keys():
        prime_dict[2] = 0
    prime_dict[2] += 1

for j in range(2, prime_upper, 2):
    check[j] = True

for i in range(3, prime_upper, 2):
    if not check[i]:
        prime.append(i)
        while m % i == 0:
            m //= i
            if not i in prime_dict.keys():
                prime_dict[i] = 0
            prime_dict[i] += 1

        for j in range(i, prime_upper, i):
            check[j] = True

if len(prime_dict.values()) != 0:
    value_max = max(prime_dict.values())
    com2 = [[0] * (value_max + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, value_max + 1):
            if i == 1:
                com2[i][j] = 1
            elif j == 1:
                com2[i][j] = i
            else:
                com2[i][j] = (com2[i][j - 1] + com2[i - 1][j]) % num
    if m != 1:
        ans = n
    else:
        ans = 1
    for key, value in prime_dict.items():
        ans = (ans * com2[n][value]) % num
else:
    print(n)

print(ans)

### FIXED CODE ###

num = (10 ** 9) + 7

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

if m == 1:
    print(1)
    exit()

prime_upper = int(m ** (1/2) + 50)
prime_dict = {}

check = [False] * prime_upper
prime = [2]

while m % 2 == 0:
    m //= 2
    if not 2 in prime_dict.keys():
        prime_dict[2] = 0
    prime_dict[2] += 1

for j in range(2, prime_upper, 2):
    check[j] = True

for i in range(3, prime_upper, 2):
    if not check[i]:
        prime.append(i)
        while m % i == 0:
            m //= i
            if not i in prime_dict.keys():
                prime_dict[i] = 0
            prime_dict[i] += 1

        for j in range(i, prime_upper, i):
            check[j] = True

if len(prime_dict.values()) != 0:
    value_max = max(prime_dict.values())
    com2 = [[0] * (value_max + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, value_max + 1):
            if i == 1:
                com2[i][j] = 1
            elif j == 1:
                com2[i][j] = i
            else:
                com2[i][j] = (com2[i][j - 1] + com2[i - 1][j]) % num
    if m != 1:
        ans = n
    else:
        ans = 1
    for key, value in prime_dict.items():
        ans = (ans * com2[n][value]) % num
    print(ans)
else:
    print(n)
s=input()
for i in range(len(s)):
  if s[i]=="0":
    z+=1
  else:
    o+=1
print(2*min(0,1))

### FIXED CODE ###

s=input()
z,o=0,0
for i in range(len(s)):
  if s[i]=="0":
    z+=1
  else:
    o+=1
print(2*min(z,o))
n = int(input())
sum_money = 0
for i in range(n):
  x,u = map(input())
  int_x = float(x)
  
  if u == 'BTC':
    int_x *= 380000.0
  sum_money += int_x
print(sum_money)

### FIXED CODE ###

n = int(input())
sum_money = 0
for i in range(n):
  x,u = input().split()
  int_x = float(x)
  
  if u == 'BTC':
    int_x *= 380000.0
  sum_money += int_x
print(sum_money)
import sys

input = sys.stdin.readline

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

sc = []
dic = dict()
for _ in range(M):
    sc.append(list(map(int, input().split())))

sc.sort(key=lambda x:x[0])

if sc[-1][0] > N:
    print(-1)
    exit()

for i in range(M):
    if sc[i][0] not in dic.keys():
        dic[sc[i][0]] = sc[i][1]
    elif dic[sc[i][0]] != sc[i][1]:
        print(-1)
        exit()

if N == 1:
    if sc[0][0] == 1 and sc[0][1] == 0:
        print(0)
        exit()
else:
    if sc[0][0] == 1 and sc[0][1] == 0:
        print(-1)
        exit()

ans = ['a'] * N

try:
    for i in range(M):
        ans[sc[i][0]-1] = sc[i][1] 
except:
    print(-11)
    exit()

if ans[0] == 'a':
    ans[0] = 1
if ans[1] == 'a':
    ans[1] = 0
if ans[2] == 'a':
    ans[2] = 0 

out = ""
for i in range(N):
    out += str(ans[i])

print(int(out))

### FIXED CODE ###

import sys

input = sys.stdin.readline

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

if M == 0:
    ans = 0
    if N == 2:
        ans = 10
    if N == 3:
        ans = 100
    print(ans)
    exit()

sc = []
dic = dict()
for _ in range(M):
    sc.append(list(map(int, input().split())))

sc.sort(key=lambda x:x[1])
sc.sort(key=lambda x:x[0])

if sc[-1][0] > N:
    print(-1)
    exit()

for i in range(M):
    if sc[i][0] not in dic.keys():
        dic[sc[i][0]] = [sc[i][1]]
    elif sc[i][1] not in dic[sc[i][0]]:
        dic[sc[i][0]].append(sc[i][1])

for value in dic.values():
    if len(value) > 1:
        print(-1)
        exit()

if N == 1:
    if sc[0][0] == 1 and sc[0][1] == 0:
        print(0)
        exit()
else:
    if sc[0][0] == 1 and sc[0][1] == 0:
        print(-1)
        exit()

ans = ['a'] * N

for i in range(M):
    ans[sc[i][0]-1] = sc[i][1] 

if ans[0] == 'a':
    ans[0] = 1
for i in range(len(ans)):
    if ans[i] == 'a':
        ans[i] = 0

out = ""
for i in range(len(ans)):
    out += str(ans[i])

print(int(out))
mod = 10**9 +7
n,m = map(int,input().split())
stairs = [1 for _ in range(n)]
memo = [0 for _ in range(n)]
for _ in range(m):
    a = int(input()) - 1
    stairs[a] = 0
memo[0] = stairs[0]
if stairs[1]:
    memo[1] = stairs[1] + memo[0]
for i in range(2,n):
    if stairs[i]:
        memo[i] = (memo[i-1] +memo[i-2])%mod
    else:
        memo[i] = 0
print(memo[n-1])

### FIXED CODE ###

mod = 10**9 +7
n,m = map(int,input().split())
stairs = [1 for _ in range(n)]
memo = [0 for _ in range(n)]
for _ in range(m):
    a = int(input()) - 1
    stairs[a] = 0
memo[0] = stairs[0]
if n ==1:
    print(memo[0])
    exit()
if stairs[1]:
    memo[1] = stairs[1] + memo[0]
if n==2:
    print(memo[1])
    exit()
for i in range(2,n):
    if stairs[i]:
        memo[i] = (memo[i-1] +memo[i-2])%mod
    else:
        memo[i] = 0
print(memo[n-1])
s = input().split()

if s[0] < s[1]:
  s1 = s[0]
  s2 = s[1]
else:
  s1 = s[1]
  s2 = s[0]
  
result = 0
if (s2-s1) > 2:
  result = s2*2 - 1
else (s2-s1) = 1:
  result = s2 + s1

print(result)

### FIXED CODE ###

s = input().split()
 
if int(s[0]) < int(s[1]):
  s1 = int(s[0])
  s2 = int(s[1])
else:
  s1 = int(s[1])
  s2 = int(s[0])
  
result = 0
if (s2-s1) >= 2:
  result = s2*2 - 1
else:
  result = s2 + s1
 
print(result)
raw_data = raw_input()

data = raw_data.split('\n')

n = data.pop(0)

max_v = 1000000000
min_v = -1000000000
for i, r in enumerate(data):
    max_v = max(max_v, r - min_v)
    min_v = min(min_v, r)

print(max_v) 

### FIXED CODE ###

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

min_value = data.pop(0)
earn_value = -1000000000000
for d in data:
    earn_value = max(d - min_value, earn_value)
    min_value = min(d, min_value) 
print(earn_value)
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N, K = map(int, input().split())
A = list(map(int, input().split()))
result = 0
for i in range(N):
    for j in range(i):
        if A[i-j-1] > A[i-j]:
            tmp = A[i-j]
            A[i-j] = A[i-j-1]
            A[i-j-1] = tmp
        print(A)

for i in range(K):
    result += A[i]

print(result)



### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

N, K = map(int, input().split())
A = list(map(int, input().split()))
result = 0
for i in range(N):
    for j in range(i):
        if A[i-j-1] > A[i-j]:
            tmp = A[i-j]
            A[i-j] = A[i-j-1]
            A[i-j-1] = tmp

for i in range(K):
    result += A[i]

print(result)
taka_def = int(list[0])
taka_off = int(list[1])
aoki_def = int(list[2])
aoki_off = int(list[3])

if taka_def - aoki_off <=0:
	list[0] = taka_def - aoki_off
	print('No')
else:
	list[2] = aoki_def - taka_off
	if aoki_def - taka_off <=0:
		print('Yes')
	else:
		list[0] = taka_def - aoki_off
		if taka_def - aoki_off <=0:
			print('No')
		else:
			list[2] = aoki_def - taka_off
			print('Yes')


### FIXED CODE ###

import math
A, B, C, D = map(int, input().split())
if math.ceil(C/B) <= math.ceil(A/D):
  print('Yes')
else:
  print('No')
from scipy.special import comb

n, k = map(int, input().split(' '))
a = list(map(int, input().split(' ')))

Min = 0
Max = 0

a_sort = sorted(a)
for i, num in enumerate(a_sort):
    if i >= k-1:
        Min += comb(i, k-1, exact=True) * num
    if n-i >= k:
        Max += comb(n-i-1, k-1, exact=True) * num

print(int((Min - Max) % (10e08+7)))
print(Min - Max)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
 
class Combination():
    # コンストラクタ
    def __init__(self, N:int, P:int):
        self.N = N
        self.P = P
 
        # fact[i] = (i! mod P)
        self.fact = [1, 1]   
        # factinv[i] = ((i!)^(-1) mod P)
        self.factinv = [1, 1]
        # factinv 計算用
        self.inv = [0, 1]    
 
        for i in range(2, N+1):
            self.fact.append((self.fact[-1] * i) % P)
            self.inv.append((-self.inv[P % i] * (P // i)) % P)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % P)
    
    # nCk (mod P)   (ただし、n<=N)
    def getComb(self, n:int, k:int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] * self.factinv[n-k] % self.P
 
def main():
    N,K = map(int,input().split())
    A = sorted([int(i) for i in input().split()])
 
    mod = 10**9+7
 
    COMB = Combination(N,mod)
 
    cmb = [0] * (N-K+1)
    for i in range(N-K+1):
        cmb[i] = COMB.getComb(i+(K-1),K-1)
 
    sum_max = 0
    for i in range(K-1,N):
        sum_max = (sum_max + cmb[i-(K-1)] * A[i]) % mod
 
    sum_min = 0
    for i in range(N-K,-1,-1):
        sum_min = (sum_min + cmb[(N-K)-i] * A[i]) % mod
 
    answer = sum_max - sum_min
    print(answer % mod)
 
if __name__ == "__main__":
    main()
# -*- coding: utf-8 -*-
from scipy.special import comb

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

mod = int(10 ** 9 + 7)

for i in range(1, k + 1):
    if i > n - k + 1:
        print(0)
    else:
        print(comb(k - 1, i - 1) * comb(n - k + 1, i) % mod)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

n, m = map(int, input().split())
g = [[] for _ in range(3 * n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    # u0 -> v1
    g[3 * u].append(3 * v + 1)
    # u1 -> v2
    g[3 * u + 1].append(3 * v + 2)
    # u2 -> v0
    g[3 * u + 2].append(3 * v)

s, t = map(int, input().split())
s = 3 * (s - 1)
t = 3 * (t - 1)

depth = dict()
depth[s] = 0
q = deque([s])


while(len(q) != 0):
    v = q.popleft()
    for u in g[v]:
        if u not in depth:
            q.append(u)
            depth[u] = depth[v] + 1

print(depth[t] // 3 if t in depth else -1)
import string
a = 0
b = 0
while True:
    n = input()
    i = 0
    if n != 0:
        while i != n:
            set = raw_input().split()
            set[0] = int(set[0])
            set[1] = int(set[1])

            if set[0] == set[1]:
                a += set[0]
                b += set[1]

            elif set[0] > set[1]:
                a += ( set[0] + set[1] )
            else:
                b += ( set[0] + set[1] )

            i += 1

        print a,b
    else:
        n=0

### FIXED CODE ###

printlist = []
while True:
    n = input()
    if n == 0:
        break
    a = 0
    b = 0
    i = 0
    if n != 0:
        while i != n:
            set = raw_input().split()
            set[0] = int(set[0])
            set[1] = int(set[1])

            if set[0] == set[1]:
                a += set[0]
                b += set[1]

            elif set[0] > set[1]:
                a += ( set[0] + set[1] )
            else:
                b += ( set[0] + set[1] )

            i += 1

        printlist.append(a)
        printlist.append(b)
    else:
        break

#print 'hoge'
p = len(printlist)
i = 0
while i != p:
    print printlist[i],printlist[i+1]
    i += 2
n = int(input())
h = list(map(int,input().split()))
ans=1
for j in range(1,n):
    if(h[j]>=h[0]:
       ans+=1
print(ans)

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
ans=1
tp=h[0]
for j in range(1,n):
    if(h[j]>=tp):
        tp=h[j]
        ans+=1
print(ans)
a, b, c = map(int, input().split())

if a < b amd b < c:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

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

if a < b and b < c:
  print("Yes")
else:
  print("No")
X=int(input())
if X=3 or X=5 or X=7:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

X=int(input())
if X==3 or X==5 or X==7:
  print('YES')
else:
  print('NO')
#149d

def win(n):
	if n=='r':
		return p
	elif n=='s':
		return r
	else:
		return s

n,k=map(int,input().split())
r,s,p=map(int,input().split())
t=input()
score=0
for i in t:
	score += win(i)

#hands=list(t)

for i in range(n):
	if i+k<n:
		if t[i]==t[i+k]:
			score-=win(t[i+k])
			t[i+k]='x'
print(score)

### FIXED CODE ###


def win(n):
	if n=='r':
		return p
	elif n=='s':
		return r
	else:
		return s

n,k=map(int,input().split())
r,s,p=map(int,input().split())
t=input()
score=0
for i in t:
	score += win(i)

hands=list(t)

for i in range(n):
	if i+k<n:
		if hands[i]==hands[i+k]:
			score-=win(hands[i+k])
			hands[i+k]='x'
print(score)
n,m = input().split(" ")
n = int(n)
m = int(m)

arr = [[] for _ in range(m)]

for i in range(n):
  a,b = input().split(" ")
  a = int(a) -1
  b = int(b)
  
  if a > m:
    continue
  arr[a].append(b)

vs = []
res = 0
for item in arr:
  vs[len(vs):len(vs)] = item
  if len(vs) == 0:
    continue
    
  vs.sort()
  maxi = vs.pop(-1)
  res += maxi
  
print(res)

### FIXED CODE ###

import heapq
n,m = input().split(" ")
n = int(n)
m = int(m)

arr = [[] for _ in range(m)]

for i in range(n):
  a,b = input().split(" ")
  a = int(a)
  b = - int(b) # for heap
  
  if a > m:
    continue
    
  arr[a-1].append(b)

vs = []
heapq.heapify(vs)

res = 0
for item in arr:
  for v in item:
	  heapq.heappush(vs, v)
  
  if len(vs) == 0:
    continue
    
  maxi = heapq.heappop(vs)
  res += (-1* maxi)
  
print(res)
import collections
s = input()
alphabet = "abcdefghijklmnopqrstuvwxyz"
dif = sorted(list(set(alphabet) - set(s)))
if len(s) > 26:
    print(-1)
elif 0 < len(dif):
    if len(s) == len(set(s)):
        print(s + dif[0])
    else:
        print(-1)
else:
    if alphabet[::-1] == s:
        print(-1)
    else:
        tmp = [s]
        for i in range(25):
            if s[i] == alphabet[i]:
                continue
            else:
                tmp.append(s[:i-1] + alphabet[i])
        tmp.sort()
        print(tmp[tmp.index(s)+1])

### FIXED CODE ###

s = input()+chr(ord("a")-1)
ans = -1
for i in range(len(s)):
    t = s[:~i]
    dif = set(map(chr,range(ord(s[~i])+1,123))) - set(t)
    if dif:
        ans = t + min(dif)
        break
print(ans)
a,b = map(int,input().split())
print(max(a+b,a-ba*b))

### FIXED CODE ###

a,b = map(int,input().split())
print(max(a+b,a-b,a*b))
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *



N=int(input())
LR=[list(map(int,input().split())) for i in range(N)]
for i in range(N):
    LR[i][1]+=1

value=max([R-L for L,R in LR])
#LR=sorted(LR,key=lambda x:x[1])
LR=sorted(LR,key=lambda x:x[0]*10**9+x[1])
a=2*(10**9)
minRlst=[a for i in range(N)]
minRlst[-1]=LR[-1][1]
maxLlst=[0 for i in range(N)]
maxLlst[0]=LR[0][0]
for i in range(N-2,-1,-1):
    minRlst[i]=min(minRlst[i+1],LR[i][1])
for i in range(1,N):
    maxLlst[i]=max(minRlst[i-1],LR[i][0])
L1,R1=LR[0]
L2,R2=LR[-1][0],minRlst[1]
maxR=from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *



N=int(input())
LR=[list(map(int,input().split())) for i in range(N)]
for i in range(N):
    LR[i][1]+=1

value=max([R-L for L,R in LR])
#LR=sorted(LR,key=lambda x:x[1])
LR=sorted(LR,key=lambda x:x[0]*10**9+x[1])
a=2*(10**9)
minRlst=[a for i in range(N)]
minRlst[-1]=LR[-1][1]
maxLlst=[0 for i in range(N)]
maxLlst[0]=LR[0][0]
for i in range(N-2,-1,-1):
    minRlst[i]=min(minRlst[i+1],LR[i][1])
for i in range(1,N):
    maxLlst[i]=min(minRlst[i-1],LR[i][0])
L1,R1=LR[0]
L2,R2=LR[-1][0],minRlst[1]
minR=min([R for L,R in LR])
for i in range(0,N-1):
    L,R=LR[i]
    a=max(R-L,0)
    b=max(minR-LR[-1][0],0)
    value=max(value,a+b)
    L1=L
    R1=min(R1,R)
    R2=minRlst[i+1]
    a=max(R1-L1,0)
    b=max(R2-L2,0)
    value=max(value,a+b)
print(value)
([R for L,R in LR])
for i in range(0,N-1):
    L,R=LR[i]
    a=max(R-L,0)
    b=max(maxR-LR[-1][0],0)
    value=max(value,a+b)
    L1=L
    R1=min(R1,R)
    R2=minRlst[i+1]
    a=max(R1-L1,0)
    b=max(R2-L2,0)
    value=max(value,a+b)
print(value)


### FIXED CODE ###

from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *



N=int(input())
LR=[list(map(int,input().split())) for i in range(N)]
for i in range(N):
    LR[i][1]+=1

value=max([R-L for L,R in LR])
#LR=sorted(LR,key=lambda x:x[1])
LR=sorted(LR,key=lambda x:x[0]*10**9+x[1])
a=2*(10**9)
minRlst=[a for i in range(N)]
minRlst[-1]=LR[-1][1]
maxLlst=[0 for i in range(N)]
maxLlst[0]=LR[0][0]
for i in range(N-2,-1,-1):
    minRlst[i]=min(minRlst[i+1],LR[i][1])
for i in range(1,N):
    maxLlst[i]=max(minRlst[i-1],LR[i][0])
L1,R1=LR[0]
L2,R2=LR[-1][0],minRlst[1]
maxR=min([R for L,R in LR])
for i in range(0,N-1):
    L,R=LR[i]
    a=max(R-L,0)
    b=max(maxR-LR[-1][0],0)
    value=max(value,a+b)
    L1=L
    R1=min(R1,R)
    R2=minRlst[i+1]
    a=max(R1-L1,0)
    b=max(R2-L2,0)
    value=max(value,a+b)
print(value)
import sys
readline = sys.stdin.readline

N, A, B, C = map(int, readline().split())
S = [readline().strip() for i in range(N)]

AB, AC, BC = 'AB', 'AC', 'BC'

n0 = [A, B, C].count(0)

F = [A, B, C]
H = ['A', 'B', 'C']
G = {AB: (0, 1), BC:(1,2), AC:(0, 2)}

if n0 == 3:
    print('No')
elif n0 == 2 and sum([A, B, C]) == 1:
    path = []
    for com in S:
        a,b = G[com]
        if F[a] == F[b] == 0:
            print('No')
            exit(0)
        else:
            if F[a] == 1:
                a,b = b,a
            path.append(H[a])
            F[a] += 1
            F[b] -= 1
    print('Yes')
    for p in path:
        print(p)
else:
    if (S[0] == AB and A == 0 and B == 0) or \
     (S[0] == AC and A == 0 and C == 0) or (S[0] == BC and B == 0 and C == 0):
        print('No')
        exit(0)

    path = []
    for i,com in enumerate(S):
        a,b = G[com]
        if a == 0 or b == 0:
            if b == 0:
                a,b = b,a
            path.append(H[a])
            F[a] += 1
            F[b] -= 1
        else:
            if i < len(S) - 1 and H[a] == H[b]:
                if b in G[S[i + 1]]:
                    a, b = b, a
                path.append(H[a])
                F[a] += 1
                F[b] -= 1
            else:
                if F[a] > F[b]:
                    a,b = b,a
                path.append(H[a])
                F[a] += 1
                F[b] -= 1
        assert all(v >= 0 for v in F)
    print('Yes')
    for p in path:
        print(p)
                




### FIXED CODE ###

import sys
readline = sys.stdin.readline

N, A, B, C = map(int, readline().split())
S = [readline().strip() for i in range(N)]

AB, AC, BC = 'AB', 'AC', 'BC'

n0 = [A, B, C].count(0)

F = [A, B, C]
H = ['A', 'B', 'C']
G = {AB: (0, 1), BC:(1,2), AC:(0, 2)}

if n0 == 3:
    print('No')
elif n0 == 2 and sum([A, B, C]) == 1:
    path = []
    for com in S:
        a,b = G[com]
        if F[a] == F[b] == 0:
            print('No')
            exit(0)
        else:
            if F[a] == 1:
                a,b = b,a
            path.append(H[a])
            F[a] += 1
            F[b] -= 1
    print('Yes')
    for p in path:
        print(p)
else:
    if (S[0] == AB and A == 0 and B == 0) or \
     (S[0] == AC and A == 0 and C == 0) or (S[0] == BC and B == 0 and C == 0):
        print('No')
        exit(0)

    path = []
    for i,com in enumerate(S):
        a,b = G[com]
        if F[a] == 0 or F[b] == 0:
            if F[b] == 0:
                a,b = b,a
            path.append(H[a])
            F[a] += 1
            F[b] -= 1
        else:
            if i < len(S) - 1 and F[a] == F[b]:
                if b in G[S[i + 1]]:
                    a, b = b, a
                path.append(H[a])
                F[a] += 1
                F[b] -= 1
            else:
                if F[a] > F[b]:
                    a,b = b,a
                path.append(H[a])
                F[a] += 1
                F[b] -= 1
        assert all(v >= 0 for v in F)
    print('Yes')
    for p in path:
        print(p)
y = x ** 3
print y

### FIXED CODE ###

x = input()
print x ** 3
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)

    if temp!=1:
        arr.append(temp)

    if arr==[]:
        arr.append(n)

    return arr

#import numpy as np

a, b = map(int, input().split())
if a==1 and b==1:
    print(1)
else:
    #print(factorization(a))
	prime_a = factorization(a)
	prime_b = factorization(b)
	#print(prime_a, prime_b)
	print(1+len(set(prime_a)&set(prime_b)))

### FIXED CODE ###

n = int(input())

if n%2==0:
    print(1/2)
else:
    print((n+1)/2/n)
from operator import itemgetter

N,T=map(int,input().split())
a=[]
for i in range(N):
    c,t=map(int,input().split())
    a.append([c,t])

a=sorted(a,key=itemgetter(1))

key=0
ans=1001
while a[key][1]<=T:
    ans = min(ans,a[key][0])
    key += 1

if ans==1001:
    print('TLE')
else:
    print(ans)




    
      


### FIXED CODE ###

N,T=map(int,input().split())
a=[]
for i in range(N):
    c,t=map(int,input().split())
    a.append([c,t])

cost=10000
for i in range(N):
    if a[i][1] <= T:
        cost = min(cost,a[i][0])



if cost==10000:
    print('TLE')
else:
    print(cost)
def f(s):
    if s == "":
        return []
    if s[0] == "1": 
        if "0" in s:
            i = s.index("0")
            return [len(s[:i])]+f(s[i:])
        else:
            return [len(s)]
    else:
        if "1" in s:
            i = s.index("1")
            return [-len(s[:i])]+f(s[i:])
        else:
            return [-len(s)]
from itertools import accumulate
N,K = map(int,input().split())
S = input()
ls = f(S)
inds = []
for i in range(len(ls)):
    if ls[i] < 0:
        inds.append(i)
acc1 = [0]+list(accumulate(ls, lambda x,y:max(x,0)+max(0,y)))
if acc1[1] < 0:
    acc1[1] *= -1
acc2 = [0]+list(accumulate([-ls[i] for i in inds], lambda x,y:x+y))
ans = max(ls)

for i in range(len(inds)-K+1):
    #print(acc2[i+K]-acc2[i], acc1[min(inds[i+K-1]+2, len(acc1)-1)],acc1[max(inds[i]-1,0)])
    ans = max(acc2[i+K]-acc2[i]+acc1[min(inds[i+K-1]+2, len(acc1)-1)]-acc1[max(inds[i]-1,0)], ans)
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
s = input()
ls = []
i = 0
c = 0
while i < N and s[i] == "1":
    c += 1
    i += 1
if i==N:
    print(N)
    exit()
while i < N:
    l = c
    c = 0
    while i < N and s[i] == "0":
        c += 1
        i += 1
    m = c
    c = 0
    while i < N and s[i] == "1":
        c += 1
        i += 1
    r = c
    ls.append((l,m,r))
K = min(K, len(ls))
from itertools import accumulate
acc = list(accumulate([0]+ls, lambda x,y:x+y[1]+y[2]))
ans = 0
for i in range(len(ls)-K+1):
    ans = max(ans, acc[i+K]-acc[i]+ls[i][0])
print(ans)