問題文

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

制約

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

入力例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として空文字列はとれないことに注意せよ。