配点 : 1300 点
問題文
A, B 组成
给出了 N 字符串
给出了 S 。
您可以执行以下操作: 可以重复超过 0 次。
- S 持续 2 字符,
AB把否选择某些内容并将其删除。 之后,连接剩余的左右(可能为空)字符串并创建一个新的 S 。
操作后 S 有多少种可能的字符串? 除以 998244353 后求余数。 是一个字符串
制約
- 2 \leq N \leq 10^6
- S 表示
A,B组成 给出了 N 是一串
入力
输入是按以下格式从标准输入给出的。
N S
出力
输出答案。
入力例 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