Harryxun/stf_run huggingface dataset:
n=int(input())
x=input()
p=0
chk0=chk1=chk2=0
b=x.count("1")
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk0+=pow(2,i)
        chk1+=pow(2,i,b+1)
        chk2+=pow(2,i,b-1)
#print(chk0,chk1,chk2)
#print(bin(chk0+1),bin(chk1),bin(chk2))
#print(bin(chk0+1).count("1"),bin(chk1).count("1"),bin(chk2).count("1"))
print((chk1+1)%(b+1))
#print(chk0+1,bin(chk0+1).count("1"))
#print((chk0+1)%bin(chk0+1).count("1"))
#exit()
l=[]
#chk1=chk1+b+1
#chk2=chk2+b-1
for i,j in enumerate(x[::-1]):
    a1=pow(2,i,b+1)
    a2=pow(2,i,b-1)
    if j=="0":
        t=chk1+a1
    else:
        t=chk2+b-1-a2
    ans=0
    f=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)
A, B = mao(int, input().split())
K = A + B
if K % 2 == 0:
  print(K / 2)
else:
  print("IMPOSSIBLE")

### FIXED CODE ###

A, B = map(int, input().split())
K = A + B
if K % 2 == 0:
  print(K // 2)
else:
  print("IMPOSSIBLE")
inputA= int(input())
inputB =map(str,input())

print(inputB.count('ABC'))

### FIXED CODE ###


inputA,inputB,inputC = map(int, input().split())

if inputC >= inputA:
    if inputB > inputC-inputA:
        print(0,inputB -(inputC-inputA))
    else:
        print(0,0)
else:
    print(inputA-inputC,inputB)
import sys
sys.setrecursionlimit(1000000000000)

def dfs(i):
	if i in use:
		return 
	use.add(i)
	for e in edges_r[i]:
		dfs(e)

def bf():
	d = [float('inf') for _ in range(n + 1)]
	d[1] = 0
	for _ in range(n):
		f = False
		for e in edges_f:
			if d[e[1]] > d[e[0]] + e[2]:
				d[e[1]] = d[e[0]] + e[2]
				f = True	
		if not f:
			return max(0, -1 * d[n])
	return -1

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

edges_f = []
edges_r = [[] for i in range(n + 1)]
for _ in range(m):
	a, b, c = list(map(int, input().split()))
	edges_f.append([a, b, -1 * (c - p)])
	edges_r[b].append(a)

use = set()
dfs(n)

edges_f = [e for e in edges_f if e[0] in use and e[1] in use]
print(bf())

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)

def dfs(i):
	if i in use:
		return 
	use.add(i)
	for e in edges_r[i]:
		dfs(e)

def bf():
	d = [float('inf') for _ in range(n + 1)]
	d[1] = 0
	for _ in range(n):
		f = False
		for e in edges_f:
			if d[e[1]] > d[e[0]] + e[2]:
				d[e[1]] = d[e[0]] + e[2]
				f = True	
		if not f:
			return max(0, -1 * d[n])
	return -1

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

edges_f = []
edges_r = [[] for i in range(n + 1)]
for _ in range(m):
	a, b, c = list(map(int, input().split()))
	edges_f.append([a, b, -1 * (c - p)])
	edges_r[b].append(a)

use = set()
dfs(n)

edges_f = [e for e in edges_f if e[0] in use and e[1] in use]
print(bf())
int N = int(input())
int a = int(input())
int b = int(input())
print(N==1 ? "hello World" : a+b)

### FIXED CODE ###

N = int(input())
if N == 1:
    print("Hello World")
else:
    a = int(input())
    b = int(input())
    print(a+b)
import numpy as np
R=int(input())
circle=float(R*2*np.pi))
print(circle)

### FIXED CODE ###

import numpy as np
R=int(input())
circle=float(R*2*np.pi)
print(circle)
n,m = map(int,input().split())

a = []
for i in range(m):
    a.append(int(input()))

d = [a[0]-1]
for j in range(1,m):
    d.append(a[j]-a[j-1]-2)

d.append(n-a[m-1]-1)


fiblist = [0] * 100000
fiblist[0] = 1
fiblist[1] = 1

for p in range(2,100000):
    fiblist[p] = (fiblist[p-1]+fiblist[p-2]) % 1000000007

#print(d)

if (-1 in d) or (-2 in d):
    print(0)
