AT_toyota2023spring_final_f Forbidden Pattern
题目描述
给定一个由 `A` 和 `B` 组成，长度为 $N$ 的字符串 $S$。
你可以重复进行如下操作 $0$ 次或多次：
- 从 $S$ 中选择连续的 $2$ 个字符，这两个字符不是 `AB`，将其删除。然后，将剩下的左右（可能为空的）字符串连接起来，作为新的 $S$。
请你求出，经过若干次操作后，可能得到的不同字符串有多少种。答案对 $998244353$ 取模。
输入格式
输入通过标准输入给出，格式如下：
> $N$ $S$
输出格式
请输出答案。
说明/提示
## 限制条件
- $2 \leq N \leq 10^6$
- $S$ 是由 `A` 和 `B` 组成的长度为 $N$ 的字符串
## 样例解释 1
经过操作后，可能得到的字符串有 `A`、`B`、`BBA` 共 $3$ 种。
## 样例解释 2
经过操作后，可能得到的字符串有 `A`、`ABA`、`ABABA` 共 $3$ 种。
由 ChatGPT 4.1 翻译