Harryxun/stf_run huggingface dataset:
import time

# success
# https://atcoder.jp/contests/abc151/tasks/abc151_e
# https://blogarithms.github.io/articles/2019-01/fermats-theorem


MOD =  1000000007
MOD2 = 1000000005
MAX = 100001

# facs = [1 for _ in range(MAX)]



"""for i in range(1, MAX):
	facs[i] = (facs[i-1] * i) % MOD"""


def get_facs(n, k):
	if k<n-k:
		k = n-k
	r = 1
	for i in range(k+1, n+1):
		r *= i
	for i in range(2, n-k+1):
		r /= i
	return r

def choose(n, k):

	if k==0 or n==k:
		return 1
	if n==0:
		return 0
	if k>n:
		return 0
	return get_facs(n, k)



def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return abs(numbers[0] - numbers[-1])

	score = 0
	for i, x in enumerate(numbers):
		score += ((choose(i, K-1) - choose(N-1-i, K-1)) * x)

	return int(score%MOD)
	
	
print(main())


### FIXED CODE ###

print(chr(1+ord(input())))
def isBingo(a):
    for i in range(3)
        if a[i][0] == a[i][1] and a[i][0] == a[i][2]:
            return 'Yes'
        elif a[0][i] == a[1][i] and a[i][0] == a[2][i]:
            return 'Yes'
    if a[0][0] == a[1][1] and a[0][0] == a[2][2]:
        return 'Yes'
    elif a[0][2] == a[1][1] and a[0][2] == a[2][0]
        return 'Yes'
    else:
        return 'No'
    
a = []
for i in range(3):
    a.append(list(map(int, input().split())))
n = int(input())
b = []
for i in range(n):
    b.append(int(input()))

for i in range(n):
    for j in range(3):
        if b[i] in a[j]:
            a[j][a[j].index(b[i])] = -1

print(isBingo(a))

### FIXED CODE ###

def isBingo(a):
    for i in range(3):
        if a[i][0] == a[i][1] and a[i][0] == a[i][2] and a[i][0] == -1:
            return 'Yes'
        elif a[0][i] == a[1][i] and a[0][i] == a[2][i] and a[0][i] == -1:
            return 'Yes'
    if a[0][0] == a[1][1] and a[0][0] == a[2][2] and a[0][0] == -1:
        return 'Yes'
    elif a[0][2] == a[1][1] and a[0][2] == a[2][0] and a[0][2] == -1:
        return 'Yes'
    else:
        return 'No'
    
a = []
for i in range(3):
    a.append(list(map(int, input().split())))
n = int(input())
b = []
for i in range(n):
    b.append(int(input()))

for i in range(n):
    for j in range(3):
        if b[i] in a[j]:
            a[j][a[j].index(b[i])] = -1

print(isBingo(a))
n,m=map(int,input().split())
graph=[[False]*n for i in range(n)] #点の隣接連結を示す
color=[0]*n
visited=[False]*n #dfsを書くときに訪問した点を記録する
for i in range(m):
    a,b,c=map(int,input().split())
    graph[a-1][b-1][0],graph[b-1][a-1][0],graph[a-1][b-1][1],graph[b-1][a-1][1]=True,True,c,c
def dfs(v):
    visited[v]=True
    for i in range(n):
        if graph[v][i]==False:continue
        if visited[i]==True:continue
        color[i]=color[v]^(graph[v][i]%2)
        dfs(i)#訪問済みでなく辺によってつながれている頂点に対して同じ操作を繰り返す
for i in range(n):
  dfs(i)
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n=int(input())
graph=[[] for i in range(n)]
color=[-1]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    graph[a-1].append([b-1,c%2])
    graph[b-1].append([a-1,c%2])
def coloring(pre,c):
  color[pre]=c
  for i,j in graph[pre]:
    if color[i]<0:
      coloring(i,color[pre]^j)
coloring(0,1)
for i in color:
  print(i)
import sys
n,t=map(int,input().split())
T=[int(i) for i in sys.stdin]
endtime=0
for i in t:
  if endtime>i+t:
    endtime=endtime-(endtime-i)+t
print(endtime)

### FIXED CODE ###

import sys
n,t=map(int,input().split())
T=list(map(int,input().split()))
ans=0
starttime=0
endtime=0
for i in T:
  if endtime>=i:
    endtime=endtime-(endtime-i)+t
  else:
    ans+=endtime-starttime
    starttime=i
    endtime=i+t
