题目描述

给定一个由 A 和 B 组成，长度为 $N$ 的字符串 $S$。

你可以重复进行如下操作 $0$ 次或多次：

• 从 $S$ 中选择连续的 $2$ 个字符，这两个字符不是 AB，将其删除。然后，将剩下的左右（可能为空的）字符串连接起来，作为新的 $S$。

请你求出，经过若干次操作后，可能得到的不同字符串有多少种。答案对 $998244353$ 取模。

输入格式

输入通过标准输入给出，格式如下：

$N$ $S$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
BBA

输出 #1

3

输入输出样例 #2

输入 #2

5
ABABA

输出 #2

3

输入输出样例 #3

输入 #3

9
BABBAAAAB

输出 #3

14

输入输出样例 #4

输入 #4

48
AABABBBAABAAABAAABBBAAABBBAABAABBABAABBAAAAABBBB

输出 #4

3073910

说明/提示

限制条件

• $2 \leq N \leq 10^6$
• $S$ 是由 A 和 B 组成的长度为 $N$ 的字符串

样例解释 1

经过操作后，可能得到的字符串有 A、B、BBA 共 $3$ 种。

样例解释 2

经过操作后，可能得到的字符串有 A、ABA、ABABA 共 $3$ 种。

由 ChatGPT 4.1 翻译