Niesamowicie urocze pisklęta pingwinów uwielbiają jeść robaki. Pewnego dnia ich matka znalazła długiego robaka w kształcie sznurka, na którym znajdowały się litery. Postanowiła pokroić go na kawałki i nakarmić pisklęta.
Pisklęta z jakiegoś powodu uwielbiają International Collegiate Programming Contest i chcą jeść kawałki z napisami w stylu ICPC. Napis jest w stylu ICPC, jeśli spełnia następujące warunki:
Składa się wyłącznie z liter
C,IiP.Dwie z tych trzech liter występują w napisie tyle samo razy (być może zero razy), a pozostała litera występuje ściśle więcej razy.
Na przykład ICPC i PPPPPP są w stylu ICPC, ale PIC, PIPCCC i PIPE nie są.
Dany jest napis na robaku znalezionym przez matkę. Matka chce podać co najmniej jeden kawałek robaka, każdy z napisem w stylu ICPC, nie marnując żadnych resztek. Twoim zadaniem jest policzyć sposoby przygotowania robaka w ten sposób.
Wejście
Wejście składa się z jednego wiersza zawierającego napis $S$ złożony wyłącznie z liter C, I i P, znajdujący się na robaku w kształcie sznurka znalezionym przez matkę pingwinów. Długość $S$ wynosi od $1$ do $10^6$ włącznie.
Wyjście
Wypisz w jednym wierszu liczbę sposobów przedstawienia napisu $S$ jako konkatenacji co najmniej jednego napisu w stylu ICPC, modulo liczba pierwsza $998\,244\,353=2^{23}\times7\times17+1$.
Przykład
Wejście 1
ICPC
Wyjście 1
2
Wejście 2
CCCIIIPPP
Wyjście 2
69
Wejście 3
PICCICCIPPI
Wyjście 3
24
W pierwszym przykładzie napis ICPC można przedstawić na dwa sposoby:
Jeden napis w stylu ICPC:
ICPC.Konkatenacja czterech napisów w stylu ICPC:
I,C,PiC.