Balph 正在学习玩一款名为 Buma 的游戏。在这个游戏中,他得到了一排彩球。他必须选择一个新球的颜色以及插入它的位置(两个球之间,或所有球的左侧,或所有球的右侧)。
当球被插入时,会重复发生以下情况:如果相同颜色的球的某些部分由于先前的动作而变长并且其长度至少达到$$$3$$$,则该部分的所有球都将被消除。
例如,考虑一排球“AAABBBWWBB”。假设巴尔夫选择了一个颜色为“W”的球,并在第六个球之后将其插入的位置,即。 e.在两个“W”的左侧。 Balph 插入该球后,颜色为“W”的球被消除,因为该段变得更长,现在长度为 $$$3$$$,因此该行变为“AAABBBBB”。颜色“B”的球现在被消除,因为颜色“B”的球段变得更长并且现在长度为$$$5$$$。因此,该行变为“AAA”。然而,现在没有一个球被消除,因为没有拉长的部分。
帮助 Balph 计算选择新球的颜色和插入位置以消除所有球的可能方法的数量。
输入
唯一一行包含一个由大写英文字母组成的非空字符串,长度最多为 $$$3 \cdot 10^5$$$。每个字母代表一个具有相应颜色的球。
输出
输出选择新球的颜色和位置的方法数,以消除所有球。
示例
输入 #1
BBWWBB
输出 #1
3
输入 #2
BWWB
输出 #2
0
输入 #3
BBWBB
输出 #3
0
输入#4
OOOWWW
输出#4
0
输入 #5
WWWOOOOOOWWW
输出 #5
7