問題文

シカのAtCoDeerくんは、たかいたい(高い鯛)が大好きです。ところでこの文字列は空でない文字列$A,B,C$を使って$ABCAC$(文字列を連結したもの)と書けます($A$="た",$B$="か",$C$="い")。そこで、AtCoDeerくんは文字列$S$に対して、このような分割が何通りあるか求めることにしました。

制約

• $5≦|S|≦200000$
• $S$ は英小文字のみからなる。

入力

入力は以下の形式で標準入力から与えられる。

$S$

部分点

この問題には部分点が設定されている。

• $|S|≦2000$を満たすデータセットに正解した場合、部分点として$20$点が与えられる。

出力

$S=ABCAC$と書けるような非空文字列の組${A,B,C}$が何通りあるか出力せよ。

入力例1

takaitai

出力例1

2

$A="ta",B="ka",C="i"$ と,$A="t",B="ak",C="ai"$ の2通りがある。

入力例2

aaaaaaaaaa

出力例2

6

以下の6通りである。

• $A="aaa",B="aa",C="a"$
• $A="aa",B="aa",C="aa"$
• $A="aa",B="aaaa",C="a"$
• $A="a",B="aa",C="aaa"$
• $A="a",B="aaaa",C="aa"$
• $A="a",B="aaaaaa",C="a"$

入力例3

abcabc

出力例3

0

$A,B,C$として空文字列はとれないことに注意せよ。