else:
    ans = 1
    for k in range(m+1):
        ans = (ans * fiblist[d[k]]) % 1000000007

    print(ans)

   

### FIXED CODE ###

fiblist = [0] * 100001
fiblist[0] = 1
fiblist[1] = 1
for p in range(2,100001):
    fiblist[p] = (fiblist[p-1]+fiblist[p-2]) % 1000000007

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

if m == 0:
    print(fiblist[n])
else:
    a = []
    for i in range(m):
        a.append(int(input()))

    d = [a[0]-1]
    for j in range(1,m):
        d.append(a[j]-a[j-1]-2)

    d.append(n-a[m-1]-1)




#print(d)

    if (-1 in d) or (-2 in d):
        print(0)
    else:
        ans = 1
        for k in range(m+1):
            ans = (ans * fiblist[d[k]]) % 1000000007

        print(ans)
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    t1, t2 = LI()
    a1, a2 = LI()
    b1, b2 = LI()

    if a1 < b1:
        tmp = b1
        b1 = a1
        a1 = tmp

        tmp = b2
        b2 = a2
        a2 = tmp

    l1 = (a1 - b1) * t1
    l2 = (a2 - b2) * t2
    l3 = l1 + l2

    if l3 == 0:
        print("infinity")
        return
    if l3 > 0:
        print(0)
        return
    ans = 1
    if l1 % (-l3) == 0:
        print(ans + 2 * (l1 // (-l3)) - 1)
        return
    print(ans + 2 * (l1 // (-l3)))






if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n = II()
    a_s = LI()
    d = [0, 0, 0]
    ans = 1
    for i in a_s:
        flag = True
        tmp = 0
        for index, j in enumerate(d):
            # print(i, j)
            if j == i:
                tmp += 1
                if flag:
                    d[index] += 1
                    flag = False
        ans = ans * tmp % MOD
        # print(d, tmp, i, ans)
    print(ans)





if __name__ == '__main__':
    main()
from collections import deque
import sys
input = sys.stdin.readline
h,w=map(int, input().split(' '))
a = [list(input()) for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            a[i][j] = 0
            q.append([i,j,0])
        else:
            a[i][j] = -1
while q:
    [s,t,cnt] = q.popleft()
    if s>0 and a[s-1][t] == -1:
        q.append([s-1,t,cnt+1])
        a[s-1][t] = cnt+1
    if s<h-1 and a[s+1][t] == -1:
        q.append([s+1,t,cnt+1])
        a[s+1][t] = cnt+1
    if t>0 and a[s][t-1] == -1:
        q.append([s,t-1,cnt+1])
        a[s][t-1] = cnt+1
    if t<w-1 and a[s][t+1] == -1:
        q.append([s,t+1,cnt+1])
        a[s][t+1] = cnt+1
ans = 0
for i in range(h):
    ans = max(ans,max(a[i]))
print(ans)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h,w=map(int, input().split(' '))
a = [input() for i in range(h)]
nl = [[] for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            nl[i].append(0)
            q.append([i,j,0])
        else:
            nl[i].append(-1)
while q:
    [s,t,cnt] = q.popleft()
    if s>0 and nl[s-1][t] == -1:
        q.append([s-1,t,cnt+1])
        nl[s-1][t] = cnt+1
    if s<h-1 and nl[s+1][t] == -1:
        q.append([s+1,t,cnt+1])
        nl[s+1][t] = cnt+1
    if t>0 and nl[s][t-1] == -1:
        q.append([s,t-1,cnt+1])
        nl[s][t-1] = cnt+1
    if t<w-1 and nl[s][t+1] == -1:
        q.append([s,t+1,cnt+1])
        nl[s][t+1] = cnt+1
ans = 0
for i in range(h):
    ans = max(ans,max(nl[i]))
print(ans)
num1=input()
num1=(int)num1
num2=input()
num2=(int)num2
print(num1*num2)

### FIXED CODE ###

a,b=input().split()
print(int(a)*int(b))
N, K = map(int, input().split())
mod = 10 ** 9 + 7

s = 0
tmp = 1
for _ in range(N):
    tmp *= K
    tmp %= mod
s = tmp
for i in range(K+1):
    baisuu = K % i
    tmp = 1
    for _ in range(N):
        tmp *= baisuu
        tmp %= mod
    s += tmp * (i - 1)

print(s)

### FIXED CODE ###

from functools import lru_cache


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

@lru_cache
def gcd1_tuples(k):
    if k == 1:
        return 1
    tmp = pow(k, N, mod)
    for j in range(2, k+1):
        tmp -= gcd1_tuples(k//j)
        tmp %= mod
    return tmp

s = 0
for i in range(1, K+1):
    s += gcd1_tuples(K//i) * i
    s %= mod

print(s)
import bisect

a,b,n=map(int,input().split())
l1=[int(input()) for i in range(a)]
l2=[int(input()) for i in range(b)]
x=[int(input()) for i in range(n)]
l1.sort()
l2.sort()
for i in range(n):
    idx1=bisect.bisect_left(l1,x[i])
    if idx1<a:
        p=abs(l1[idx1-1]-x[i])
        q=abs(l1[idx1]-x[i])
        if p>q:
            po=l1[idx1]
            dis1=q
        else:
            po=l1[idx1-1]
            dis1=p
    else:
        dis1=x[i]-l1[-1]
        po=l1[-1]
    idx3=bisect.bisect_left(l2,po)
    if idx3<b:
        dis=min(abs(l2[idx3-1]-po),abs(l2[idx3]-po))
    else:
        dis=po-l2[-1]
    dis1+=dis
    idx2=bisect.bisect_left(l2,x[i])
    if idx2<b:
        p=abs(l2[idx2-1]-x[i])
        q=abs(l2[idx2]-x[i])
        if p>q:
            po=l2[idx2]
            dis2=q
        else:
            po=l2[idx-1]
            dis2=p
    else:
        dis2=x[i]-l2[-1]
        po=l2[-1]
    idx3=bisect.bisect_left(l1,po)
    if idx3<a:
        dis=min(abs(l1[idx3-1]-po),abs(l1[idx3]-po))
    else:
        dis=po-l1[-1]
    dis2+=dis
    print(min(dis1,dis2))

### FIXED CODE ###

import bisect

a,b,n=map(int,input().split())
l1=[int(input()) for i in range(a)]
l2=[int(input()) for i in range(b)]
x=[int(input()) for i in range(n)]
l1.sort()
l2.sort()
for i in range(n):
    idx1=bisect.bisect_left(l1,x[i])
    if idx1<a:
        p=abs(l1[idx1-1]-x[i])
        q=abs(l1[idx1]-x[i])
        for j in range(2):
            if j==0:
                po=l1[idx1-1]
                idx3=bisect.bisect_left(l2,po)
                if idx3<b:
                    dis=min(abs(l2[idx3-1]-po),abs(l2[idx3]-po))
                else:
                    dis=po-l2[-1]
                dis1=p+dis
            else:
                po=l1[idx1]
                idx3=bisect.bisect_left(l2,po)
                if idx3<b:
                    dis=min(abs(l2[idx3-1]-po),abs(l2[idx3]-po))
                else:
                    dis=po-l2[-1]
                dis1=min(dis1,q+dis)
    else:
        p=x[i]-l1[-1]
        po=l1[-1]
        idx3=bisect.bisect_left(l2,po)
        if idx3<b:
            dis=min(abs(l2[idx3-1]-po),abs(l2[idx3]-po))
            dis1=dis+p
        else:
            dis1=po-l2[-1]+p
    idx2=bisect.bisect_left(l2,x[i])
    if idx2<b:
        p=abs(l2[idx2-1]-x[i])
        q=abs(l2[idx2]-x[i])
        for j in range(2):
            if j==0:
                po=l2[idx2-1]
                idx3=bisect.bisect_left(l1,po)
                if idx3<a:
                    dis=min(abs(l1[idx3-1]-po),abs(l1[idx3]-po))
                else:
                    dis=po-l1[-1]
                dis2=p+dis
            else:
                po=l2[idx2]
                idx3=bisect.bisect_left(l1,po)
                if idx3<a:
                    dis=min(abs(l1[idx3-1]-po),abs(l1[idx3]-po))
                else:
                    dis=po-l1[-1]
                dis2=min(dis2,q+dis)
    else:
        p=x[i]-l2[-1]
        po=l2[-1]
        idx3=bisect.bisect_left(l1,po)
        if idx3<a:
            dis=min(abs(l1[idx3-1]-po),abs(l1[idx3]-po))
            dis2=dis+p
        else:
            dis2=po-l1[-1]+p
    print(min(dis1,dis2))
from math import factorial

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

x = 1000000007

num = factorial(N - K + 1) * factorial(K - 1)

for i in range(1, K + 1):
    if N - K < i - 1:
        print(0)

    denom = factorial(i) * factorial(N - K + 1 - i) * factorial(i - 1) * factorial(K - i)
    v = num // denom

    print(v % x)


### FIXED CODE ###

from math import factorial

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

x = 1000000007

num = factorial(N - K + 1) * factorial(K - 1)

for i in range(1, K + 1):
    if N - K < i - 1:
        print(0)
    else:
        denom = factorial(i) * factorial(N - K + 1 - i) * factorial(i - 1) * factorial(K - i)
        v = num // denom

        print(v % x)
H,W = map(int,input().split())
l = [[0]*H]*W
ans = 0
if H%2 == 0 and W%2 == 0:
  ans = (W//2)*H
else:
  ans = (W//2)*(H//2) +(H-(H//2))*(W-(W//2))
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
ans = 0
if H%2 == 0 and W%2 == 0:
  ans = (W//2)*H
elif H == 1 or W == 1:
  print(1)
  exit()
elif H%2 != 0 and W%2 != 0:
  ans = (W//2)*(H//2) + (H-(H//2))*(W-(W//2))
elif H%2 == 0 and W%2 != 0:
  ans = (W//2)*(H//2) + (H//2)*(W-(W//2))
elif H%2 != 0 and W%2 == 0:
  ans = (W//2)*(H//2) + (H-(H//2))*(W//2)
print(ans)
n = int(input())
l = list(map(int, input().split()))
tot = sum(l)
flag = True:
for l_i in l:
  if 2 * l_i >= tot:
    flag = False
    break
if flag:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
tot = sum(l)
flag = True
for l_i in l:
  if 2 * l_i >= tot:
    flag = False
    break
if flag:
  print('Yes')
else:
  print('No')
k= int(input())
runrun = [1,2,3,4,5,6,7,8,9]
for i in range(10, 1000000):
    si = str(i)
    lsi = len(si)
    t =False
    for i in range(lsi-1):
        if abs(int(si[i]) - int(si[i+1])) <= 1:
            t = True
        else:
            t = False
            break
    if t:
        runrun.append(int(si))
print(runrun[k-1])
        

### FIXED CODE ###

from collections import deque

k = int(input())

q =deque([1,2,3,4,5,6,7,8,9])

num = 0

while True:
    x = q.popleft()
    num += 1
    if num == k:
        break
    y = x % 10
    if y != 0:
        q.append(10*x+y-1)
    q.append(10*x+y)
    if y != 9:
        q.append(10*x+y+1)

print(x)
N = int(input())
L,R = [None]*N,[None]*N
for i in range(N):
  L[i],R[i] = map(int,input().split())
L.sort(reverse=True)
R.sort()

def it():
  for l,r in zip(L,R):
    if r < l
      yield 2*(l-r)
    else:
      return

print(sum(it()))

### FIXED CODE ###

N = int(input())

intervals = list(tuple(map(int,input().split())) for _ in range(N))

L = sorted(((l,i) for i,(l,r) in enumerate(intervals)))
R = sorted(((r,i) for i,(l,r) in enumerate(intervals)), reverse=True)

def helper(L,R,turn):
  used = [False]*(N+1)
  used[N] = True

  x = 0
  cost = 0
  while True:
    A = [L,None,R][turn+1]

    i = N
    while used[i]:
      y,i = A.pop()

    if turn*(y-x) < 0:
      cost += abs(x-y)
      x = y
    else:
      break
    turn *= -1
  cost += abs(x)
  return cost

print(max(helper(L.copy(), R.copy(), t) for t in [-1,1]))
N=int(input())
for i in range(N):
    t,x,y = map(int,input().split())
    if x+y>t or (x+y-t)%2:
        print('No')
        exit() 
print('Yes')

### FIXED CODE ###

a,b=map(int,input().split())
if a*b%2==0:
    print('Even')
else:
    print('Odd')
x = raw_input()
print x^3

### FIXED CODE ###

x = input()
print x*x*x
s = input()
z = int(input())
list = [chr(i) for i in range(97,97+26)]
d = []
flag = 0
for j in list:
  indexes = [i for i,x in enumerate(s) if x==j]
  for k in indexes:
    for l in range(len(s)-k):
      d.append(s[k:l+k+1])
  if len(d)==k:
    break
print(sorted(set(d))[z-1])

### FIXED CODE ###

s = input()
z = int(input())
list = [chr(i) for i in range(97,97+26)]
d = []
for j in list:
  indexes = [i for i,x in enumerate(s) if x==j]
  if len(indexes)==0:
    continue
  for k in indexes:
    for l in range(len(s)-k):
      d.append(s[k:l+k+1])
      if len(s[k:l+k+1])==z:
        break
print(sorted(set(d))[z-1])
import os
import random
import re
import sys

def solution(a,b,c,k):
    max=0
    while(k>0):
        while(a>0 and k>0):
            max+=1
            a-=1
            k-=1
        if(k<=0):
            return max
            break
        while(b>0 and k>0):
            b-=1
            k-=1
        if(k<=0):
            return max
            break
        while(c>0 and k>0):
            max-=1
            c-=1
            k-=1
        return max
            
                
if __name__ == '__main__':
    fptr = sys.stdout
    a=int(input())
    b=int(input())
    c=int(input())
    k=int(input())
    result = solution(a,b,c,k)

    fptr.write(str(result) + '\n')


fptr.close()


### FIXED CODE ###

import sys 
a,b,c,k = map(int,input().split())
max=0
if(a==k):
    print(a)
elif(a>k):
    print(k)
else:
    if(a<k):
        max+=a
        k=k-a
    if(b>k):
        print(max)
    else:
        k=k-b
        if(k<=0):
            print(max)
        else:
            if(c>=k):
                max-=k
                print(max)
            elif(c<k):
                max-=c
                print(max)
import sys
s=input()
ans=0
i=0
j=len(s)-1
xi=0
yj=0
while(i<j):

    while(s[i]=='x'):
        i+=1
        xi+=1
#        print(i,xi)

    while(s[j]=='x'):
        j-=1
        yj+=1
#        print(j,yj)

#    print(i,xi,j,yj)
    if(s[i]!=s[j]):
        print(-1)
        sys.exit()
    else:
        ans+=abs(xi-yj)
        xi=0
        yj=0
        i+=1
        j-=1

print(ans)

### FIXED CODE ###

import sys
s=input()
ans=0
i=0
j=len(s)-1
xi=0
yj=0
while(i<j):

    while(i<len(s)-1 and s[i]=='x'):
        i+=1
        xi+=1
#        print(i,xi)

    while(j>0 and s[j]=='x'):
        j-=1
        yj+=1
#        print(j,yj)

#    print(i,xi,j,yj)
    if(s[i]!=s[j]):
        print(-1)
        sys.exit()
    else:
        ans+=abs(xi-yj)
        xi=0
        yj=0
        i+=1
        j-=1

print(ans)
import collections
n = int(input())
a = list(map(str,input().split()))
ls = [i for i in range(10**5)]
c = collections.Counter(a)
comon = c.most_common()
ans = 0

for i in comon:
    if i != 1:
      ls[int(i[0])] = i[1]
      ans += (i[1]*(i[1]-1)//2)

for i in a:
    co = ls[int(i)]
    print(ans-(co*(co-1)//2)+((co-1)*(co-2)//2))

      

### FIXED CODE ###

import collections
n = int(input())
a = list(map(str,input().split()))
ls = [i for i in range(2*10**5)]
c = collections.Counter(a)
comon = c.most_common()
ans = 0

for i in comon:
    if i != 1:
      ls[int(i[0])] = i[1]
      ans += (i[1]*(i[1]-1)//2)

for i in a:
    co = ls[int(i)]
    print(ans-(co*(co-1)//2)+((co-1)*(co-2)//2))
s = input().split() #標準入力　sに値を入れる

def sort(A):
    if len(A) < 2:
        return A
    c = len(A)//2
    return merge(sort(A[:c]), sort(A[c:]))

def merge(X, Y):
    if len(X) < 1:
        return Y
    if len(Y) < 1:
        return X
    if (X[0] > Y[0]):
        return [Y[0]]+ merge(X, Y[1:])
    else:
        return [X[0]] + merge(X[1:], Y)

n = int(s[0])
divisors = []
for i in range(1, int(n**0.5)+1):
    if n % i == 0:
        divisors.append(i)
        if i != n // i:
            divisors.append(n//i)

divisors = sort(divisors)
l = len(divisors)
n1 = divisors[l // 2 - 1]
n2 = divisors[l // 2]
ans = n1 + n2 - 2
print(n2)

### FIXED CODE ###

import math
s = input().split() #標準入力　sに値を入れる
n = int(s[0])
root = int(math.sqrt(n))
ans = 10**18
for i in range(1, root + 1):
    if n % i != 0:
        continue
    j = n / i
    ans = min(ans, i + j - 2)
print(int(ans))
a=int(input())
b=int(input())
abc=[1,2,3]
abc.pop(a)
abc.pop(b)
print(abc[0])


### FIXED CODE ###

a=int(input())
b=int(input())
abc=[1,2,3]
abc.remove(a)
abc.remove(b)
print(abc[0])
def digit_dp(n, m):
    # dp[i][j][k] -> i: 現在見ている桁数
    #                j: n以下が保証されているかどうか
    #                k: m で割った余りの総和
    n = list(map(int, list(str(n))))
    n_len = len(n)
    dp_table = [[[0 for k in range(m)] for j in range(2)] for i in range(n_len + 1)]
    dp_table[0][0][0] = 1

    for i in range(n_len):
        for j in range(2):
            for k in range(m):
                for d in range(0, 10 if j else n[i] + 1):
                    dp_table[i + 1][j or (d < n[i])][(k + d % m) % m] += dp_table[i][j][k]

    return dp_table[-1][0][0] + dp_table[-1][1][0] - 1
    #0 の分、1を減算


a, b = map(int, input().split())
mod = 10**9 + 7
print(digit_dp(a, b) % mod)


### FIXED CODE ###

k = str(input())
d = int(input())

DP = [[[0 for _ in range(d)] for _ in range(2)] for _ in range(len(k)+1)]
DP[0][0][0] = 1

for i in range(len(k)):
    now = int(k[i])
    for j in range(2):
        for mod in range(d):
            for n in range(10):
                # 対象の数字未満が確定する場合
                if j==1 or (j==0 and n < now):
                    next_j = 1
                # 対象の数字とこの桁まで同じ場合
                elif n == now:
                    next_j = 0
                # 対象の数字よりも大きな値の場合
                else: 
                    continue

                n_mod = n % d
                next_mod = (mod + n_mod) % d
                DP[i+1][next_j][next_mod] = (DP[i+1][next_j][next_mod] + DP[i][j][mod]) % (10**9+7)

ans = (DP[len(k)][0][0] + DP[len(k)][1][0] -1) % (10**9+7)
print(ans)
# print(DP)
o1 = (w * h) / 2

l = []
a = h / w

for i in range(h+1):
  l.append((i, w / h * i))
  l.append((i, - h / w * i + h))

if (x, y) in l:
  o2 = 1
else:
  o2 = 0
  
print(o1, o2)
  

### FIXED CODE ###

w, h, x, y = [int(i) for i in input().split()]

o1 = (w * h) / 2

l = [(x, h / w * x), (x, - h / w * x + h)]
l2 = [(0, 0), (w, 0), (0, h), (w, h)]
if (x, y) in l2:
  o2 = 0
elif (x, y) in l:
  o2 = 1
else:
  o2 = 0
  
print(o1, o2)
N = int(input())
X = input()

def popcount(x):
    tmp = x
    count = 0
    while tmp > 0:
        if tmp & 1 == 1:
            count += 1
        tmp >>= 1
    
    return count

x = int(X, 2)
pcx = X.count("1")
pc1 = x % (pcx - 1) if pcx > 1 else 0
pc2 = x % (pcx + 1)


for i in range(N):
    if X[i] == '0':
        X_next = pc2 + pow(2,N-1-i,pcx+1)
        X_pop_next = pcx + 1
    else:
        X_next = pc1 - pow(2,N-1-i,pcx-1)
        X_pop_next = pcx - 1
        
    if X_pop_next == 0:
        print(0)
        continue
        
    X_next = X_next % X_pop_next
    ans = 1
    
    while X_next != 0:
        X_next = X_next % popcount(X_next)
        ans += 1
    
    print(ans)

### FIXED CODE ###

n = int(input())
s = input()
x = int(s, 2)
pcx = s.count("1")
pc1 = x % (pcx - 1) if pcx > 1 else 0
pc2 = x % (pcx + 1)

def f(j):
    cnt = 0
    while j:
        j %= bin(j).count("1")
        cnt += 1
    return cnt

for i, y in enumerate(s):
    k = n - 1 - i
    if y == "0":
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)
U=input()
M=input()
B=input()

print(U[0].M[1].B[2])

### FIXED CODE ###


U=input()
M=input()
B=input()

print(U[0]+M[1]+B[2])