信じられないほどかわいいペンギンのひなたちは、虫を食べるのが大好きです。ある日、母親は、いくつもの文字が書かれた長いひも状の虫を見つけました。母親は、この虫を切り分けてひなたちに食べさせることにしました。

ひなたちはなぜか International Collegiate Programming Contest が大好きで、ICPC らしい文字列が書かれた部分を食べたがっています。ここで、文字列が ICPC らしいとは、次の条件を満たすことをいいます。

• C、I、P のみからなります。

• この三文字のうち二文字は同じ回数（0 回でもかまいません）現れ、残りの一文字はそれより厳密に多く現れます。

例えば、ICPC と PPPPPP は ICPC らしいですが、PIC、PIPCCC、PIPE はそうではありません。

母親が見つけた虫に書かれた文字列が与えられます。母親は余りを無駄にすることなく、すべてに ICPC らしい文字列が書かれるよう、虫を一つ以上の部分にして与えたいと考えています。このように虫を準備する方法の数を数えてください。

入力

入力は、母親が見つけたひも状の虫に書かれた、C、I、P のみからなる文字列 $S$ を含む一行です。$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 の連結。