006 - Swap Digits
時間制限 2 秒 / メモリ制限 128 MB / 得点 600 / x 15 /
問題
$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$ で割った余りを出力せよ。