006 - Swap Digits

時間制限 2 秒 / メモリ制限 128 MB / 得点 600 / x 15 /


TLE
2sec
MLE
128MB
得点
600

問題

$K$ 桁の正整数 $X$ が与えられる。
$X$ の左から $k$ 番目 $(1 \leq k \leq K)$ の桁の数を $X_k$ と表す。
ここで、任意の $i, j \ (1 \leq i, j \leq K, i \neq j)$ を選び、$X_i, X_j$ を入れ替える操作を任意の回数行う。
この操作によってできる新たな整数を $X'$ としたとき、考えられる $X'$ 全てについての集合を $S$ とする。
ただし、$S$ は重複を許さない。
また、先頭に $0$ が $n$ 個 $(0 \leq n \leq K - 1)$ 続く $X'$ は、$S$ において有効なものとし、先頭 $n$ 個の $0$ は考慮しない。
例として、$01$ は $1$ であり、$0000314$ は $314$ である。
$S$ の全ての要素の総和を $998244353$ で割った余りを求めよ。

入力

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

$K$ $X$

出力

総和を $998244353$ で割った余りを出力せよ。
出力の末尾には改行を入れること。

制約

  • $1 \leq K \leq 10^5$
  • $10^{K - 1} \leq X \lt 10^K$
  • 入力はすべて整数である。

入出力例

入力例1

3 314

出力例1

1776

$314$ に操作を行ってできる整数として考えられるものは、$314, 341, 134, 143, 413, 431$ である。
これらの総和である $1776$ を出力する。


入力例2

4 1333

出力例2

11110

$1333$ に操作を行ってできる整数として考えられるものは、$1333, 3133, 3313, 3331$ である。
これらの総和である $11110$ を出力する。


入力例3

5 90000

出力例3

99999

$90000$ に操作を行ってできる整数として考えられるものは、$90000, 9000, 900, 90, 9$ である。
これらの総和である $99999$ を出力する。


入力例4

76 8363562156007085841705385838305105744383512895208096085941574935007192235285

出力例4

100006536

$998244353$ で割った余りを出力せよ。