C - ABCAC 解説 /

実行時間制限: 5 sec / メモリ制限: 256 MB

問題文

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