#214931. [ICPC 2022 Yokohama R] Incredibly Cute Penguin Chicks

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 consisting of only C’s, I’s, and P’s, which is on the string-shaped worm the mother penguin found. The length of is between and , inclusive.

Print in a line the number of ways to represent the string as a concatenation of one or more ICPC-ish strings modulo a prime number .

样例输入 1

ICPC

样例输出 1

2

样例输入 2

CCCIIIPPP

样例输出 2

69

样例输入 3

PICCICCIPPI

样例输出 3

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”.