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

from collections import deque
X, Y = map(int,input().split())
ans = 0
start = [0, 0]
move = [[1, 2], [2, 1]]
queue = deque()
queue.append(start)
while queue:
  x, y = queue.popleft()
  for i in range(len(move)):
    nextX = x + move[i][0]
    nextY = y + move[i][1]
    #print(i,nextX, nextY)
    if nextX == X and nextY == Y:
      ans += 1
    if nextX < X and nextY < Y:
      queue.append([nextX, nextY])
print(ans%(10**9+7))

### FIXED CODE ###

X, Y = map(int,input().split())
n = int((2*Y-X)/3)
m = int((2*X-Y)/3)
if (X+Y)%3!=0:
  print(0)
  exit()
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = 10 ** 9 + 7
N = 10 ** 6  
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
print(cmb(n+m, n, p))
### BUGGY CODE ###

import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

k = int(input())
tmp = 0
for a in range(1, k+1):
  for b in range(a, k+1):
    for c in range(b, k+1):
      #print('a='+str(a)+', b='+str(b)+', c='+str(c))
      if a == b and a == c:
        tmp += gcd_list([a, b, c]) 
      elif a == b and a != c:
        tmp += gcd_list([a, b, c]) 
        tmp += gcd_list([b, c, a]) 
        tmp += gcd_list([c, a, b]) 
      elif b == c and a != c:
        tmp += gcd_list([a, b, c]) 
        tmp += gcd_list([b, c, a]) 
        tmp += gcd_list([c, a, b]) 
      elif a == c and b != c:
        tmp += gcd_list([a, b, c]) 
        tmp += gcd_list([b, c, a]) 
        tmp += gcd_list([c, a, b]) 
      else:
        tmp += gcd_list([a, b, c])
        tmp += gcd_list([a, c, b])
        tmp += gcd_list([b, a, c])
        tmp += gcd_list([b, c, a])
        tmp += gcd_list([c, a, b])
        tmp += gcd_list([c, b, a])
print(tmp)


### FIXED CODE ###

import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

k = int(input())
tmp = 0
for a in range(1, k+1):
  for b in range(a, k+1):
    for c in range(b, k+1):
      #print('a='+str(a)+', b='+str(b)+', c='+str(c))
      if a == b and a == c:
        tmp += gcd_list([a, b, c]) 
      elif a == b and a != c:
        tmp += gcd_list([a, b, c]) * 3
#        tmp += gcd_list([b, c, a]) 
#        tmp += gcd_list([c, a, b]) 
      elif b == c and a != c:
        tmp += gcd_list([a, b, c]) * 3
#        tmp += gcd_list([b, c, a]) 
#        tmp += gcd_list([c, a, b]) 
      elif a == c and b != c:
        tmp += gcd_list([a, b, c]) * 3
#        tmp += gcd_list([b, c, a]) 
#        tmp += gcd_list([c, a, b]) 
      else:
        tmp += gcd_list([a, b, c]) * 6
#        tmp += gcd_list([a, c, b])
#        tmp += gcd_list([b, a, c])
#        tmp += gcd_list([b, c, a])
#        tmp += gcd_list([c, a, b])
#        tmp += gcd_list([c, b, a])
print(tmp)
### BUGGY CODE ###

import fractions

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

X=[A[0]]
for i in range(1, N-1):
  X.append(fractions.gcd(X[-1], A[i]))

Y=[A[-1]]
for i in range(N-2, 0, -1):
  Y=[fractions.gcd(Y[0], A[i])]+Y
  
X=[Y[0]]+X
Y=Y+[X[-1]]

X=tuple(X)
Y=tuple(Y)

Z=[fractions.gcd(X[i], Y[i]) for i in range(N)]
    
print(max(Z))

### FIXED CODE ###

import fractions

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

X=[0]*N
X[1]=A[0]
for i in range(2, N):
  X[i]=fractions.gcd(X[i-1], A[i-1])

