Coloring Cards 2

Time limit1sMemory limit1024 MB

Summary

Given the colors of the first row of an N by N grid, sum the number of white patterns over all valid colorings where diagonals match and every row has the same white count.

Level: Hard8 of 10
Topics: Combinatorics, Dynamic programming, Math
Solved: No attempts yet

Problem

Yeongwoo made greeting cards for the participants of the year-end contest. The image of Donghyeon, summoned from the entrance greeting card, will greet the participants. There are $N^2$ cards in total, arranged in a square with $N$ rows and $N$ columns. Leehwan is in charge of coloring the cards. Leehwan colors every card either black or white. Some cards in the first row are already colored. The coloring must follow these rules.

To keep the color pattern from getting complicated, a card and the card diagonally below and to its right must have the same color. That is, the card in row $i$ , column $j$ and the card in row $i+1$ , column $j+1$ must have the same color. ( $1 \le i, j < N$ )
In every row, the number of white cards must be the same.

It can be proven that, no matter how the first-row cards are colored, there is at least one way to color the cards that follows these rules.

After all cards are colored, the score of the card array is defined as follows.

Each white card belongs to a pattern. Two white cards belong to the same pattern only if one can move from one to the other through white cards only, moving up, down, left, or right.
The score of the card array is the number of distinct patterns. The shape of a pattern does not matter.

Leehwan wants to know the scores of the card arrays that can result from coloring. Given the coloring of the first row, write a program that prints the sum of the scores of all distinct card arrays that can be obtained by coloring the cards under the rules. Since the answer can be very large, print it modulo $998\,244\,353$ .

Input

The first line contains an integer $N$ .

The second line contains a string of length $N$ consisting of 0, 1, and ?. If the $i$ -th character is ?, the card in row 1, column $i$ is not colored. If it is 0 or 1, the card in row 1, column $i$ is colored black or white, respectively.

Output

Print the sum of the scores of all distinct card arrays that can be obtained by coloring the cards under the rules, modulo $998\,244\,353$ .

Constraints

$3 \leq N \leq 1\,000\,000$
All given numbers are integers.

Examples3

Example 1
Input
```
8
01010101
```
Expected output
```
32
```
Example 2
Input
```
5
?10?1
```
Expected output
```
23
```

Example 3

Input

32
0??1???1?????11?????0????0??1???

Expected output

25165822