Harryxun/stf_run huggingface dataset:
from math import *
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
x = input()
c = x.count('1')

y = 0
for i in range(n):
    y += int(x[i])*2**(n-1-i)
a = [-1]*(y+1)
a[0] = 0
a[1] = 1

for i in range(n):
    ans = 0
    if x[i] == '0':
        c_tmp = c + 1
        y_tmp = y + 2**(n-1-i)
    else:
        c_tmp = c - 1
        y_tmp = y - 2**(n-1-i)
    reg = y_tmp
    while y_tmp != 0:
        ans += 1
        y_tmp = y_tmp % c_tmp
        c_tmp = format(y_tmp,'b').count('1')
        try:
            if 0 < y_tmp < n and a[y_tmp] != -1:
                ans += a[y_tmp]
                break
        except:
            continue
    print(ans)
    try:
        a[reg] = ans
    except:
        continue




### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    a = xdec % (m+1)
    b = xdec % (m-1) if m > 1 else 0

    num = [0]*N
    for i in range(1, N):
        num[i] = num[i % bin(i).count('1')] + 1

    for i in range(N):
        if xbin[i] == '0':
            y = ( a + pow(2, N-i-1, m+1) ) % ( m+1 )
            print(num[y] + 1)
        elif m <= 1:
            print(0)
        else:
            y = ( b - pow(2, N-i-1, m-1) ) % ( m-1 )
            print(num[y] + 1)

if __name__ == '__main__':
    solve()
class BellmanFord():
    class Edge():
        def __init__(self, _from, _to, _cost):
            self.from_ = _from
            self.to = _to
            self.cost = _cost

    def __init__(self):
        self.edges = []  # 辺
        self.v_set = set()  # 頂点の集合

    @property
    def E(self):
        return len(self.edges)

    @property
    def V(self):
        return len(self.v_set)

    def add(self, _from, _to, _cost):
        self.edges.append(self.Edge(_from, _to, _cost))
        self.v_set.add(_from)
        self.v_set.add(_to)

    def shortest_path(self, s):
        d = [float("inf")] * self.V
        d[s] = 0

        while True:
            do_update = False
            for i in range(self.E):
                e = self.edges[i]
                if d[e.from_] != float("inf") and d[e.to] > d[e.from_] + e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    do_update = True

            if not do_update: break

        return d

    def exist_negative_loop(self):
        d = [0] * self.V
        for i in range(self.V):
            for j in range(self.E):
                e = self.edges[j]
                if d[e.to] > d[e.from_] + e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    if i == self.V - 1: return True
        return False

n, m, p = map(int, input().split())
abc = []
e = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    abc.append([a-1, b-1, p-c])
    e[a-1].append(b-1)

v = [0] * n
v[0] = 1
def bfs(x, depth):
    #print(x, depth, e[x])
    if depth >= n:
        return 1
    if x == n-1:
        return 0
    temp = 1
    for y in e[x]:
        #print(y)
        if v[y] == 1 or x == y:
            continue
        #print(x, y)
        ret = bfs(y, depth + 1)
        if ret == 0:
            v[y] = 1
            temp = 0
    return temp

bfs(0, 0)

bf = BellmanFord()
for a, b, c in abc:
    if v[a] * v[b] == 1:
        bf.add(a, b, c)
    else:
        bf.add(a, b, float('inf'))

if bf.exist_negative_loop():
    print(-1)
    exit()
else:
    print(max(0, - bf.shortest_path(0)[-1]))

### FIXED CODE ###

n, m, p = map(int, input().split())
abc = []
for _ in range(m):
    a, b, c = map(int, input().split())
    abc.append([a-1, b-1, p-c])

d = [float('inf')] * n
d[0] = 0

for i in range(n):
    for a, b, c in abc:
        d[b] = min(d[b], d[a] + c)

for a, b, c in abc:
    if d[b] > d[a] + c:
        d[b] = - float('inf')

for i in range(n):
    for a, b, c in abc:
        d[b] = min(d[b], d[a] + c)

if d[n-1] == - float('inf'):
    print(-1)
