E - Adjust
Darjeeling
2
s
1024
MB
500
点
問題文
整数 $N$ と長さ $2N$ の文字列 $S$ が与えられます。
$S$ は 0 または 1 からなる文字列であり、 0 と 1 は $N$ 個ずつ存在します。
以下の条件を満たす $(1,2,\ldots,2N)$ の順列 $P$ は $(N!)^2$ 個存在しますが、その各順列について転倒数を求め、それらの総和を $998244353$ で割った余りを求めてください。
- $1\leq i \leq 2N$ について $P_i \leq N \Leftrightarrow S_i = $
0
制約
- $N$ は整数
- $1 \leq N \leq 2 \times 10^5$
- $S$ は
0または1からなる文字列 - $S$ には
0と1が $N$ 個ずつ含まれる
入力
入力は以下の形式で標準入力から与えられます。
$N$
$S$
出力
答えを1行に出力してください。
入力例 1
2
0101
出力例 1
8
順列 $P$ としてあり得るものは
$(1,3,2,4)$
$(2,3,1,4)$
$(1,4,2,3)$
$(2,4,1,3)$
の 4 通りであり、転倒数はそれぞれ $1,2,2,3$ なので、合計は $8$ となります。
入力例 2
7
10101000101110
出力例 2
119426047
$998244353$ で割った余りを出力しましょう。