题目描述

巴尔夫在玩一个游戏。在这个游戏中，他将得到一串彩色的球。他需要选择一个颜色的球并在这串球中选择任意一个位置插入这个球。

当一个球被插入后，以下情况会重复发生：如果连续一串相同颜色的球由于先前的操作而变长，并且其长度大于或等于$3$，则这一串相同颜色的球都将被消除。

例如，一串球“AAABBBWWBB”。假如巴尔夫选择了一个颜色为‘W’的球，并将其插入到第$6$个位置（即‘B’和‘W’之间），此时颜色为‘W’的球将被消除，因为该操作使得此段变长且长度为$3$。现在，这串球为“AAABBBBB”。颜色为‘B’的球现在被消除了，因为颜色为‘B’的球段变长了，并且长度为$5$。剩下的球为“AAA”，由于没有任何操作使得颜色为‘A’的球段变长，所以无法再次进行消除。

巴尔夫想知道，如果给你任意一串球，有多少种插入的方式能使得所有的球都能被消除？

输入格式

一行字符串，长度不超过300000

输出格式

一个整数，表示能使得所有的球都能被消除的方案总数

样例

BBWWBB

3

BWWB

0

BBWBB

0

OOOWWW

0

WWWOOOOOOWWW

7