ans+=endtime-starttime
print(ans)
D = int(input())
# with open("sample1.in") as f:

last = [0 for i in range(26)]
s = [[0 for j in range(26)] for i in range(D)]
c = list(map(int, input().split(" ")))
# for i in range(26):
#    c[i] = int(input())
result=[]
# opened = []  #開催したやつを保存
for i in range(D):
    a = list(map(int, input().split(" ")))
    for j, k in enumerate(a):
        #print(i, j, k)
        s[i][j] = int(k)
        # スコア計算
    score = 0
    score_index = 0
    for j in range(26):
        if j == 0:
            score_max = s[i][j] - (i + 1 - last[j]) * c[j]
            score_index = 0
        else:
            score = s[i][j] - (i + 1 - last[j]) * c[j]
            if score_max < score:
                score_max = score
                score_index = j
    result.appned(score_index)
    #print(score_index, score)
    last[score_index] = i
    # print(a.index(max(a)))

for i in range(D):
    # print(s.index(max(s[i])))
    print(result[i])



### FIXED CODE ###

# coding: utf-8
# Your code here!

D = int(input())
# with open("sample1.in") as f:

#c = [0 for i in range(26)]
s = [[0 for j in range(27)] for i in range(D)]
c = list(map(int, input().split(" ")))
result=[]
# for i in range(26):
#    c[i] = int(input())
for i in range(D):
    a = list(map(int, input().split(" ")))
    for j, k in enumerate(a):
        #print(i, j, k)
        s[i][j] = int(k)
    result.append(a.index(max(a))+1)
    #print(a.index(max(a)))

for i in range(D):
    # print(s.index(max(s[i])))
    print(result[i])
import numpy
q=int(input())
for i in range(q):
    x,d,n=map(int,input().split())
    a=numpy.arange(x,x+d*(n-1)+1,d)
    print(a.prod()%1000003)

### FIXED CODE ###

q=int(input())
m=10**6+3
f=[1]
for i in range(1,m):
    f.append(f[-1]*i%m)
for i in range(q):
    x,d,n=map(int,input().split())
    if d==0:
        print(pow(x,n,m))
    else:
        t=x*pow(d,m-2,m)%m
        if t==0 or t+n-1>=m:
            print(0)
        else:
            print(f[t+n-1]*pow(f[t-1],m-2,m)*pow(d,n,m)%m)
s = input()
i = 0
now = s[0]
ans = 1
while i <len(s)-1:
    if len(now)==2:
        now = s[i+1]
        i += 1
        ans+=1
    if len(now)==1:
        if now != s[i+1]:
            now = s[i+1]
            i +=1
            ans+=1
        else:
            if i+2 <= len(s)-1:
                now = s[i+1:i+3]
                ans +=1
            i +=2
print(ans)


### FIXED CODE ###

s = input()
i = 1
now = s[0]
ans = 1
while i <=len(s)-1:
    if i >=len(s):
        break
    if len(now)==2:
        now = s[i]
        i += 1
        ans+=1
        continue
    if len(now)==1:
        if now != s[i]:
            now = s[i]
            i +=1
            ans+=1
        else:
            if i+2 <= len(s):
                now = s[i:i+2]
                ans +=1
            i +=2
            continue
print(ans)
n = int(input())
v = map(int,input().split())
c = map(int,input().split())
maxbenefit = 0
for i in range(n):
    if c[i]<v[i]:
        maxbenefit += v[i]-c[i]
print(maxbenefit)

### FIXED CODE ###

n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))
maxbenefit = 0
for i in range(n):
    if c[i]<v[i]:
        maxbenefit += v[i]-c[i]
print(maxbenefit)
a = list(map(int,input().split()))
a.sort()
print(abs(a[0]-a[1])+abs(a[1]-a[2]))

### FIXED CODE ###

s = list(input())
t = list(input())

for i in range(len(s)):
    a = s[-1]
    s.pop(-1)
    s.insert(0,a)
    a = []
    if s == t:
        print("Yes")
        exit()
print("No")
s = input()

if s = "ABC":
  print("ARC")
else:
  print("ABC")


### FIXED CODE ###

s = input()

if s == "ABC":
  print("ARC")
else:
  print("ABC")
# coding: utf-8
# Your code here!
import itertools
N = int(input())
balls = []
for i in range(N):
    l = list(map(int,input().split()))	
    balls.append(l)

d = list(itertools.permutations(balls, 2))

#print(d)

dic = {}

