A los polluelos de pingüino increíblemente adorables les encanta comer gusanos. Un día, su madre encontró un gusano largo con forma de cuerda y con varias letras sobre él. Decidió cortarlo en trozos y alimentar a los polluelos.

Por algún motivo, a los polluelos les encanta International Collegiate Programming Contest y quieren comer trozos con cadenas de estilo ICPC. Aquí, una cadena es de estilo ICPC si cumple las siguientes condiciones:

• Está formada únicamente por C, I y P.

• Dos de estos tres caracteres aparecen el mismo número de veces en la cadena (posiblemente cero veces), y el carácter restante aparece estrictamente más veces.

Por ejemplo, ICPC y PPPPPP son de estilo ICPC, pero PIC, PIPCCC y PIPE no lo son.

Se te da la cadena del gusano que encontró la madre. La madre quiere proporcionar uno o más trozos del gusano, todos con una cadena de estilo ICPC, sin desperdiciar restos. Tu tarea es contar el número de maneras de preparar el gusano de esta forma.

Entrada

La entrada consta de una sola línea con una cadena $S$ formada únicamente por C, I y P, que está sobre el gusano con forma de cuerda que encontró la madre pingüino. La longitud de $S$ está entre $1$ y $10^6$, ambos inclusive.

Salida

Imprime en una línea el número de maneras de representar la cadena $S$ como concatenación de una o más cadenas de estilo ICPC, módulo el número primo $998\,244\,353=2^{23}\times7\times17+1$.

Ejemplos

Entrada 1

ICPC

Salida 1

2

Entrada 2

CCCIIIPPP

Salida 2

69

Entrada 3

PICCICCIPPI

Salida 3

24

En el primer ejemplo, la cadena ICPC puede representarse de las siguientes dos maneras:

• Una única cadena de estilo ICPC, ICPC.

• La concatenación de cuatro cadenas de estilo ICPC, I, C, P y C.