通过这一道题目希望大家能够知道：我们归根结底还是一个正经算法竞赛。

本题来源于《中国式家长》中的一个小游戏。

游戏开始时会生成一个长度为 $n$ 的宝石序列，每个宝石按照从左到右的顺序被标号成 $1$ 到 $n$。每个宝石有类型和能量两种属性，宝石的类型有四种，分别用字母ABCD表示，在初始时每个宝石的能量都是 $1$。同时保证初始时不存在连续的三个相同类型的宝石。

蒜斜可以进行若干轮操作，每轮操作的流程如下：

1. 选择结束游戏，当只剩下一个宝石的时候，蒜斜必须结束游戏。
2. 选择并删除某一个当前还存在的宝石，删除后右侧的宝石会自动向左补齐。
3. 令 $i$ 为当前最小的下标满足从左到右第 $i,i+1,i+2$ 个宝石的类型和能量都相同。如果这样的 $i$ 不存在，则这一轮结束，开始下一轮。否则这三个宝石会被移出游戏，同时在原来第 $i$ 个宝石的位置会出现一个类型和原来相同，能量比原来大 $1$ 的宝石。接着右侧的宝石会向左补齐，游戏回到这一步的开始，并继续从左到右寻找连续三个相同的宝石。

我们用 $A(x)$ 表示类型为 $A$ 能量为 $x$ 的宝石，下面是两个例子：

1. 如果宝石序列是 A(1)A(1)B(1)A(1)A(1)，那么在删除 B(1) 之后，结果序列为A(2)A(1)。
2. 如果宝石序列是 A(3)A(3)A(2)A(2)A(1)A(1)B(1)A(1)，那么在删除 B(1) 之后，结果序列为 A(4)。

蒜斜是一个全收集爱好者。她发现每一次开始这个小游戏，初始的宝石的数量、顺序和颜色都是完全相同的。而游戏中有一个传说级成就：合成出所有可能的结束状态。

在开始刷成就之前，蒜斜想让你帮她计算一下，一共有多少种不同的结束状态。

两个结束状态是不同的当且仅当剩下宝石的数量不同，或者存在一个下标 $i$ 满足两个状态中从左到右第 $i$ 个小球的类型或者能量不同。

输入格式

第一行一个整数 $n(1\le n\le {10}^6)$ 表示宝石序列的长度。

第二行一个长度为 $n$ 的由 ABCD 组成的字符串，表示初始的宝石序列。保证该序列中，不存在连续的三个相同的字符。

输出格式

输出一行一个整数，表示可能的结束状态个数。答案可能很大，对 $998244353$ 取模后输出。

样例输入一

input

5
AABAA

output

13

explanation

没有删除 B(1) 的情况（共 9 种）：A(1)A(1)B(1)A(1)A(1), A(1)A(1)B(1)A(1), A(1)A(1)B(1), A(1)B(1)A(1)A(1), A(1)B(1)A(1), A(1)B(1), B(1)A(1)A(1), B(1)A(1), B(1)。

删除了 B(1) 的情况（共 4 种）：A(2)A(1), A(2), A(1)A(1), A(1)。

因此一共有 13 种可能的结束状态。

样例输入二

input

16
ABCDABCDABCDABCD

output

42775

样例输入三

input

16
DAABBAACCBBAACCD

output

6314

限制与约定

Small Task: 初始序列相邻球颜色不同。

Large Task: 无特殊限制。

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载