믿을 수 없을 만큼 귀여운 아기 펭귄들은 벌레 먹는 것을 좋아한다. 어느 날 엄마 펭귄은 여러 글자가 적힌 길고 끈 모양의 벌레를 발견했다. 엄마는 이 벌레를 조각내어 아기들에게 먹이기로 했다.

아기 펭귄들은 어쩐지 International Collegiate Programming Contest를 좋아해서 ICPC스러운 문자열이 적힌 조각을 먹고 싶어 한다. 여기서 문자열이 ICPC스럽다는 것은 다음 조건을 만족한다는 뜻이다.

• C, I, P만으로 이루어져 있다.

• 이 세 문자 중 두 문자의 등장 횟수가 같고(0회일 수도 있다), 나머지 한 문자의 등장 횟수는 그보다 엄격히 크다.

예를 들어 ICPC와 PPPPPP는 ICPC스럽지만, PIC, PIPCCC, PIPE는 그렇지 않다.

엄마 펭귄이 찾은 벌레에 적힌 문자열이 주어진다. 엄마는 남는 부분을 버리지 않고, 모든 부분에 ICPC스러운 문자열이 적히도록 벌레를 하나 이상의 부분으로 나누어 주고 싶다. 이런 방식으로 벌레를 준비하는 방법의 수를 세어라.

입력

입력은 엄마 펭귄이 찾은 끈 모양 벌레에 적힌 문자열 $S$를 포함하는 한 줄이다. $S$는 C, I, P만으로 이루어져 있다. $S$의 길이는 $1$ 이상 $10^6$ 이하이다.

출력

문자열 $S$를 하나 이상의 ICPC스러운 문자열의 연결로 나타내는 방법의 수를 소수 $998\,244\,353=2^{23}\times7\times17+1$로 나눈 나머지를 한 줄에 출력한다.

예제

입력 1

ICPC

출력 1

2

입력 2

CCCIIIPPP

출력 2

69

입력 3

PICCICCIPPI

출력 3

24

첫 번째 예제에서 문자열 ICPC는 다음 두 가지 방법으로 나타낼 수 있다.

• 하나의 ICPC스러운 문자열 ICPC.

• 네 개의 ICPC스러운 문자열 I, C, P, C의 연결.