问题文

AtCoDeer是一只喜欢高贵鲷鱼的鹿。事实上，可以用非空字符串$A,B,C$表示连结字符串$ABCAC$（$A$="た", $B$="か", $C$="い"）。因此，AtCoDeer决定对字符串$S$求解有多少种这样的分割方式。

约束条件

• $5≦|S|≦200000$
• $S$ 只包含小写英文字母。

输入

输入从标准输入中获取，具有以下格式。

$S$

部分点

本问题设有部分点。

• 如果能够正确解决满足$|S|≦2000$的数据集，则可得到20分。

输出

输出有多少种非空字符串的组合${A,B,C}$使得$S=ABCAC$。

示例输入1

takaitai

示例输出1

2

存在两种情况：$A="ta",B="ka",C="i"$ 和 $A="t",B="ak",C="ai"$。

示例输入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$不能是空字符串。