AT_agc066_b [AGC066B] Decreasing Digit Sums

题目描述

题意翻译

定义 $f(x)$ 表示 $x$ 各数位之和，例如 $f(331)=3+3+1=7$，$f(2024)=2+0+2+4=8$，$f(1)=1$ 等。

给定 $n$，你需要找到一个数 $k$ 满足以下条件：

• $1\leq k\leq10^{10000}$；
• 对于任意整数 $1\leq i\leq n$，有 $f(2^{i-1}k)>f(2^ik)$。

输入格式

一行一个正整数 $n$。

输出格式

一行一个整数表示你给出的答案 $k$。

样例 1

输入

3

输出

89

说明/提示

$1\leq n\leq50$。