問題文

整数 N が与えられます。あなたは、整数 N に対して以下の操作を 1 回だけ行えます。

• 操作 : N の桁のうち、いくつかの桁を選び（ 0 個でも良い）、それらを全て独立に 0 ~ 9 のいずれかに等確率で置き換える。ただし、先頭に 0 が続く場合 leading zero として解釈する。

あなたの目的は、出来るだけ高い確率で N の値を操作前よりも大きくすることです。最適な戦略をとった場合に操作前の N よりも大きい数を得られる確率を \text{mod } 998244353 で求めてください。

制約

• N は 1 以上 10^{200000} 未満の整数
• N の先頭には余分な 0 は含まれない

入力例 1

502

出力例 1

509104621

この場合、2 桁目と 3 桁目を選ぶのが最適で、 \frac{97}{100} の確率で 502 よりも大きい値を得ることができます。

このとき、100\times 509104621 \equiv 97 \pmod{998244353} が成り立つので、答えとして 509104621 を出力してください。

入力例 2

520

出力例 2

698771048

この場合、3 桁目を選ぶのが最適で、 \frac{9}{10} の確率で 520 よりも大きい値を得ることができます。