AT_utpc2022_h Digit Slot

给定一个整数 $N$，你可以对 $N$ 执行如下**操作**一次： - **操作**：任选 $N$ 的若干位数（也可以不选），每一位单独等概率地替换成 $0$ 到 $9$ 之间的任意一个数字。若操作后数字前出现了 $0$，则这些 $0$ 认为是前导零。 你的目标是，以尽可能高的概率使得到的新数比操作前的 $N$ 更大。请在采用最优策略的情况下，计算操作后得到比原来大的数字的概率，并对 $998244353$ 取模。 本题中所求概率一定是有理数。在题目的约束条件下，设所求概率为最简分数 $\frac{y}{x}$，则 $x$ 一定不会被 $998244353$ 整除。 此时，存在唯一的 $0$ 到 $998244352$ 之间的整数 $z$，使得 $xz \equiv y \pmod{998244353}$。请输出这个 $z$。

输入仅一行，包含一个整数 $N$。

输出一行答案。

### 样例解释 1 本例中，最优做法是选择第 2、3 位，这样有 $\frac{97}{100}$ 的概率得到比 $502$ 更大的数字。 此时有 $100\times 509104621 \equiv 97 \pmod{998244353}$ 成立，所以输出 $509104621$。 ### 样例解释 2 本例中，最优做法是选择第 3 位，这样有 $\frac{9}{10}$ 的概率得到比 $520$ 更大的数字。 # 提示 - $N$ 是一个大于等于 $1$ 且小于 $10^{200000}$ 的整数。 - $N$ 的最高位不会有多余的前导 $0$。 由 ChatGPT 5 翻译