Y=[0]*N
Y[-2]=A[-1]
for i in range(N-3, -1, -1):
  Y[i]=fractions.gcd(Y[i+1], A[i+1])
  
X[0]=Y[0]
Y[-1]=X[-1]

Z=[fractions.gcd(X[i], Y[i]) for i in range(N)]
    
print(max(Z))
### BUGGY CODE ###

from collections import deque
N, M = [int(x) for x in input().split()]
INF = 10**9
dist = [INF] * N
ans = [-1] * N
to = [set() for _ in range(N)]
for _ in range(M):
    A, B = [int(x)-1 for x in input().split()]
    to[A].add(B)
    to[B].add(A)
bfs = deque([(0, 0, -1)])
while len(bfs):
    cur, d, p = bfs.popleft()
    if d < dist[cur]:
        dist[cur] = d
        ans[cur] = p
    for v in to[cur]:
        if d+1 < dist[v]:
            bfs.append((v, d+1, cur))
    d += 1
print('Yes')
for a in ans[1:]:
    print(a+1)


### FIXED CODE ###

from collections import deque
N, M = [int(x) for x in input().split()]
INF = 10**6
dist = [INF] * N
ans = [-1] * N
to = [set() for _ in range(N)]
for _ in range(M):
    A, B = [int(x)-1 for x in input().split()]
    to[A].add(B)
    to[B].add(A)
bfs = deque([(0, 0, -1)])
while len(bfs):
    cur, d, p = bfs.popleft()
    if d >= dist[cur]: continue
    dist[cur] = d
    ans[cur] = p
    for v in to[cur]:
        if d+1 < dist[v]:
            bfs.append((v, d+1, cur))
print('Yes')
for a in ans[1:]:
    print(a+1)
### BUGGY CODE ###

N = int(input())
P =1
for i in range(1,N+1):
    P*=i

print(P%1000000007)


### FIXED CODE ###

N = int(input())
M = 1000000007
n=[1]*(N+1)
for i in range(1,N+1):
    n[i] = (n[i-1]*i)%M

print(n[N])
### BUGGY CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n=int(readline())
    ans=0
    for i in range(1,n):
        ans+=i
    print(ans)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

### FIXED CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n=int(readline())

    ans=(n * (n-1)) // 2
    
    print(ans)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------
### BUGGY CODE ###

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


def main():
    k = int(input())+1
    s = 0
    for a in range(1, k):
        for b in range(1, k):
            for c in range(1, k):
                s += gcd(a, b, c)
    print(s)


main()


### FIXED CODE ###

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


def main():
    k = int(input())+1
    s = 0
    for a in range(1, k):
        for b in range(1, k):
            for c in range(1, k):
                s += gcd(a, b, c)
    print(s)


main()
### BUGGY CODE ###

#shellSort(A, n)
n=int(input())
A=[int(input()) for i in range(n)]
cnt = 0
G=[1]
S=str(G[0])
while G[0]<n//5:
    G.insert(0,G[0]*3+1)
  #  print (i)
    S=str(G[0])+" "+S
m=len(G)
print (m)
print(S)
for i in range(m):
    g=G[i]
    for j in range(g,n):
        v = A[j]
        k = j - g
        while k >= 0 and A[k] > v:
              A[k+g] = A[k]
              k = k - g
              cnt+=1
        A[k+g] = v 
print(cnt)
for i in range(n):
    print(A[i])

### FIXED CODE ###

#shellSort(A, n)
n=int(input())
A=[int(input()) for i in range(n)]
cnt = 0
G=[1]
S=str(G[0])
#if 5<n<13:
t=n//5
#elif n<3000:
  #  t=n//9
#else:
  #  t=n//17
#Gt=[4, 9, 20, 46, 103, 233, 525, 1182,2660, 5985, 13467]
f=1.0
while f<t:
    f*=2.2
    f=int(f)
    G.insert(0,f)
  #  print (i)
    S=str(G[0])+" "+S
