問題文

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

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

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

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

制約

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

入力例 1

3
BBA

出力例 1

3

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

入力例 2

5
ABABA

出力例 2

3

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

入力例 3

9
BABBAAAAB

出力例 3

14

入力例 4

48
AABABBBAABAAABAAABBBAAABBBAABAABBABAABBAAAAABBBB

出力例 4

3073910