とここちゃん 「4040」
んぐ 「それって ngng な整数だね！」

正の整数 $x$ について、$x$ の十進表記で上から $i$ 桁目の数字を $x_i$ とします。ただし、十進表記において上位桁に不要な $0$ は付けないものとします。

十進表記で $d$ 桁の正の整数 $x$ が次の条件を両方とも満たすとき、かつその時に限り、$x$ は ngng な整数 であると定義します。

• $x_i \neq x_j$ かつ $x_j \neq x_k$ かつ $x_i \neq x_k$ を満たす $1$ 以上 $d$ 以下の整数の組 $(i, j, k)$ が存在しない
• $x_i \neq x_{i + 1}$ を満たす $1$ 以上 $d$ 未満の整数 $i$ の個数が $3$ 以上の奇数である

整数 $N$ が与えられます。 $1$ 以上 $N$ 以下の整数のうち、ngng な整数の個数を $998244353$ で割ったあまりを求めてください。

• $1 \leq N \leq 10^{ 100{,}000 }$
• 入力は全て整数

以下の制約を追加したデータセットに正解した場合は $1$ 点が与えられる。

• $N \leq 10^6$

入力は以下の形式で標準入力から与えられます。

答えを標準出力に出力してください。