m=len(G)
print (m)
print(S)
for i in range(m):
    g=G[i]
    for j in range(g,n):
        v = A[j]
        k = j - g
        while k >= 0 and A[k] > v:
              A[k+g] = A[k]
              k = k - g
              cnt+=1
        A[k+g] = v 
print(cnt)
for i in range(n):
    print(A[i])
### BUGGY CODE ###

N = int(input())

ans1 = 0

A = '1'
B = str(N)

if len(A)>=len(B):
    ans = len(A)
else:
    ans = len(B)
    
for i in range(2,N+1):
    A = i
    if N%A==0:
        B = int(N / A)
        A = str(A)
        B = str(B)
        #print(A, B)
        if len(A)>=len(B):
            ans1 = len(A)
        else:
            ans1 = len(B)
        if ans1 <= ans:
            ans = ans1
    if len(str(A))==len(str(B)):
        break
print(ans)


### FIXED CODE ###

import math

N = int(input())

ans1 = 0

A = '1'
B = str(N)

if len(A)>=len(B):
    ans = len(A)
else:
    ans = len(B)
    
for i in range(2,int(math.sqrt(N))+1):
    A = i
    if N%A==0:
        B = int(N / A)
        A = str(A)
        B = str(B)
        if len(A)>=len(B):
            ans1 = len(A)
        else:
            ans1 = len(B)
        if ans1 <= ans:
            ans = ans1
    if len(str(A))==len(str(B)):
        break
print(ans)
### BUGGY CODE ###

n = int(input())
a = 1
L=list(map(int,input().split()))
for i in range(0,n):
    a*=L[i]
    if(a>10**18):
        a=-1
if(a<0):
    a=-1
print(a)

### FIXED CODE ###

import sys
N=int(input())
L=list(map(int,input().split()))
a=1
if 0 in L:
  print(0)
  sys.exit()
for i in range(N):
  a=a*L[i]
  if a>10**18:
    print(-1)
    sys.exit()
print(a)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

p = []
for ai in a:
    for bi in b:
        p.append(ai + bi)
p.sort(reverse=True)
q = []
for pi in p[:k]:
    for ci in c:
        q.append(pi + ci)
q.sort(reverse=True)
for qi in q[:k]:
    print(qi)


### FIXED CODE ###

x, y, z, kk = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

p = []
for i in range(x):
    for j in range(y):
        for k in range(z):
            if (i + 1) * (j + 1) * (k + 1) <= kk:
                p.append(a[i] + b[j] + c[k])
            else:
                break
p.sort(reverse=True)
for i in range(kk):
    print(p[i])
### BUGGY CODE ###

K,S=input().split()
K,S=[int(K),int(S)]
a=[]
for X in range(K+1):
    for Y in range(K+1):
        Z=S-X-Y
        if 0<=Z<=K and X+Y+Z==S:
            a.append(S)
print(len(a))

### FIXED CODE ###

K,S=input().split()
K,S=[int(K),int(S)]
a=0
for X in range(K+1):
    for Y in range(K+1):
        Z=S-X-Y
        if 0<=Z<=K:
           a+=1 
print(a)
### BUGGY CODE ###

import numpy as np
import re

def main():
    S = input()
    N = len(S) + 1

    ans = 0
    s_list = re.split("><", S)
    nelem = len(s_list)
    for i in range(nelem):
        elem = s_list[i]
        ln = elem.count(">") + 1
        rn = elem.count("<") + 1
        if i == 0:
            rn -= 1
        if i == nelem - 1:
            ln -= 1
        nmax = np.max([ln, rn])
        nmin = np.min([ln, rn])
        ans += np.sum(np.arange(start=0, stop=nmax+1, step=1))
        ans += np.sum(np.arange(start=0, stop=nmin, step=1))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import re
 
