题目背景

保先生是个好司机，总是开车带学生们上山玩。但是保先生去年开了最后一趟车后，由于一些奇奇怪怪的原因转行了。半年间，再也没有从这条路上山的人了。

当VFleaKing 再次来到这座山玩的时候，发现已经没有往日的来来往往的游人了。算了，过去保先生还在的时候，来山上玩的人，也不全是来欣赏山上的风景的。

题目描述

如果机房马上要关门了，或者你急着要和MM约会，请直接跳到第六个自然段。

VFleaKing注意到了这条上山下山的土路，有些地方能欣赏到美景，有些地方则不能。把上山的道路每10cm分为一小段，则对于每一小段，用a表示能欣赏到美景，用b表示不能欣赏到美景，就能得到一个只含a,b的字符串s。当然由于下山和上山是一条路，所以下山的道路的字符串就是将上山的道路的字符串反过来。

设上山字符串长度为n，每个字符依次为$s_1, s_2 ,\cdots, s_n$。在上山和下山的路上，VFleaKing会选择某些小段查看旁边的景色，其他时间低头走路。即 VFleaKing 会选择k个小段$x_1, x_2 \cdots x_k$，且$k >0,1≤x_1<x_2<…<x_k≤n$,VFleaKing 上山和下山的过程中会在这些地方查看景色。

VFleaKing 希望，上山下山时看到的美景的情况相同。也就是说，VFleaKing 上山时是否看到了美景的情况是： $s_{x_1},s_{x_2},\cdots,s_{x_k}$ 记为字符序列 $T_1$，下山时是否看到了美景的情况是：$s_{x_k},s_{x_{k-1}},\cdots,s_{x_1}$ 记为字符序列 $T_2$。VFleaKing 希望 $T_1=T_2$。

VFleaKing 还希望，上山下山时查看景色的间隔相等。也就是说，上山时查看景色的间隔为：$x_2-x_1,x_3-x_2,x_k-x_{k-1}$，记为数列 $P_1$。下山时查看景色的间隔为：$x_k-x_{k-1},x_{k-1}-x_{k-2},…,x_2-x_1$，记为数列 $P_2$。VFleaKing 希望 $P_1=P_2$。

VFleaKing 觉得，如果第一次查看景色和最后一次查看景色这段时间里，没有一次低头看路他就会摔倒。也就是说，如果对于所有 $1\le i\le k$ 都有$x_i=x_1+i- 1$，VFleaKing 就会摔倒，VFleaKing不希望发生这样的情况。

就是要在一个只含 a、b 的字符串中选取一个子序列，使得:

1. 位置和字符都关于某条对称轴对称。
2. 不能是连续的一段。

以 $s = \texttt{"abaaaaabbabbabaa"}$ 为例。如果我们用符号 $[a_1, a_2,…,a_k]$ 表示一个序列，那么 $[1,4]$ 就是一个合法的序列 $x$，$[5,8,10,12,15]$ 也是，$[4,5,8,9,10,11,12,15,16]$ 也是。但是 $[1,2]$ 不满足 VFleaKing 第一个希望和第三个希望，所以不是。$[1,2,4]$ 不满足第二个希望，所以不是。$[9,10,11]$ 不满足第三个希望，所以不是。

输入格式

一行，一个只包含a,b两种字符的字符串

输出格式

一行，一个非负整数表示问题的答案

abaabaa

14

样例解释

14个方案分别是：

• [1,3],[1,4],[2,5],[1,6],[3,6],[4,6],[1,7],[3,7],[4,7]
• [1,4,7],[3,5,7]
• [1,3,4,6],[1,2,5,6],[3,4,6,7]

aaabbbaaa

44

aaaaaaaa

53

数据范围

• 其中10%的数据，字符串仅包含字母α或字母b
• 另有20%的数据，$n\le1000$
• 另有20%的数据，要么a的个数不超过10，要么b的个数不超过10
• 另有10%的数据，$n \le 10000$
• 对于100%的数据，$n \le 100000$

来源

• 2013湖北互测week1
• bzoj3160
• 信息学奥赛之数学一本通
• stong9070整理