問題文

横 $N$ マス縦 $1$ マスのオセロ盤があります。オセロ盤の左から $i$ マス目を $A_i$ とおきます。最初、オセロ盤にコマは置かれていません。
あなたは、マスのうちまだコマが置かれていないものを $1$ つずつ選び、黒白どちらを上にするかを自由に決めたうえで、オセロのコマを $1$ つずつ置く操作を $N$ 回行います。この際、コマの上を向いている色のことを「コマの色」と呼ぶことにします。このコマの色はオセロのルールと同様に入れ替わります。

具体的には、マス目 $A_x$ , $A_{x+1}$ , $...$ $A_{y-1}$ , $A_y$ について、

• $A_y$ を除く全てにコマが乗っておりそのうち $A_x$ のもののみが異なる色である状態のときに、 $A_y$ に $A_x$ 上のコマの色と同じ色を上にした状態でコマを置くと、 $A_{x+1}$ , $A_{x+2}$ , $...$ $A_{y-1}$ 上のコマの色が $A_y$ のものと等しくなる。
• $A_x$ を除く全てにコマが乗っておりそのうち $A_y$ のもののみが異なる色である状態のときに、 $A_x$ に $A_y$ 上のコマの色と同じ色を上にした状態でコマを置くと、 $A_{x+1}$ , $A_{x+2}$ , $...$ $A_{y-1}$ 上のコマの色が $A_x$ のものと等しくなる。

文字列 $S$ が与えられます。 $S$ の $i$ 文字目について、

• o であれば $A_i$ にはコマが白を上に向けて置かれている
• x であれば $A_i$ にはコマが黒を上に向けて置かれている
• ? であれば $A_i$ のコマの色は欠けていてわからない

欠けた部分の個数を $M$ 個としたときにそこを白か黒のコマで埋めるとしてその埋め方は $2^M$ ありますが、そのうち上のルールによって実現可能な最終配置の個数を $998244353$ で割ったあまりを求めてください。

入力

$N$
$S$

• $1≦N≦10^6$
• $|S|=N$
• 入力はすべて整数

出力

実現可能なオセロ盤の盤面の個数を $998244353$ で割ったあまりを求めてください。 最後に改行してください。

サンプル

3
ox?

2

5
ox??o

3

10
??????????

488