← 返回题目列表

AtCoder · toyota2023spring_final_f

F. 禁止图案

中文机器翻译题面 查看原题

配点 : 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