No.3242 Count 8 Included Numbers (Hard)
タグ : / 解いたユーザー数 93
作問者 :
AngrySadEight
/ テスター :
👑 
p-adic
👑 
ygussany
問題文
この問題は Count 8 Included Numbers (Easy)（コンテスト A 問題）と同じ設定であり，制約およびその他の細部のみが異なります．
この問題に正解するコードを提出することで，Count 8 Included Numbers (Easy) にも正解できます．
AngrySadEight さんは，$8$ という数字が大好きです．そこで，$8$ が含まれる数がいくつあるかを数えてみることにしました．
$N$ 以下の正整数の中で，十進表記において数字の $8$ が含まれるものはいくつあるか求めてください．
ただし，答えは非常に大きくなることがあるので，答えを $998244353$ で割った余りを出力してください．
制約
- $N$ は整数
- $1 \leq N < 10^{888888}$
入力
入力は以下の形式で標準入力から与えられる．
$N$
出力
答えを $998244353$ で割った余りを出力せよ．
サンプル
サンプル1
入力
8
出力
1
$8$ 以下の正整数であって $8$ を含むものは，$8$ の $1$ 個です．したがって，$1$ を出力してください．
サンプル2
入力
88
出力
17
$88$ 以下の正整数であって $8$ を含むものは，$8, 18, 28, 38, 48, 58, 68, 78, 80, 81, 82, 83, 84, 85, 86, 87, 88$ の $17$ 個です．したがって，$17$ を出力してください．
サンプル3
入力
1
出力
0
$1$ 以下の正整数であって $8$ を含むものは存在しません．したがって，$0$ を出力してください．
サンプル4
入力
888
出力
241
サンプル5
入力
888888888888888888888888
出力
241265183
入力が $64$ ビット整数の範囲内に収まらないことがあることに注意してください．また，答えを $998244353$ で割った余りを出力してください．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。