背景

    保先生是个好司机,总是开车带学生们上山玩。但是去年保先生去年开了最后一趟车后,由于一些奇奇怪怪的原因转行了。半年间,再也没有从这条路上山的人了。
    当VFleaKing再次来到这座山玩的时候,发现已经没有往日的来来往往的游人了。
    算了,过去保先生还在的时候,来山上玩的人,也不全是来欣赏山上的风景的。

描述

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

    VFleaKing注意到了这条上山下山的土路,有些地方能欣赏到美景,有些地方则不能。把上山的道路每10cm分为一小段,则对于每一小段,用a表示能欣赏到美景,用b表示不能欣赏到美景,就能得到一个只含a,b的字符串s。当然由于下山和上山是一条路,所以下山的道路的字符串就是将上山的道路的字符串反过来。设上山字符串长度为n,每个字符依次为s_1, s_2, ..., s_n。在上山和下山的路上,VFleaKing会选择某些小段查看旁边的景色,其他时间低头走路。即VFleaKing会选择k个小段x_1, x_2, \cdots, x_k,且k > 0, 1 \leq x_1 < x_2 < \cdots < x_k \leq n,VFleaKing上山和下山的过程中会在这些地方查看景色。
    VFleaKing希望,上山下山时看到的美景的情况相同。也就是说,VFleaKing上山时是否看到了美景的情况是:s_{x_1}, s_{x_2}, \cdots, s_{x_n},记为字符序列T_1,下山时是否看到了美景的情况是:s_{x_n}, s_{x_{n - 1}}, \cdots, s_{x_1},记为字符序列T_2。VFleaKing希望T_1 = T_2
    VFleaKing还希望,上山下山时查看景色的间隔相等。也就是说,上山时查看景色的间隔为:x_2 - x_1, x_3 - x_2, \cdots, x_n - x_{n - 1},记为数列P_1。下山时查看景色的间隔为:x_n - x_{n - 1}, x_{n - 1} - x_{n - 2}, \cdots, x_2 - x_1,记为数列P_2。VFleaKing希望P_1 = P_2
    VFleaKing觉得,如果第一次查看景色和最后一次查看景色这段时间里,没有一次低头看路他就会摔倒。也就是说,如果对于所有1 \leq i \leq k都有x_i = x_1 + i - 1,VFleaKing就会摔倒,VFleaKing不希望发生这样的情况。

   就是要在字符串中选取一个子序列,使得:(请参照以上描述理解)
  1. 位置和字符都关于某条对称轴对称。
  2. 不能是连续的一段。
    以为例。如果我们用符号[a_1, a_2, ..., a_k]表示一个序列,那么[1, 4]就是一个合法的序列x[8, 10, 12]也是。但是[1, 2]不满足VFleaKing第一个希望和第三个希望,所以不是。[1, 2, 4]不满足第二个希望,所以不是。[9, 10, 11]不满足第三个希望,所以不是。(如果不能理解请下载pdf,有配图“超萌超好懂”。)

    给你字符串s,现在VFleaKing想知道,有多少个合法的x。答案可能很大,VFleaKing想知道结果对1000000007取模的值。

输入格式

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

输出格式

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

样例输入

abaabaa
更多样例数据请参考pdf

样例输出

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]

数据范围与约定

其中10%的数据,字符串仅包含字母a或字母b。
另有20%的数据,n \leq 1000
另有20%的数据,要么a的个数不超过10,要么b的个数不超过10。
另有10%的数据,n \leq 10000
对于100%的数据,n \leq 100000

来源

VFleaKing