else:
    print(max(0, - d[n-1]))
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

def f(x):
    if x == 1 or x == 0:
        return 1
    else:
        return f(x-1) + f(x-2)

def sol(a):
    for i in range(m - 1):
        if a[i+1] - a[i] == 1:
            print(0)
            return
    mod = 10 ** 9 + 7
    stairs = []
    now = 0
    for i in range(m):
        stairs.append(a[i] - 1 - now)
        now = a[i] + 1
    stairs.append(n - now)

    ans = 1
    for ele in stairs:
        ans *= f(ele)

    print(ans % mod)


sol(a)
    


### FIXED CODE ###

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

ways = [1, 1]
for i in range(2, n + 1):
    ways.append(ways[i-2] + ways[i-1])

stairs = []
now = 0
for i in range(m):
    stairs.append(a[i] - 1 - now)
    now = a[i] + 1

stairs.append(n - now)

ans = 1
for ele in stairs:
    if ele == -1:
        ans *= 0
    else:
        ans *= ways[ele]

mod = 10 ** 9 + 7
print(ans % mod)
n = int(input())
a_L = list(map(int,input().split()))
 
ans = 0
while True:
  for i in range(a_L):
    if a_L[i]%2 != 0:
      print(ans)
      exit()
    a_L[i] = a_L[i]%2
  ans += 1

### FIXED CODE ###

import sys

n = int(input())
a_L = list(map(int,input().split()))
counter = 0


while True:
    for val in a_L:
        if val % 2 != 0:
            print(counter)
            sys.exit(0)
    counter +=1
    a_L = [i/2 for i in a_L]
h, w = map(int, input().split())
    ki = int(h/2) + h%2
    gu = int(h/2)

    sum_ki = ki *(int(w/2) + w%2)
    sum_gu = gu * (int(w / 2) )
    print(sum_ki+sum_gu)

### FIXED CODE ###

def b():
    h, w = map(int, input().split())
    if (h == 1) or (w == 1):
        print("1")
    else:
        ki = int(h / 2) + h % 2
        gu = int(h / 2)

        sum_ki = ki * (int(w / 2) + w % 2)
        sum_gu = gu * (int(w / 2))
        print(sum_ki + sum_gu)


def c():
    a, b, c = map(int, input().split())
    ab = 4 * a * b
    a_b_c = c - (a + b)
    a_b_c_2 = a_b_c ** 2
    if a_b_c <= 0:
        print("No")
    else:
        if ab < a_b_c_2:
            print("Yes")
        else:
            print("No")


if __name__ == "__main__":
    b()
NK = input()
NK = N.split(" ")
N = int(NK[0])
K = int(NK[1])


h = []
for i in range(N):
  h.append(int(input()))
  
  
h.sort()
ans = h[-1] - h[0]

for i in range(N-K+1):
  ans = min(ans, h[i+K-1] - h[i])
print(ans)

### FIXED CODE ###

NK = input()
NK = NK.split(" ")
N = int(NK[0])
K = int(NK[1])


h = []
for i in range(N):
  h.append(int(input()))
  
  
h.sort()
ans = h[-1] - h[0]

for i in range(N-K+1):
  ans = min(ans, h[i+K-1] - h[i])
print(ans)
#include <bits/stdc++.h>
using namespace std;
int A[101],B[101],C[101],D[101];
int ans;
int N,M,Q;
void dfs(vector<int> v)
{
    // cout<<" hi"<<"";
    if(v.size()==N)
    {
        int sum=0;
        for(int i=0;i<Q;i++)
        {
            if (v[B[i]-1]-v[A[i]-1]==C[i])
            {
                sum+=D[i];
            }
        }
        ans=max(ans,sum);
    }
    else
    {
        for(int i=v[v.size()-1];i<=M;i++)
        {
            vector<int> n=v;
            n.push_back(i);
            dfs(n);
        }
    }
}
int main() 
{  
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ans=INT_MIN;
    cin>>N>>M>>Q;
    for(int i=0;i<Q;i++)
    {
        cin>>A[i]>>B[i]>>C[i]>>D[i];
    }
    for(int i=1;i<=M;i++)
    {
        vector<int> v;
        v.push_back(i);
        dfs(v);
    }
    cout<<ans<<" ";
}