for i in range(len(d)):
   p = d[i][1][0] - d[i][0][0]
   q = d[i][1][1] - d[i][0][1]
   dic[str(p) + "," + str(q)] = 0
   
for i in range(len(d)):
   p = d[i][1][0] - d[i][0][0]
   q = d[i][1][1] - d[i][0][1]
   
   dic[str(p) + "," + str(q)] += 1

max_num = max(dic.values())
#p_q = max(dic.items(), key = lambda x:x[1])[0]

#p,q = map(int,p_q.split(","))

#print(max_num)

ans = N - max_num
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
import itertools
N = int(input())
balls = []
for i in range(N):
    l = list(map(int,input().split()))	
    balls.append(l)

d = list(itertools.permutations(balls, 2))

#print(d)
if N == 1:
    print(1)
    sys.exit()
    

dic = {}

for i in range(len(d)):
   p = d[i][1][0] - d[i][0][0]
   q = d[i][1][1] - d[i][0][1]
   dic[str(p) + "," + str(q)] = 0
   
for i in range(len(d)):
   p = d[i][1][0] - d[i][0][0]
   q = d[i][1][1] - d[i][0][1]
   dic[str(p) + "," + str(q)] += 1

dic[str(0) + "," + str(0)] = -1


max_num = max(dic.values())
ans = N - max_num
p_q = max(dic.items(), key = lambda x:x[1])[0]
p,q = map(int,p_q.split(","))

#if p == 0 && q == 0:
    
#print(max_num)


print(ans)
import sys
read = sys.stdin.buffer.read

import heapq
mod = 10**9+7
n, *clst = map(int, read().split())
if n == 1:
  print(2*clst[0] % mod)
  quit()
heapq.heapify(clst)
import numpy as np
clst=np.sort(clst)
d=2**(n-2)
start = 2**(n-1)+(n-1)*d
end = 2**(n-1)-1
q=np.arange(start,end,-d)

res=np.sum(clst*q)
print(2**n*res % mod)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
mod=10**9+7
n, *clst = map(int, read().split())
if n == 1:
  print(clst[0]*2%mod)
  quit()
clst.sort(reverse=True)
res=sum(i*item for i, item in enumerate(clst,2))
print((4**(n-1)*res)%mod)
import sys

inp=input().split(" ")
thp=int(inp[0])
tat=int(inp[1])
ahp=int(inp[2])
aat=int(inp[3])

for i in range(100);
  ahp-=tat
  if ahp<=0;
    print("Yes")
    sys.exit()
  thp-=aat
  if thp<=0;
    print("Yes")
    sys.exit()

### FIXED CODE ###

import sys

inp=input().split(" ")
thp=int(inp[0])
tat=int(inp[1])
ahp=int(inp[2])
aat=int(inp[3])

for i in range(100):
  ahp-=tat
  if ahp<=0:
    print("Yes")
    sys.exit()
  thp-=aat
  if thp<=0:
    print("No")
    sys.exit()
n, m = map(int, input().split())
a = [input() for i in range(n)]
b = [input() for i in range(m)]


for i in range(n-m+1):
    for j in range(n-m)+1:
        flag = 0
        for k in range(m):
            for l in range(m):
                if a[i + k][j + l] != b[k][l]:
                    flag = 1
        if flag == 0:
            print('Yes')
            exit()


print('No')


### FIXED CODE ###

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


for i in range(n-m+1):
    for j in range(n-m+1):
        flag = 0
        for k in range(m):
            for l in range(m):
                if a[i + k][j + l] != b[k][l]:
                    flag = 1
        if flag == 0:
            print('Yes')
            exit()


print('No')
import sys
input = sys.stdin.readline
print(-1)import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
res = float("inf")
for i in range(pow(2, N)):
  x = []
  l = []
  c = 0
  for j in range(N):
    if i & (1 << j):
      c += 1
      x.append((b[j], j))
    else:
      x.append((a[j], j))
  if c % 2: continue
  y = sorted(x, key = lambda x: x[0])
  z = -1
  #print(y, i)
  for j in range(N):
    t = abs(j - y[j][1])
    #print(i & (1 << y[j][1]) > 0, t)
    if i & (1 << j) > 0:
      if t % 2:
        z = max(z, t)
      else:
        z = -1
        break
    else:
      if t % 2 == 0:
        z = max(z, t)
      else:
        z = -1
        break
  if z == -1: continue
  z = 0
  for j in range(N):
    for k in range(j, len(x)):
      if x[k][0] == y[j][0]:
        x.pop(k)
        x.insert(0, (0, 0))
        z += k - j
        break
  res = min(res, z)

  
