No.3098 Linear Reversi
Problem Statement
There is an Othello board that is $N$ squares wide and $1$ square tall. Let $A_i$ denote the $i$-th square from the left of the board. Initially, no pieces are placed on the board.
You perform the following operation $N$ times: choose $1$ square that does not yet have a piece on it, freely decide whether black or white faces up, and place $1$ Othello piece there. Here, the color facing up on a piece is called the "color of the piece". The colors of the pieces get flipped in the same way as in the rules of Othello.
Specifically, for squares $A_x$ , $A_{x+1}$ , $...$ $A_{y-1}$ , $A_y$ ,
- When all of them except $A_y$ have pieces on them and, among those, only the piece on $A_x$ has a different color, placing a piece on $A_y$ with the same color facing up as the piece on $A_x$ makes the colors of the pieces on $A_{x+1}$ , $A_{x+2}$ , $...$ $A_{y-1}$ equal to that of the piece on $A_y$.
- When all of them except $A_x$ have pieces on them and, among those, only the piece on $A_y$ has a different color, placing a piece on $A_x$ with the same color facing up as the piece on $A_y$ makes the colors of the pieces on $A_{x+1}$ , $A_{x+2}$ , $...$ $A_{y-1}$ equal to that of the piece on $A_x$.
You are given a string $S$. The $i$-th character of $S$ means the following:
- If it is
o, a piece is placed on $A_i$ with white facing up. - If it is
x, a piece is placed on $A_i$ with black facing up. - If it is
?, the color of the piece on $A_i$ is missing and unknown.
Letting $M$ be the number of missing parts, there are $2^M$ ways to fill them with white or black pieces. Among these, find the number of final configurations achievable under the above rules, modulo $998244353$.
Input
The input is given from standard input in the following format.$N$ $S$
- $1≦N≦10^6$
- $|S|=N$
- All inputs are integers.
Output
Output the number of achievable Othello board configurations, modulo $998244353$. Print a newline at the end.
Sample
Sample 1
Input
3 ox?
Output
2
Sample 2
Input
5 ox??o
Output
3
Sample 3
Input
10 ??????????
Output
488
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
hamo21