def main():
    S = input()
    N = len(S) + 1
 
    ans = 0
    s_list = re.split("><", S)
    nelem = len(s_list)
    for i in range(nelem):
        elem = s_list[i]
        ln = elem.count(">") + 1
        rn = elem.count("<") + 1
        if i == 0:
            rn -= 1
        if i == nelem - 1:
            ln -= 1
        nmax = max([ln, rn])
        nmin = min([ln, rn])
        ans += (0 + nmax) * (nmax + 1) / 2
        ans += (0 + nmin - 1) * (nmin) / 2
    print(int(ans))
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

if N == 1:
    print(P)
else:
    ans = 1
    for x in range(1, int(P**(1/N))+10):
        if P % pow(x,N) == 0:
            ans = max(ans, x)
    print(ans)

### FIXED CODE ###

from collections import Counter

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

# n以下の全ての素数のセットを返す関数
def prime_set(n):
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5) + 1):
        primes.difference_update(range(i*2, n+1, i))
    return primes

# nを素因数分解して素因数の全リストを返す関数
def prime_factors(n):
    f = []
    for i in prime_set(int(n**0.5) + 1):
        while n % i == 0:
            f.append(i)
            n //= i
    if n > 1:
        f.append(n)
    return f

c = Counter(prime_factors(P))
ans = 1

for x in c.keys():
    ans *= pow(x, int(c[x]//N))

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

import sys

readline = sys.stdin.buffer.readline


def main():
    N, K = map(int, readline().split())
    H = list(map(int, readline().split()))
    for i in range(K):
        H.append(10**10)

    dp = [10**10] * (N+K)
    dp[0] = 0

    for i in range(N):
        for k in range(1, K+1):
            dp[i+k] = min(dp[i+k], dp[i] + abs(H[i+k]-H[i]))

    print(dp[N-1])


main()


### FIXED CODE ###

import sys

readline = sys.stdin.buffer.readline


def main():
    N, K = map(int, readline().split())
    H = list(map(int, readline().split()))
    for i in range(K):
        H.append(10**10)

    dp = [10**10] * (N+K)
    dp[0] = 0

    for i in range(N):
        for k in range(1, K+1):
            dp[i+k] = min(dp[i+k], dp[i] + abs(H[i+k]-H[i]))

    print(dp[N-1])


main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
R,C,K = map(int,input().split())
lis = [[0] * (C+1) for i in range(R+1)]
for _ in range(K):
    r,c,v = map(int,input().split())
    lis[r][c] = v

dp = [[[0] * 4 for _ in range(C+1)] for _ in range(R+1)]
#print(dp)
for i in range(1,R+1):
    for j in range(1,C+1):
        for k in range(4):
            dp[i][j][0] = max(dp[i][j][0],dp[i-1][j][k])
            dp[i][j][1] = max(dp[i][j][1],dp[i-1][j][k] + lis[i][j])

            dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
            if k > 0:
                dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1] + lis[i][j])
# print(dp[0])
# print(dp[1])
# print(dp[2])
# print(dp[3])
print(max(dp[R][C][0],dp[R][C][1],dp[R][C][2],dp[R][C][3]))


### FIXED CODE ###

import sys
input = sys.stdin.readline
R,C,K = map(int,input().split())
lis = [[0] * (C+1) for i in range(R+1)]
for _ in range(K):
    r,c,v = map(int,input().split())
    lis[r][c] = v

dp = [[[0] * (C+1) for _ in range(R+1)] for _ in range(4)]
#print(dp)
for i in range(1,R+1):
    for j in range(1,C+1):
        for k in range(4):
            dp[0][i][j] = max(dp[0][i][j],dp[k][i-1][j])
            dp[1][i][j] = max(dp[1][i][j],dp[k][i-1][j] + lis[i][j])

            dp[k][i][j] = max(dp[k][i][j],dp[k][i][j-1])
            if k > 0:
                dp[k][i][j] = max(dp[k][i][j],dp[k-1][i][j-1] + lis[i][j])