if res != float("inf"): print(res)
else: print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
def check(i):
  x = []
  for j in range(N):
    if i & (1 << j):
      x.append(b[j])
    else:
      x.append(a[j])
  sx = sorted(x)
  odd = [0] * 51
  even = [0] * 51
  for j in range(N):
    odd[sx[j]] += j % 2
    even[sx[j]] += (j % 2 == 0)
  for j in range(N):
    if i & (1 << j):
      if j % 2: even[x[j]] -= 1
      else: odd[x[j]] -= 1
    else:
      if j % 2: odd[x[j]] -= 1
      else: even[x[j]] -= 1
  return min(min(odd), min(even)) >= 0
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
res = float("inf")
for i in range(pow(2, N)):
  if check(i) == False: continue
  fwk = BIT(N)
  t = 0
  odd = []
  even = []
  for j in range(N):
    if i & (1 << j):
      if j % 2: even.append((b[j], j))
      else: odd.append((b[j], j))
    else:
      if j % 2: odd.append((a[j], j))
      else: even.append((a[j], j))
  #print(t, i)
  odd.sort(key = lambda x: x[0])
  even.sort(key = lambda x: x[0])
  ind = []
  #print(t, i)
  for j in range(N):
    if j % 2: ind.append(odd[j // 2][1])
    else: ind.append(even[j // 2][1])
  #print(t, i, ind)
  for x in ind:
    t += fwk.get(x, N)
    fwk.add(x + 1, 1)
  res = min(res, t)
  #print(t, i)
if res == float("inf"): print(-1)
else: print(res)
N,C,K = map(int,input().split())
li = []
for t in range(N):
  li.append(int(input()))

count = 0
ans = 0

newLi = sorted(li)

while(len(newLi)):
  for c in range(C - 1):
    if len(newLi) < 2:
	  break
    
    if newLi[1] <= newLi[0] + K:
      newLi.pop(1)
    else:
      break

  newLi.pop(0)
  ans += 1

print(ans)

### FIXED CODE ###

N,C,K = map(int,input().split())
li = []
for t in range(N):
  li.append(int(input()))

count = 0
ans = 0

newLi = sorted(li)

while(len(newLi)):
  for c in range(C - 1):
    if len(newLi) < 2:
      break
    
    if newLi[1] <= newLi[0] + K:
      newLi.pop(1)
    else:
      break

  newLi.pop(0)
  ans += 1

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

print(a*b//2)

### FIXED CODE ###

a,b,c= map(int,input().split())
print(a*b//2)
#!/usr/bin/env python3
import sys
from collections import Counter
from scipy.special import comb

def solve(N: int, s: "List[str]"):
    print(sum([comb(v, 2, exact=True) for v in Counter(s).values()]))

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [ ' '.join(sorted(next(tokens))) for _ in range(N) ]  # type: "List[str]"
    solve(N, sorted(s))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter
from scipy.misc import comb

def solve(N: int, s: "List[str]"):
    print(sum([comb(v, 2, exact=True) for v in Counter(s).values()]))

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [ ' '.join(sorted(next(tokens))) for _ in range(N) ]  # type: "List[str]"
    solve(N, sorted(s))

if __name__ == '__main__':
    main()
A = [int(input()) for i in range(5)]
B = [A[i] % 10 for i in range(5)]
C = [10 - B[i] for i in range(5) if B[i] != 0]

ans = 0
for i in range(5):
    ans += A[i]
    if B[i]: ans += 10 - B[i]

print(ans - max(C))

### FIXED CODE ###

A = [int(input()) for i in range(5)]
B = [A[i] % 10 for i in range(5)]
C = [10 - B[i] for i in range(5) if B[i] != 0]
if C == []:
    C.append(0)

ans = 0
for i in range(5):
    ans += A[i]
    if B[i]: ans += 10 - B[i]

print(ans - max(C))
b = input()

if b == "A" :
    print("T")
elif b == "T" :
    print("A")
elif b == "C" :
    print("G")
else print("C")

### FIXED CODE ###

b = str(input())

if b == "A" :
    print("T")
elif b == "T" :
    print("A")
elif b == "C" :
    print("G")
else :
    print("C")
a = int(input())
b = int(input())

if 2*a-1 > 2*b-1:
    if (2*a-1) > a+b:
        print(2*a-1)
    else:
        print(a+b)
else:
    if 2*b-1 > a+b:
        print(2*b-1)
    else:
        print(a+b)


### FIXED CODE ###

n, m=[int(k) for k in input().split()]
cont=0
for i in range(2):
    if n>m: 
        cont+=n
        n-=1
    elif m>=n:
        cont+=m
        m-=1
print(cont)
N = int(input())
list_1 = []
for i in range(N):
    list_1.append(list(map(int, input().split())))

m = 0
for list_i in list_1:
    for list_j in list_1:
        if list_i != list_j:
            d = math.sqrt((list_j[0]-list_i[0])**2 + (list_j[1]-list_i[1])**2)
            m += d

average = m / N
print(average)

### FIXED CODE ###

import math

N = int(input())
list_1 = []
for i in range(N):
    list_1.append(list(map(int, input().split())))

m = 0
for list_i in list_1:
    for list_j in list_1:
        if list_i != list_j:
            d = math.sqrt((list_j[0]-list_i[0])**2 + (list_j[1]-list_i[1])**2)
            m += d

average = m / N
print(average)
import math

N = int(input())
hstr = input().split()
h = [int(n) for n in hstr]

dp = [math.inf for i in range(N)]

dp[0] = 0
dp[1] = abs(h[0] - h[1])

for i in range(2, N):
    dif1 = abs(h[i] - h[i-1])
    dif2 = abs(h[i] - h[i-2])
    dp[i] = min(dp[i-1] + dif1, dp[i-2] + dif2)

print(dp[N-1])



### FIXED CODE ###

N = int(input())
hstr = input().split()
h = [int(n) for n in hstr]

dp = [0 for i in range(N)]

dp[0] = 0
dp[1] = abs(h[0] - h[1])

for i in range(2, N):
    dif1 = abs(h[i] - h[i-1])
    dif2 = abs(h[i] - h[i-2])
    dp[i] = min(dp[i-1] + dif1, dp[i-2] + dif2)

print(dp[N-1])
s = input()
k = int(input())
i = 0
while s[i] == "1":
    i += 1
print(s[i])

### FIXED CODE ###

s = input()
k = int(input())
if k == 1: print(s[0])
else:
    for i in range(k):
        if s[i] != "1":
            print(s[i])
            break
        else:
            if i == k - 1:
                print(s[i])
                break
import math

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

cd_gcd = math.gcd(c, d)
cd_lcm = c * d // cd_gcd

ans = (b - a + 1) - (b - a -1)//c - (b - a -1)//d + (b - a -1)//cd_lcm
print(ans)

### FIXED CODE ###

# import math
from fractions import gcd

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

cd_lcm = c * d // gcd(c, d)

x1 = b//c - (a-1)//c
x2 = b//d - (a-1)//d
x3 = b//cd_lcm - (a-1)//cd_lcm

print((b-(a-1))-x1-x2+x3)
a, b, k = map(int, input())
st = set(range(a, min(b, a+k)+1)) + set(range(b, max(a, b-k)-1, -1))
for i in sorted(st):
    print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
st = list(range(a, min(b+1, a+k))) + list(range(b, max(a-1, b-k), -1))
for i in sorted(set(st)):
    print(i)
N, Q = map(int, input().split())
S = input()
cnt_array = [0] * (N+1)
ans = [0] * Q
for i in range(N):
    if S[i] == 'A' and S[i+1] == 'C':
        cnt_array[i+1] = 1 + cnt_array[i]
    else:
        cnt_array[i+1] = cnt_array[i]
for i in range(Q):
    l, r = map(int, input().split())
    ans[i] = cnt_array[r-1] - cnt_array[l-1]
# print(cnt_array)
# print(ans)
for i in ans:
    print(i)

### FIXED CODE ###

# import math
N, Q = map(int, input().split())
# line = list(map(int, input().split()))
# line = input()
S = input()
question = []
ac = [0] * N
ans = []
count = 0
for _ in range(Q):
    question.append(list(map(int, input().split())))

for i in range(N):
    if S[i] == 'C' and S[i-1] == 'A':
        count += 1
        ac[i] = count
    else:
        ac[i] = count

# print(ac)

for i in range(Q):
    start = question[i][0] - 1
    end = question[i][1] - 1
    tmp = ac[end] - ac[start]
    ans.append(tmp)

for i in range(len(ans)):
    print(ans[i])
import copy
s = list(input())
def check01_2(s, pos):
    p = 0
    if abs(len(s) - pos)  > 2:
        for i in range(pos, len(s), 1):
            if s[i] != s[i+1]:
                del s[i:i+2]
                if i !=0:
                    p = i-1
                return check01_2(s, p)
    return s

s2 = copy.deepcopy(s)
s2 = check01_2(s2, 0)
print(len(s) - len(s2))



### FIXED CODE ###

import numpy as np
s = list(input())

cnt = np.empty(2)
for i in range(len(s)):
    cnt[int(s[i]) - 0] += 1
ans = np.min(cnt) * 2
print(int(ans))
import math
from functools import reduce

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    n, m, *a_n = map(int, open(0).read().split())
    a_n_half = list(map(lambda x: x // 2, a_n))
    a_n_lcm = lcm(a_n_half)
    
    cnt = m // a_n_lcm
    
    if cnt % 2 == 0:
        print(cnt // 2)
    else:
        print(cnt // 2 + 1)
        
        
    
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

from fractions import gcd
from functools import reduce
import copy
import sys

N, M, *a_n = map(int, open(0).read().split())
a_n = list(set(a_n))
a_n = [a // 2 for a in a_n]
N = len(a_n)

def lcm_base(x, y):
    return (x * y) //  gcd(x, y)

def lcm_list(a_n):
    return reduce(lcm_base, a_n)

a_n_half = [0] * N
a_n_copy = copy.copy(a_n)
for i in range(N):
    while a_n_copy[i] % 2 == 0:
        a_n_copy[i] //= 2
        a_n_half[i] += 1
        
for i in range(N-1):
    if a_n_half[i] != a_n_half[i+1]:
        print(0)
        sys.exit()
        
print(-(-(M // lcm_list(a_n)) // 2))
n=int(input())
x=input()
chk0=chk1=chk2=0
b=x.count("1")
if b==1 and x=="1":
    print(0)
    exit()
elif b==1 and x[-1]=="1":
    for i in range(n-1):
        print(2)
    print(0)
    exit()
elif b==1:
    for i in range(n):
        if i=="0": print(1//0)
        else: print(0//0)
    exit()
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk1+=pow(2,i,b+1)
        if b>1: chk2+=pow(2,i,b-1)
        else: chk2=0
l=[]
for i,j in enumerate(x[::-1]):
    if b: a1=pow(2,i,b+1)
    else: a1=1
    if b>1: a2=pow(2,i,b-1)
    else: a2=1
    if j=="0":
        t=chk1+a1
    else:
        if b>1: t=chk2+b-1-a2
        else: t=0
    ans,f=0,1
    while t:
        if f:
            if j=="0": t%=(b+1)
            else: t%=(b-1)
            f=0
        else:
            t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l[::-1]:
    print(i)

### FIXED CODE ###

n=int(input())
x=input()
chk0=chk1=chk2=0
b=x.count("1")
if b==1 and x=="1":
    print(0)
    exit()
elif b==1:
    for i in range(n):
        if i==n-1: print(2)
        elif x[i]=="0": print(1)
        else: print(0)
    exit()
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk1+=pow(2,i,b+1)
        if b>1: chk2+=pow(2,i,b-1)
        else: chk2=0
l=[]
for i,j in enumerate(x[::-1]):
    if b: a1=pow(2,i,b+1)
    else: a1=1
    if b>1: a2=pow(2,i,b-1)
    else: a2=1
    if j=="0":
        t=chk1+a1
    else:
        if b>1: t=chk2+b-1-a2
        else: t=0
    ans,f=0,1
    while t:
        if f:
            if j=="0": t%=(b+1)
            else: t%=(b-1)
            f=0
        else:
            t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l[::-1]:
    print(i)
import math
a, b, c, d = map(int, input().split())

a_c = (a-1)//c
a_d = (a-1)//d
gcd_dc = math.gcd(d,c)
lcm_dc = (c*d)//gcd_dc
a_cd = (a-1)//lcm_dc
b_c = b//c
b_d = b//d
b_cd = b//lcm_dc

print(b-a+1-(b_c+b_d-b_cd-a_c-a_d+a_cd))


### FIXED CODE ###

from fractions import gcd
a, b, c, d = map(int, input().split())

a_c = (a-1)//c
a_d = (a-1)//d
gcd_dc = gcd(d,c)
lcm_dc = (c*d)//gcd_dc
a_cd = (a-1)//lcm_dc
b_c = b//c
b_d = b//d
b_cd = b//lcm_dc

print(b-a+1-(b_c+b_d-b_cd-a_c-a_d+a_cd))