题目描述

为了备战即将到来的 ICPC，你开始研究字符串 ICPC 的性质。

首先定义“好字符串”。对一个字符串，可以执行如下操作：

• 选择一处作为连续子串出现的 ICPC，将这四个字符替换为一个字符 C。

如果一个字符串经过零次或多次上述操作后能够变为 ICPC，则称它为好字符串。

例如：

• ICPC、IICPCPC、ICPICPICPC 是好字符串；
• C、ICICPPC、JAG 不是好字符串。

给定一个长度为 $n$ 的字符串 $s$，求 $s$ 的所有子序列中，有多少个是好字符串。

更准确地说，需要计算满足以下条件的整数集合 $P$ 的数量：

• $P$ 中的每个元素都是 $1$ 到 $n$ 之间的整数；
• 设 $P=\{p_1,p_2,\ldots,p_m\}$，删除 $s$ 的第 $p_1,p_2,\ldots,p_m$ 个字符后，剩余字符按原顺序组成的字符串是好字符串。

不同的删除位置集合视为不同方案，即使它们最终得到的字符串内容相同。

答案可能很大，请输出其对 $998244353$ 取模后的结果。

输入格式

输入包含多组测试数据。

每组测试数据格式如下：

n
s

• 第一行输入一个整数 $n$，表示字符串长度；
• 第二行输入一个由英文大写字母组成的长度为 $n$ 的字符串 $s$。

输入以仅包含一个整数 0 的行结束。

输出格式

对于每组测试数据，输出一行一个整数，表示满足条件的删除位置集合数量对 $998244353$ 取模后的结果。

数据范围

所有测试数据中 $n$ 的总和不超过 $7000$。

样例

4
ICPC
12
ICPCICPCICPC
3
JAG
20
ICWCPPCIWPCICWCICCCP
0

1
40
0
46