# print(dp[0])
# print(dp[1])
# print(dp[2])
# print(dp[3])
print(max(dp[0][R][C],dp[1][R][C],dp[2][R][C],dp[3][R][C]))
### BUGGY CODE ###

#!/usr/bin/env python
from collections import Counter
import sys
from functools import lru_cache

input = sys.stdin.readline

@lru_cache(maxsize=None)
def main():
    n = int(input().rstrip())
    l = list(input().rstrip().split())

    c = Counter(l)
    for item in l:
        ans = 0
        for key in c:
            tmp = c[key]
            if key == item:
                tmp -= 1
            ans += tmp * (tmp - 1) // 2
        print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python
from collections import Counter
import sys

input = sys.stdin.readline

def main():
    n = int(input().rstrip())
    l = list(input().rstrip().split())

    c = Counter(l)
    total = 0
    for key in c:
        total += c[key] * (c[key] -1) // 2
    for item in l:
        print(total - (c[item] -1))
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
S = []
C = []
for i in range(N):
  s = input()
  if s in S:
    n = S.index(s)
    C[n] += 1
    if C[n] > N // 2:
      print(S[n])
      exit()
  else:
    S.append(s)
    C.append(1)
M = max(C)
l = len(C)
A = [S[j] for j in range(l) if C[j] == M]
A.sort()
[print(k) for k in A]

### FIXED CODE ###

import collections
N = int(input())
l = [input() for i in range(N)]
L = collections.Counter(l)
a = L.most_common()
M = a[0][1]
A = [j[0] for j in a if j[1] == M]
[print(k) for k in sorted(A)]
### BUGGY CODE ###

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
grid = [list(map(int, input().split())) for _ in range(N)]
grid1 = []
grid2 = []
grid3 = []
ans = float('inf')
for i in range(N):
    for k in range(N):
        tmp = grid[i][k]
        tmp2 = i + k
        if tmp2 % 3 == 1:
            grid1.append(tmp)
        elif tmp2 % 3 == 2:
            grid2.append(tmp)
        else:
            grid3.append(tmp)
sum1 = sum(grid1)
sum2 = sum(grid2)
sum3 = sum(grid3)
tmp1 = [sum1]*C
tmp2 = [sum2]*C
tmp3 = [sum3]*C
for i in range(C):
    for k in grid1:
        tmp1[i] = tmp1[i] - k + D[k-1][i]
for i in range(C):
    for k in grid2:
        tmp2[i] = tmp2[i] - k + D[k-1][i]
for i in range(C):
    for k in grid3:
        tmp3[i] = tmp3[i] - k + D[k-1][i]
for i in range(C):
    for k in range(C):
        if i == k:
            continue
        for l in range(C):
            if i == l or k == l:
                continue
            ans = min(ans,tmp1[i]+tmp2[k]+tmp3[l])
print(ans)

### FIXED CODE ###

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
grid = [list(map(int, input().split())) for _ in range(N)]
grid1 = []
grid2 = []
grid3 = []
ans = float('inf')
for i in range(N):
    for k in range(N):
        tmp = grid[i][k]
        tmp2 = i + k
        if tmp2 % 3 == 1:
            grid1.append(tmp)
        elif tmp2 % 3 == 2:
            grid2.append(tmp)
        else:
            grid3.append(tmp)
sum1 = sum(grid1)
sum2 = sum(grid2)
sum3 = sum(grid3)
tmp1 = [sum1]*C
tmp2 = [sum2]*C
tmp3 = [sum3]*C
for i in range(C):
    for k in grid1:
        tmp1[i] = tmp1[i] - k + D[k-1][i]
for i in range(C):
    for k in grid2:
        tmp2[i] = tmp2[i] - k + D[k-1][i]
for i in range(C):
    for k in grid3:
        tmp3[i] = tmp3[i] - k + D[k-1][i]
