Problem Description

There are $ 2N $ cards. The $ i $ -th ($1 \leq i \leq 2N$) card has the integer $ i $ written on it.

Chisaki and Tsukinose decided to play a game using these cards.

1. The cards are shuffled well, and each player takes $ N $ cards to form their initial hand.
2. The game consists of $ N $ rounds. In each round, both players choose the card with the smallest number from their hand and show it to each other. The player with the larger number on the shown card wins the round. The shown cards are removed from their hands and are not considered in subsequent rounds.

Chisaki and Tsukinose played this game once.

The result of the game is given as a string $ S $ of length $ N $ consisting only of 0 and 1. For any integer $ i $ ($1 \leq i \leq N$), if $ S_i $ is 1, it means that Chisaki won the $ i $ -th round; if $ S_i $ is 0, it means she did not.

How many different initial hands for Chisaki could have led to this game result? Since the answer can be very large, output it modulo $ 998244353 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ S $

Output Format

Output the number of different possible initial hands for Chisaki, modulo $ 998244353 $.

Sample Input and Output

Sample Input #1

2
01

Sample Output #1

1

Sample Input #2

15
111110001011100

Sample Output #2

2100

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $ S $ is a string of length $ N $ consisting only of 0 and 1.

Sample Explanation 1

Consider the case where Chisaki's initial hand has cards with $ 1 $ and $ 4 $, and Tsukinose's initial hand has cards with $ 2 $ and $ 3 $. In this case:
- In the first round, Chisaki shows the card with $ 1 $, and Tsukinose shows the card with $ 2 $. Tsukinose wins the round.
- In the second round, Chisaki shows the card with $ 4 $, and Tsukinose shows the card with $ 3 $. Chisaki wins the round.

Thus, Chisaki's initial hand satisfies the given game result.

见题面 Input 部分

见题面 Output 部分