万径人踪灭

题目背景

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

题目描述

如果机房马上要关门了,或者你急着要走,请直接跳到第六个自然段。 VFleaKing 注意到了这条上山下山的土路,有些地方能欣赏到美景,有些地方则不能。把上山的道路每 $10$ cm 分为一小段,则对于每一小段,用 `a` 表示能欣赏到美景,用 `b` 表示不能欣赏到美景,就能得到一个只含 `a`、`b` 的字符串 $s$。当然由于下山和上山是一条路,所以下山的道路的字符串就是将上山的道路的字符串反过来。 设上山字符串长度为 $n$,每个字符依次为 $s_1, s_2 .…, s_n$。在上山和下山的路上,VFleaKing 会选择某些小段查看旁边的景色,其他时间低头走路。即 VFleaKing 会选择 $k$ 个小段 $x_1, x_2 …x_k$,且 $k >0$,$1\le x_1<x_2<…<x_k\le n$,VFleaKing 上山和下山的过程中会在这些地方查看景色。 ![](https://cdn.luogu.com.cn/upload/image_hosting/t9qpo3f9.png) 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]$ 不满足第三个希望,所以不是。 ![](https://cdn.luogu.com.cn/upload/image_hosting/6849dqla.png) 给你字符串 $s$,现在 VFleaKing 想知道,有多少个合法的 $x$。答案可能很大,VFleaKing 想知道对 $1000000007$ 取模的值。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

abaabaa

输出样例 #1

14

输入样例 #2

aaabbbaaa

输出样例 #2

44

输入样例 #3

aaaaaaaa

输出样例 #3

53

说明

## 样例解释 ### 样例解释 1 $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]$。 ### 样例解释 2 我已经想到了一个绝妙的解释,可惜方案太多,写不下了。 ### 样例解释 3 我已经想到了一个绝妙的解释,可惜方案太多,写不下了。 ## 数据范围 - 其中 $10\%$ 的数据,字符串仅包含字母 `a` 或字母 `b`。 - 另有 $20\%$ 的数据,$n\le 1000$。 - 另有 $20\%$ 的数据,要么 `a` 的个数不超过 $10$,要么 `a` 的个数不超过 $10$。 - 另有 $10\%$ 的数据,$n\le 10000$。 - 对于 $100\%$ 的数据,$n \le 100000$。 ## 来源 - 2013 湖北互测 week1 - bzoj 3160 - 信息学奥赛之数学一本通 - stong9070 整理