問題文

正の整数 $X$ を（先頭に $0$ がつかない形で）十進法表記したときに $0$ から $9$ の各数字が現れる回数が偶数回であるとき、 $X$ を良い数であると定義します。

例えば $77$ や $144100$ は各数字が偶数回ずつ現れており良い数です。 $110$ や $1213$ は良い数ではありません。

$N$ 以下の正の整数であって良い数であるものの個数を求めてください。答えはとても大きな値になる場合があるので、答えを素数 $998244353$ で割った余りを計算してください。

入力

$N$

$1 \leq N \leq 10^{10000}$

$N$ は正の整数。

出力

答えを $998244353$ で割った余りを1行で出力してください。最後に改行してください。

サンプル

1019

11

37181

261

31415926535897

15778096