for i in range(C):
    for k in range(C):
        if i == k:
            continue
        for l in range(C):
            if i == l or k == l:
                continue
            ans = min(ans,tmp1[i]+tmp2[k]+tmp3[l])
print(ans)
### BUGGY CODE ###

x = int(input())
val = []
prime = []
for i in range(2,100000):
    val.append(i)
while len(val) != 0:
    prime.append(val[0])
    val = [i for i in val if i % val[0] != 0]
#print(prime)
#print(val)

ans = 2
for i in prime:
    if i >= x:
        ans = i
print(ans)

### FIXED CODE ###

x = int(input())
val = 0
ans = 0
for i in range(x, int(1e20)):
    if i % 2 == 0 and i !=2:
        continue
    for j in range(2,i+1):
        if i == j:
            val = 1         
        
        
        if i % j == 0:
            break

          
    if val == 1:
        ans = i
        break
    
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(X: int, Y: int, Z: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    # A.sort(reverse=True)
    # B.sort(reverse=True)
    AB = []
    for a in A:
        for b in B:
            AB.append(a+b)
    AB.sort(reverse=True)
    C.sort(reverse=True)
    AB = AB[:K]
    C = C[:K]
    ABC = []
    for ab in AB:
        for c in C:
            ABC.append(ab+c)
    ABC.sort(reverse=True)
    for i in range(K):
        print(ABC[i])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    Z = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(X)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(Y)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(Z)]  # type: "List[int]"
    solve(X, Y, Z, K, A, B, C)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(X: int, Y: int, Z: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    AB = []
    for a in A:
        for b in B:
            AB.append(a+b)
    AB.sort(reverse=True)
    C.sort(reverse=True)
    AB = AB[:K]
    C = C[:K]
    ABC = []
    for ab in AB:
        for c in C:
            ABC.append(ab+c)
    ABC.sort(reverse=True)
    for i in range(K):
        print(ABC[i])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    Z = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(X)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(Y)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(Z)]  # type: "List[int]"
    solve(X, Y, Z, K, A, B, C)

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

N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))


### FIXED CODE ###

N = int(input())
X_bin = input()
#N = 10**5
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_cnt == 0:
        return 0
    if next_int == 0:
        return 1
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
f_p = X_int % (X_cnt+1)
if X_cnt-1 == 0:
    f_m = 0
else:
    f_m = X_int % (X_cnt-1)
for i in range(N):
    if X_bin[i] == '1':
        next_cnt = X_cnt - 1
        if next_cnt == 0:
            next_int = 0
        else:
            next_int = f_m - pow(2, (N-i-1), next_cnt)  # マイナスでも正しく求まる？
    else:
        next_cnt = X_cnt + 1
        next_int = f_p + pow(2, (N-i-1), next_cnt)
    print(calc_ans(next_int, next_cnt))
    #calc_ans(next_cnt, next_cnt)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7

import fractions
from functools import reduce

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
    
l = 1
B = 0

for i in range(N):
  l = lcm(l,A[i])
for i in range(N):
  B += l//A[i]%mod
B %= mod

print(B)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7

import fractions
from functools import reduce

def gcd(x,y):
  if x == 0:
    return y
  else:
    return gcd(y-x*(y//x),x)
 

def lcm(x, y):
    return (x*y)//gcd(x,y)
    
l = 1
B = 0

for i in range(N):
  l = lcm(l,A[i])
for i in range(N):
  B += l//A[i]
B %= mod

print(B)
### BUGGY CODE ###

from itertools import combinations

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

lst = {i for i in range(0, n+1)}
re = 0
for i in range(k, n+2):
    temp = set(combinations(lst, i))
    tt = {sum(j) for j in temp}
    re += len(tt)

print(re)

### FIXED CODE ###

import sys
n, k = map(int, sys.stdin.readline().split())
ans = 0
mod = 10**9+7
for i in range(k, n+2):
    ans += (n-i+1)*i + 1
ans %= mod
print(ans)