問題文

$N + 1$ 個のマスが一列に並んでおり，順に $0, 1, \ldots, N$ の番号が付けられています． また o，x のみからなる長さ $N + 1$ の文字列 $S = S_0 S_1 \cdots S_N$ が与えられ，$S_i$ が o のときマス $i$ に石がないことを，$S_i$ が x のときマス $i$ に石があることを表します．マス $0$ とマス $N$ には石がないことが保証されます．

三段跳びが得意な高橋君はマス $0$ からスタートし，以下の操作を $0$ 回以上好きな回数繰り返すことでマス $N$ でちょうど停止することを目指します．

• 正整数 $k$ を 1 つ選ぶ．
• 現在位置をマス $i$ とする．マス $i + 2 k$ が存在しそこに石がないならばマス $i + 2 k$ に移動する．さもなくば転倒する．
• 現在位置をマス $i$ とする．マス $i + 3 k$ が存在しそこに石がないならばマス $i + 3 k$ に移動する．さもなくば転倒する．
• 現在位置をマス $i$ とする．マス $i + 5 k$ が存在しそこに石がないならばマス $i + 5 k$ に移動する．さもなくば転倒する．

なお操作は続けて行われ，中断することはできません．

高橋君が転倒することなくマス $0$ からマス $N$ に移動する方法が何通りあるか求めてください． 答えは非常に大きくなることがあるので，答えを $998244353$ で割った余りを出力してください．

制約

• $1 \leq N \leq 1.4 \times 10^5$
• $N$ は整数
• $S$ は o，x のみからなる長さ $N + 1$ の文字列
• $S_0 =$ o，$S_N =$ o

入力

入力は以下の形式で標準入力から与えられます．

出力

答えを $998244353$ で割った余りを出力してください．最後に改行してください．

サンプル

20
oxooxoooooooooooooxxo

1

最初の操作で $k = 1$ と選ぶと

• 現在位置はマス $0$ である．マス $0 + 2 \times 1 = 2$ は存在し，$S_2 =$ o よりそこに石はないのでマス $2$ に移動する．
• 現在位置はマス $2$ である．マス $2 + 3 \times 1 = 5$ は存在し，$S_5 =$ o よりそこに石はないのでマス $5$ に移動する．
• 現在位置はマス $5$ である．マス $5 + 5 \times 1 = 10$ は存在し，$S_{10} =$ o よりそこに石はないのでマス $10$ に移動する．

としてマス $10$ に移動でき，次の操作で $k = 1$ と選ぶと

• 現在位置はマス $10$ である．マス $10 + 2 \times 1 = 12$ は存在し，$S_{12} =$ o よりそこに石はないのでマス $12$ に移動する．
• 現在位置はマス $12$ である．マス $12 + 3 \times 1 = 15$ は存在し，$S_{15} =$ o よりそこに石はないのでマス $15$ に移動する．
• 現在位置はマス $15$ である．マス $15 + 5 \times 1 = 20$ は存在し，$S_{20} =$ o よりそこに石はないのでマス $20$ に移動する．

としてマス $N = 20$ に移動できます．

一方最初の操作で $k = 2$ と選ぶと

• 現在位置はマス $0$ である．マス $0 + 2 \times 2 = 4$ は存在するが，$S_4 =$ x よりそこに石があるので転倒する．

となり転倒してしまいます．

また最初の操作で $k = 10$ と選ぶと

• 現在位置はマス $0$ である．マス $0 + 2 \times 10 = 20$ は存在し，$S_{20} =$ o よりそこに石はないのでマス $20$ に移動する．
• 現在位置はマス $20$ である．マス $20 + 3 \times 10 = 50$ は存在しないので転倒する．

となり転倒してしまいます（操作は中断できません）．

転倒しない移動方法は冒頭で述べた $1$ 通りのみなので，$1$ を $998244353$ で割った余りである $1$ を出力してください．