Contest Duration: - (local time) (300 minutes) Back to Home
B - 01 Inversion Expected /

Time Limit: 2 sec / Memory Limit: 2048 MB

### 問題文

0, 1 からなる長さ N の文字列 S が与えられます． 整数の組 (i,j) (1 \leq i < j \leq N) であって，Si 文字目が 1, j 文字目が 0 であるようなものを転倒ペアと呼ぶことにします．

S 内に転倒ペアが存在する限り，以下の操作を行います．

• 転倒ペア (i,j) をランダムに一つ選ぶ．選択はこれ以前の選択と独立で，かつ一様ランダムであるとする． そして，Si 文字目と j 文字目を入れ替える．

### 制約

• 1 \leq N \leq 250000
• S0, 1 からなる長さ N の文字列

### 入力

N
S


### 入力例 1

2
10


### 出力例 1

1


### 入力例 2

3
110


### 出力例 2

499122178


### 入力例 3

1
0


### 出力例 3

0


### 入力例 4

10
1011000010


### 出力例 4

133099253


### 入力例 5

100
0101110010001000111000111001001101001100000111110001010010001010101100011001011011101101100001100111


### 出力例 5

407907276


Score : 1000 points

### Problem Statement

You are given a string S of length N consisting of 0 and 1. We define an inversion pair as a pair of integers (i, j) (1 \leq i < j \leq N) such that the i-th character of S is 1 and the j-th character of S is 0.

As long as there is an inversion pair in S, perform the following operation:

• Randomly choose an inversion pair (i, j). The choice is independent of previous choices and is uniformly random. Then, swap the i-th and j-th characters of S.

Find the expected number of operations, modulo 998244353.

What is the expected value modulo 998244353?

It can be proved that the sought expected value is always rational. Moreover, under the constraints of this problem, it can be proved that if the expected value is expressed as an irreducible fraction \frac{P}{Q}, then Q \neq 0 \pmod{998244353}. Thus, there exists a unique integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Report this R.

### Constraints

• 1 \leq N \leq 250000
• S is a string of length N consisting of 0 and 1.

### Input

The input is given from Standard Input in the following format:

N
S


### Sample Input 1

2
10


### Sample Output 1

1


The expected number of operations is 1.

### Sample Input 2

3
110


### Sample Output 2

499122178


The expected number of operations is 3/2.

### Sample Input 3

1
0


### Sample Output 3

0


### Sample Input 4

10
1011000010


### Sample Output 4

133099253


### Sample Input 5

100
0101110010001000111000111001001101001100000111110001010010001010101100011001011011101101100001100111


### Sample Output 5

407907276