AT_utpc2022_h Digit Slot

整数 $ N $ が与えられます。あなたは、整数 $ N $ に対して以下の**操作**を $ 1 $ 回だけ行えます。 - **操作** : $ N $ の桁のうち、いくつかの桁を選び（ $ 0 $ 個でも良い）、それらを全て独立に `0` ~ `9` のいずれかに等確率で置き換える。ただし、先頭に $ 0 $ が続く場合 leading zero として解釈する。 あなたの目的は、出来るだけ高い確率で $ N $ の値を操作前よりも大きくすることです。最適な戦略をとった場合に操作前の $ N $ よりも大きい数を得られる確率を $ \text{mod } 998244353 $ で求めてください。 確率 $ \text{mod } 998244353 $ の定義この問題で求める確率は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 $ \frac{y}{x} $ で表したときに $ x $ が $ 998244353 $ で割り切れないことが証明できます。 このとき $ xz \equiv y \pmod{998244353} $ を満たすような $ 0 $ 以上 $ 998244352 $ 以下の整数 $ z $ が一意に定まります。この $ z $ を答えてください。

入力は以下の形式で標準入力から与えられる。 > $ N $

答えを $ 1 $ 行に出力せよ。

### Sample Explanation 1 この場合、 $ 2 $ 桁目と $ 3 $ 桁目を選ぶのが最適で、 $ \frac{97}{100} $ の確率で $ 502 $ よりも大きい値を得ることができます。 このとき、 $ 100\times 509104621 \equiv 97 \pmod{998244353} $ が成り立つので、答えとして $ 509104621 $ を出力してください。 ### Sample Explanation 2 この場合、 $ 3 $ 桁目を選ぶのが最適で、 $ \frac{9}{10} $ の確率で $ 520 $ よりも大きい値を得ることができます。 ### Constraints - $ N $ は $ 1 $ 以上 $ 10^{200000} $ 未満の整数 - $ N $ の先頭には余分な $ 0 $ は含まれない