Description

极其可爱的企鹅宝宝们 喜欢吃蠕虫。一天，它们的妈妈发现了一条长条状的蠕虫，上面有一些字母。她决定将这条蠕虫切成几段喂给宝宝们。

:::align{center} :::

企鹅宝宝们不知为何喜欢 国际大学生程序设计竞赛，并希望吃到带有 ICPC-ish 字符串的片段。这里，一个字符串是 ICPC-ish 的，如果满足以下条件：

• 它仅由字母 C、I 和 P 组成。
• 这三个字符中有两个在字符串中出现的次数相同（可能为零次），而剩余的字符出现次数严格更多。

例如，ICPC 和 PPPPPP 是 ICPC-ish 的，但 PIC、PIPCCC 和 PIPE 不是。

你被给予企鹅妈妈发现的蠕虫上的字符串。妈妈希望提供蠕虫的一个或多个部分，每部分都带有 ICPC-ish 字符串，且不浪费剩余部分。你的任务是计算可以以这种方式准备蠕虫的方法数量。

Input Format

输入是一行，包含一个仅由字母 C、I 和 P 组成的字符串 $S$，即企鹅妈妈发现的长条状蠕虫上的字符串。$S$ 的长度在 $1$ 到 $10^6$ 之间（含）。

Output Format

在一行中输出将字符串 $S$ 表示为一个或多个 ICPC-ish 字符串连接的方法数量，结果对质数 $998244353 = 2^{23} \times 7 \times 17 + 1$ 取模。

ICPC

2

CCCIIIPPP

69

PICCICCIPPI

24

Hint

在第一个样例中，字符串 "ICPC" 可以用以下两种方式表示：

• 一个单独的 ICPC-ish 字符串："ICPC"。
• 四个 ICPC-ish 字符串的连接："I"、"C"、"P"、"C"。