問題文

正の整数 $N$ が与えられます。十進数で $N$ を最上位桁が $0$ にならないように表現した時の各桁を、最上位桁が $0$ にならないように自由に並び替えることができるものとします。このとき、全部で何通りの正の整数を作ることができますか。ただし、答えが非常に大きくなる可能性があるので、答えを $998244353$ で割った余りを回答してください。

($21$:$48$ 追記) 一部のテストケース中に先頭が $0$ で始まるテストケースが存在します。なお、どのテストケースにおいても、桁数(文字数)は $200000$ 以下です。(22:26追記)なお、先頭が0のケースでは、入力に含まれている0の個数をちょうど使い、先頭に0が来ないように並び替える場合の数を回答してください。

制約

• $1 \leq N < 10^{200000}$
• $N$ は整数
• ($21$:$48$ 追記) 一部のテストケース中に先頭が $0$ で始まるテストケースが存在します。

入力

$N$

出力

$998244353$ で割った余りを回答してください。

サンプル

120

4

9

1

1942

24

1944

12

11123456789995

212565247