### FIXED CODE ###

K=int(input())
N,M=map(int,input().split())
FLAG=0
for i in range(1000):
    if K*i>=N and K*i<=M:
        print("OK")
        FLAG=1
        break
if FLAG==0:
    print("NG")
import sys,math,collections,
input = sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
B = []
C = []
for i,a in enumerate(A):
    B.append(i+a)
    C.append(i-a)
cnt = 0
Bc = collections.Counter(B)
Cc = collections.Counter(C)

for key,val in Bc.items():
    cnt += val*Cc[key]
print(cnt)


### FIXED CODE ###

import sys,collections
input = sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
B = []
C = []
for i,a in enumerate(A):
    B.append(i+a)
    C.append(i-a)
cnt = 0
Bc = collections.Counter(B)
Cc = collections.Counter(C)

for key,val in Bc.items():
    cnt += val*Cc[key]
print(cnt)
ab = int(input().replace(" ", "")
if ab ** (1 / 2) % 1 == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

ab = int(input().replace(" ", ""))
if ab ** (1 / 2) % 1 == 0:
  print("Yes")
else:
  print("No")
N,M=map(int,input().split())
L=[list(map(int,input().split())) for i in range(N)]
import sys
sys.setrecursionlimit(10**5)
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
u=UnionFind(M)
used=[0]*M
for x,*l in L:
    used[l[0]-1]=1
    for i in range(x-1):
        used[l[i+1]-1]=1
        u.unite(l[i]-1,l[i+1]-1)
print(['NO','YES'][u.size(L[0][1])==sum(used)])

### FIXED CODE ###

N,M=map(int,input().split())
L=[list(map(int,input().split())) for i in range(N)]
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
u=UnionFind(M)
used=[0]*M
for x,*l in L:
    used[l[0]-1]=1
    for i in range(x-1):
        used[l[i+1]-1]=1
        u.unite(l[i]-1,l[i+1]-1)
print(['NO','YES'][u.size(L[0][1]-1)==sum(used)])
# -*- coding: utf-8 -*-
"""
Created on Sat May 05 21:59:05 2018

@author: ashida
"""


import numpy as np

H, W = map(int, raw_input().split())

S = np.zeros((H, W))

d_flag = 0

for i in range(H):
    tmp = list(raw_input())
    for j in range(W):
        if tmp[j] == "#":
            S[i, j] = 1
            d_flag = 1
        else:
            S[i, j] = 0



for i in range(H):
    for j in range(W):
        if S[i, j] == 1:
            flag = 0
            if i>1:
                a1 = S[i-1, j]
            else:
                a1 = 0
            if j>1:
                a2 = S[i, j-1]
            else:
                a2 = 0
            if i<H-1:
                a3 = S[i+1, j]
            else:
                a3 = 0
            if j<W-1:
                a4 = S[i, j+1]
            else:
                a4 = 0
            if a1+a2+a3+a4 == 0:
                d_flag = 0
                
if d_flag == 1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a, b = map(int, raw_input().split())

if b < a:
    print(a-1)
else:
    print(a)
N = int(input())
ans = 1
i = []
 
list = [i for i in input().split()]

 
for a in range(N-1):
  ans = ans * i[a]
 
  if ans > 10**18:
    ans = -1
 
print(ans)

### FIXED CODE ###

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

ans = 1

if 0 in a:
    print("0")
    exit()

for i in a:
    ans *= i

    if ans > 10**18:
        print("-1")
        exit()
        
print(ans)
import sys
def I(): return int(sys.stdin.readline().rstrip())

K = I()
if K % 2 == 0 or K % 5 == 0:
    print(-1)
    exit()
if K % 7 == 0:
    K //= 7

A = [1]  # A[i] = 10**i mod K
for i in range(K-2):
    A.append((A[-1]*10) % K)

s = A[0]
for i in range(1,K):
    if s % K == 0:
        print(i)
        exit()
    else:
        s += A[i]
        s %= K


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

K = I()
if K % 2 == 0 or K % 5 == 0:
    print(-1)
    exit()
if K % 7 == 0:
    K //= 7

A = [1]
for i in range(K+2):
    A.append((A[-1]*10) % K)

a = 1
i = 1
while True:
    if a % K == 0:
        print(i)
        break
    else:
        a += A[i]
        a %= K
        i += 1
a,b,c=map(int,input().split())
print(["NO","YES"][(b*10+c)%4==0]

### FIXED CODE ###

a,b,c=map(int,input().split())
print(["NO","YES"][(b*10+c)%4==0])
import math 

MOD = 10**9 + 7
N = int(input())
ABC = []
zero_cases = 1
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_cases = 2
    elif a * b >=0 and a != 0:
        ABC.append([ math.atan2(abs(b),abs(a)), abs(a), abs(b),1])
    else:
        ABC.append([math.atan2(abs(a),abs(b)), abs(b), abs(a), -1])
ABC.sort()
current_arg = ABC[-1][0]
current_x = ABC[-1][1]
current_y = ABC[-1][2]
group = []
daiich = 0
daini = 0
while ABC:
    current = ABC.pop()
    di = {}
    if current[0] == current_arg:
        if current[3]==1:
            daiich += 1
        else:
            daini += 1
    else:
        group += [[daiich, daini]]
        daiich = 0
        daini = 0
        if current[3]==1:
            daiich += 1
        else:
            daini += 1
        if ABC:
            current_arg = current[0]
            current_x = current[1]
            current_y = current[2]
else:
    group += [[daiich, daini]]
    daiich = 0
    daini = 0

ans = zero_cases
for u, v in group:
    ans *= (2**u + 2**v -1)
    ans %= MOD
print(ans-1)

### FIXED CODE ###

from math import gcd 
from collections import defaultdict

def to_irreducible(a, b):
    if a == 0:
        return [0, 1]
    GCD = gcd(a, b)
    return [a//GCD, b//GCD]

MOD = 10**9 + 7
N = int(input())
daiichi_dict = defaultdict(int)
daini_dict = defaultdict(int)
zero_cases = 0

for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_cases += 1
    elif a * b >=0 and b != 0:
        a, b = to_irreducible(abs(a), abs(b))
        daiichi_dict[(a,b)] += 1
    else:
        a, b = to_irreducible(abs(b), abs(a))
        daini_dict[(a,b)] += 1
        daiichi_dict[(a,b)] += 0


ans = 1 
for key, value_daiichi in daiichi_dict.items():
    value_daini = daini_dict[key]
    ans *= (2**value_daiichi + 2**value_daini -1)
    ans %= MOD
print((ans+zero_cases-1) % MOD)
s = input()
t = input()

sl = list(s)
tl = list(t)

count = 0

for (a, b) in zip(sl, tl):
  if a!=b:
    count++
    
print(count)


### FIXED CODE ###

s = input()
t = input()

sl = list(s)
tl = list(t)

count = 0

for (a, b) in zip(sl, tl):
  if a!=b:
    count+=1
    
print(count)
n,k,x,y = [int().split() for _ in range(4)]
print(k*x+(n-k)*y if n>=k else k*x)

### FIXED CODE ###

n,k,x,y = [int(input()) for _ in range(4)]
print(k*x+(n-k)*y if n>=k else n*x)
import sys
from collections import deque

readline = sys.stdin.readline
readlines = sys.stdin.readlines

s = readline().rstrip()
q = readline()
queries = readlines()
s = deque(s)
tot_1 = 0
for i in queries:
    if i[0] == '1':
        tot_1 += 1
        continue
    c = i[4]
    if (tot_1 + int(i[2])) % 2 == 0:
        s.append(c)
    else:
        s.appendleft(c)
ans = "".join(queue) if tot_1 % 2 == 0 else "".join(reversed(queue))
print(ans)

### FIXED CODE ###

import sys
from collections import deque

readline = sys.stdin.readline
readlines = sys.stdin.readlines

s = readline().rstrip()
q = readline()
queries = readlines()
s = deque(s)
tot_1 = 0
for i in queries:
    if i[0] == '1':
        tot_1 += 1
        continue
    c = i[4]
    if (tot_1 + int(i[2])) % 2 == 0:
        s.append(c)
    else:
        s.appendleft(c)
ans = "".join(s) if tot_1 % 2 == 0 else "".join(reversed(s))
print(ans)
H, N=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(N)]

nums=[-1]*20001
for i in range(N):
  if nums[AB[i][0]]<0:
    nums[AB[i][0]]=AB[i][1]
  else:
    nums[AB[i][0]]=min(AB[i][1], nums[AB[i][0]])
  
for i in range(1, H):
  if nums[i]>0:
    for j in range(N):
      if nums[i+AB[j][0]]>0:
        if nums[i+AB[j][0]]>nums[i]+AB[j][1]:
          nums[i+AB[j][0]]=nums[i]+AB[j][1]
      else:
        nums[i+AB[j][0]]=nums[i]+AB[j][1]
      
for i in range(H, 20000):
  if nums[i]>0:
    anss.append(nums[i])
    
print(min(nums))

### FIXED CODE ###

H, N=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(N)]

nums=[-1]*20001
for i in range(N):
  if nums[AB[i][0]]<0:
    nums[AB[i][0]]=AB[i][1]
  else:
    nums[AB[i][0]]=min(AB[i][1], nums[AB[i][0]])
  
for i in range(1, H):
  if nums[i]>0:
    for j in range(N):
      if nums[i+AB[j][0]]>0:
        if nums[i+AB[j][0]]>nums[i]+AB[j][1]:
          nums[i+AB[j][0]]=nums[i]+AB[j][1]
      else:
        nums[i+AB[j][0]]=nums[i]+AB[j][1]
      
anss=[]
for i in range(H, 20000):
  if nums[i]>0:
    anss.append(nums[i])
    
print(min(anss))
import math

A,B,C,D = map(int,input().split())
total = B - A + 1

tmp = (C * D) // math.gcd(C,D) 


C_1 = B//C
C_2 = (A-1)//C
C_total = C_1 - C_2

D_1 = B//D
D_2 = (A-1)//D
D_total = D_1 - D_2

tmp_1 = B//tmp
tmp_2 = (A-1)//tmp
tmp_total = tmp_1 - tmp_2
cnt = C_total + D_total - tmp_total
print(total-cnt)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd (a, b)


A,B,C,D = map(int,input().split())
total = B - A + 1

tmp = lcm(C,D) 


C_1 = B//C
C_2 = (A-1)//C
C_total = C_1 - C_2

D_1 = B//D
D_2 = (A-1)//D
D_total = D_1 - D_2

tmp_1 = B//tmp
tmp_2 = (A-1)//tmp
tmp_total = tmp_1 - tmp_2
cnt = C_total + D_total - tmp_total
print(total-cnt)
a,b = map(int, input().split())

if 2b>=a:
	print(0)
else:
	print(a-2b)

### FIXED CODE ###

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

if 2*b>=a:
	print(0)
else:
	print(a-2*b)
n = int(input())
for i in range(n):
    t, x, y = map(int, input().split())
    if x + y < t or (X + y) % 2 != t % 2:                                                                         
        print("No")
        exit()
print("Yes")

### FIXED CODE ###

n = int(input())
for i in range(n):
    t, x, y = map(int, input().split())
    if x + y > t or ((x + y) % 2 != t % 2):                                                                       
        print("No")
        exit()
print("Yes")
print("ABC" if input()<1000 else "ABD")

### FIXED CODE ###

a=int(input())
if a<1000:
  print("ABC")
else:
  print("ABD")
import sys
import math
sys.setrecursionlimit(10**6)

MOD = 10**9 + 7
def mod_pow(x, mod):
    xx = [1, x]
    def _pow(y, x=x):
        nonlocal xx
        if y == 0:
            return 1
        while len(xx) <= math.log(y, 2)+1:
            v = xx[-1] * xx[-1]
            v %= mod
            xx.append(v)
        i = 1
        result = 1
        while y > 0:
            if y % 2 == 1:
                result *= xx[i]
                result %= mod
            y = y >> 1
            i += 1
        return result
    return _pow

pow9 = mod_pow(9, MOD)

def f(n):
    if n == 1:
        return 0
    else:
        return 10 * f(n-1) + 2 * pow9(n-2)
def main():
    N = int(input())
    ans = f(N)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
MOD = 10**9 + 7

def mod_pow(x, mod):
    xx = [1, x]
    def _pow(y, x=x):
        nonlocal xx
        if y == 0:
            return 1
        while len(xx) <= math.log(y, 2)+1:
            v = xx[-1] * xx[-1]
            v %= mod
            xx.append(v)
        i = 1
        result = 1
        while y > 0:
            if y % 2 == 1:
                result *= xx[i]
                result %= mod
            y = y >> 1
            i += 1
        return result
    return _pow

pow10 = mod_pow(10, MOD)
pow9 = mod_pow(9, MOD)
pow8 = mod_pow(8, MOD)

def f(n):
    ans = pow10(n) - (2 * pow9(n) - pow8(n))
    ans %= MOD
    return ans


def main():
    N = int(input())
    ans = f(N)
    print(ans)

if __name__ == '__main__':
    main()
a, b, c = sys.stdin.readline().split()

if a + b >= c:
    print("Yes")
else : 
    print("No")

### FIXED CODE ###

import sys

[a, b, c] = map(int,sys.stdin.readline().split())

if a + b >= c :
    print("Yes")
else : 
    print("No")
N = int(input())
a = list(map(int, input().split()))

import functools
import math

gcd = []
for i in range(N):
    list_not_i = a.copy()
    list_not_i.remove(a[i])
    gcd.append(functools.reduce(math.gcd, list_not_i))

print(str(max(gcd)))

### FIXED CODE ###

import functools
import fractions
N = int(input())
a = list(map(int, input().split()))

L = [0] * N
for i in range(N) :
        if i == 0 :
                L[0] = 0
        elif i == 1 :
                L[1] = a[0]
        else :
                L[i] = fractions.gcd(L[i-1], a[i-1])

a.reverse()
R = [0] * N
for i in range(N) :
        if i == 0 :
                R[0] = 0
        elif i == 1 :
                R[1] = a[0]
        else :
                R[i] = fractions.gcd(R[i-1], a[i-1])
R.reverse()
a.reverse()

gcd = [0] * N
for i in range(N) :
        if i == 0 :
                gcd[0] = R[0]
        elif i == N-1 :
                gcd[N-1] = L[N-1]
        else :
                gcd[i] = fractions.gcd(L[i],R[i])

print(max(gcd))
import sys

sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
graph = [set([]) for _ in range(M)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a - 1].add(b - 1)
    graph[b - 1].add(a - 1)


def dfs(graph, visited, v):
    if all(visited):
        return 1

    cnt = 0
    for u in graph[v]:
        if visited[u]:
            continue
        visited[u] = True
        cnt += dfs(graph, visited, u)
        visited[u] = False

    return cnt


visited = [False] * len(graph)
visited[0] = True
ans = dfs(graph, visited, 0)
print(ans)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
graph = [set([]) for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a - 1].add(b - 1)
    graph[b - 1].add(a - 1)


def dfs(graph, visited, v):
    if all(visited):
        return 1

    cnt = 0
    for u in graph[v]:
        if visited[u]:
            continue
        visited[u] = True
        cnt += dfs(graph, visited, u)
        visited[u] = False

    return cnt


visited = [False] * len(graph)
visited[0] = True
ans = dfs(graph, visited, 0)
print(ans)
n=int(input())
b = [map(int, input().split())]
mostHeight =b[0]
count = 0
for i in b:
    if(i >= mostHeight):
        mostHeight = i
        count += 1
print(count)


### FIXED CODE ###

a,b = map(int, input().split())
if a != b:
    x= max([a,b])*2 -1
else:
    x =a*2
print(x)