Problem Description

You are given a string $ S $ of length $ N $ consisting of characters 0, 1, and ?. Find the number of tuples $(t_0, t_1, \ldots, t_N)$ that satisfy all of the following conditions, modulo $ 998244353 $:

• $ t_0 $ is an empty string.
• For each $i = 0, 1, \ldots, N - 1$, $ t_{i+1} $ is a string obtained by inserting either 0 or 1 into exactly one position in $ t_i $.
• $ t_N $ is a string obtained by replacing each ? in $ S $ with either 0 or 1.

Input Format

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

$ N $ $ S $

Output Format

Output the number modulo $ 998244353 $.

Sample Input and Output

Sample Input #1

3
01?

Sample Output #1

8

Sample Input #2

9
0??001011

Sample Output #2

32400

Sample Input #3

40
1111111111111111111100000000000000000000

Sample Output #3

88808106

Notes/Hints

Constraints

• $1 \le N \le 250,000$.
• $ S $ is a string of length $ N $ consisting of 0, 1, and ?.

Partial Points

• If you solve the dataset where $N \le 5,000$, you will be awarded $ 10 $ points.
• If you solve the dataset without additional constraints, you will be awarded an additional $ 90 $ points.

Sample Explanation 1

The $ 8 $ tuples $ (t_0, t_1, t_2, t_3) $ that satisfy the conditions are:

• $ t_0 $ is an empty string, $ t_1 $ is 0, $ t_2 $ is 00, $ t_3 $ is 010.
• $ t_0 $ is an empty string, $ t_1 $ is 0, $ t_2 $ is 01, $ t_3 $ is 010.
• $ t_0 $ is an empty string, $ t_1 $ is 0, $ t_2 $ is 01, $ t_3 $ is 011.
• $ t_0 $ is an empty string, $ t_1 $ is 0, $ t_2 $ is 10, $ t_3 $ is 010.
• $ t_0 $ is an empty string, $ t_1 $ is 1, $ t_2 $ is 01, $ t_3 $ is 010.
• $ t_0 $ is an empty string, $ t_1 $ is 1, $ t_2 $ is 01, $ t_3 $ is 011.
• $ t_0 $ is an empty string, $ t_1 $ is 1, $ t_2 $ is 10, $ t_3 $ is 010.
• $ t_0 $ is an empty string, $ t_1 $ is 1, $ t_2 $ is 11, $ t_3 $ is 011.

见题面 Input 部分

见题面 Output 部分