配点 : $1300$ 点

問題文

A, B からなる長さ $N$ の文字列 $S$ が与えられます．

あなたは，以下の操作を $0$ 回以上繰り返すことができます．

• $S$ 中の連続する $2$ 文字であって，AB でないものを選び，消す． その後，残った左右の（空かもしれない）文字列を連結し，これを新たに $S$ とする．

操作後の $S$ としてあり得る文字列が何通りあるかを $998244353$ で割ったあまりを求めてください．

制約

• $2 \leq N \leq 10^6$
• $S$ は A, B からなる長さ $N$ の文字列である

入力

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

$N$

$S$

出力

答えを出力せよ．

3
BBA

3

操作後の $S$ としてありうる文字列は，A, B, BBA の $3$ 通りです．

5
ABABA

3

操作後の $S$ としてありうる文字列は，A, ABA, ABABA の $3$ 通りです．

9
BABBAAAAB

14

48
AABABBBAABAAABAAABBBAAABBBAABAABBABAABBAAAAABBBB

3073910