题目描述

The Incredibly Cute Penguin Chicks love to eat worms. One day, their mother found a long string-shaped worm with a number of letters on it. She decided to cut this worm into pieces and feed the chicks.

:::align{center} :::

The chicks somehow love International Collegiate Programming Contest and want to eat pieces with ICPC-ish character strings on them. Here, a string is ICPC-ish if the following conditions hold.

• It consists of only C’s, I’s, and P’s.
• Two of these three characters appear the same number of times (possibly zero times) in the string and the remaining character appears strictly more times.

For example, ICPC and PPPPPP are ICPC-ish, but PIC, PIPCCC and PIPE are not.

You are given the string on the worm the mother found. The mother wants to provide one or more parts of the worm all with an ICPC-ish string, without wasting remains. Your task is to count the number of ways the worm can be prepared in such a manner.

输入格式

The input is a single line containing a character string $S$ consisting of only C’s, I’s, and P’s, which is on the string-shaped worm the mother penguin found. The length of $S$ is between $1$ and $10^6$, inclusive.

输出格式

Print in a line the number of ways to represent the string $S$ as a concatenation of one or more ICPC-ish strings modulo a prime number $998244353 = 2^{23} \times 7 \times 17 + 1$.

ICPC

2

CCCIIIPPP

69

PICCICCIPPI

24

提示

In the first sample, the string “ICPC” can be represented in the following two ways.

• A single ICPC-ish string, “ICPC”.
• Concatenation of four ICPC-ish strings, “I”, “C”, “P”, and “C”.