这些可爱的企鹅宝宝喜欢吃虫子。有一天，它们的妈妈找到了一条长长的带状虫子，上面写着一些字母。她决定把这条虫子切成若干段，喂给企鹅宝宝吃。

企鹅宝宝们非常喜欢国际大学生程序设计竞赛（International Collegiate Programming Contest），并希望吃到上面写着“ICPC-ish”字符串的虫子段。如果一个字符串满足以下条件，则称其为 ICPC-ish：

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

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

给定妈妈找到的虫子上的字符串。妈妈希望将虫子切成一个或多个部分，且每一部分都是 ICPC-ish 字符串，同时不浪费任何剩余部分。你的任务是计算有多少种方法可以这样准备虫子。

输入格式

输入为一行，包含一个仅由 'C'、'I' 和 'P' 组成的字符串 $S$，即企鹅妈妈找到的虫子上的字符串。$S$ 的长度在 $1$ 到 $10^6$ 之间（含边界）。

输出格式

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

样例

样例输入 1

ICPC

样例输出 1

2

样例输入 2

CCCIIIPPP

样例输出 2

69

样例输入 3

PICCICCIPPI

样例输出 3

24

说明

在第一个样例中，字符串 “ICPC” 可以通过以下两种方式表示：

• 一个单独的 ICPC-ish 字符串，“ICPC”。
• 四个 ICPC-ish 字符串的连接，“I”、“C”、“P” 和 “C”。