ストーリー

ゆ～さんは並行世界について研究している研究者ですが、今日は休んで助手であるあなたとのんびりお話をしています。

「よーし問題だ。$10$ 億までの正整数のうち僕の嫌いな数、すなわち404 を含まないのは何個あるかな？」

あなたはそれは面倒だからと機械に計算させようとしました。

コードを書いていたところ、ゆ～さんにそれが見つかってしまいました。そしてこう言われました。

「ちょ、それはナシだろ....あ、いや、やっぱり使ってもいいよ。ただ、機械を使うなら $10$ 億じゃあ小さいよね～。このくらいはいけるでしょ。」

問題文

$N$ 以下の正整数のうち、以下の条件を満たすものの個数を求めてください。

• その値の十進表記を文字列として解釈したとき、どの連続する $3$ 文字の部分文字列も404でない

ただし、求める値は非常に大きくなることがあるので、その値を $998244353$ で割ったあまりを出力してください。

また、与えられる $N$ の値が極めて大きくなることがある点に注意してください。

入力

$N$

制約

• $1\leq N \leq$ $10^{1000000}$ $=$ $10^{10^6}$
• 入力はすべて整数

出力

答えを一行に出力し、最後に改行してください。

サンプル

1000

999

98765432109876543210

848152577