TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2895
  • 题目
  • P2895万径人踪灭
    限制 : 时间限制 : 10000 MS   空间限制 : 265536 KB
    问题描述

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


    题目描述
    如果机房马上要关门了,或者你急着要和MM 约会,请直接跳到第六个自然段。
    VFleaKing注意到了这条上山下山的土路,有些地方能欣赏到美景,有些地方则不能。把上山的道路每10cm分为一小段,则对于每一小段,用a 表示能欣赏到美景,用b表示不能欣赏到美景,就能得到一个只含a,b的字符串s。当然由于下山和上山是一条路,所以下山的道路的字符串就是将上山的道路的字符串反过来。设上山字符串长度为n,每个字符依次为s1,s2,...,sn。在上山和下山的路上,VFleaKing会选择某些小段查看旁边的景色,其他时间低头走路。即VFleaKing会选择k个小段x1,x2,...,xk且k>=1,1<=x1<x2<...<xk<=n,VFleaKing上山和下山的过程中会在这些地方查看景色。

    VFleaKing 希望,上山下山时看到的美景的情况相同。也就是说,VFleaKing 上山时是否看到了美景的情况是:sx1,sx2,...,sxk,记为字符序列T1,下山时是否看到了美景的情况是:sxk,sxk-1,...,sx1,记为字符序列T2。VFleaKing希望T1=T2。
    VFleaKing还希望,上山下山时查看景色的间隔相等。也就是说,上山时查看景色的间隔为:x2-x1,x3-x2,...,xk-xk-1,记为数列P1。下山时查看景色的间隔为:xk-xk-1,xk-1-xk-2,...,x2-xk-1,记为数列P2。VFleaKing希望P1=P2。
    VFleaKing觉得,如果第一次查看景色和最后一次查看景色这段时间里,没有一次低头看路他就会摔倒。也就是说,如果对于所有1<=i<=k 都有xi=x1+i-1,VFleaKing就会摔倒,VFleaKing 不希望发生这样的情况。
    就是要在一个只含a,b的字符串中选取一个子序列,使得:
    1. 位置和字符都关于某条对称轴对称。
    2. 不能是连续的一段。
    以s=“abaaaaabbabbabaa”为例。如果我们用符号[a1,a2,...,ak]表示一个序列,那么[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]不满足第三个希望,所以不是。

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

    输入格式

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

    输出格式

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

    样例输入

    样例输入1:
    abaabaa

    样例输入2:
    aaabbbaaa

    样例输入3:
    aaaaaaaa

    样例输出

    样例输出1:
    14

    样例输出2:
    44

    样例输出3:
    53

    提示

    样例解释:
    第一组: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<=1000。
    另有20%的数据,要么a的个数不超过10,要么b的个数不超过10。
    另有10%的数据,n<=10000。
    对于100%的数据,n<=100000。


    来源  感谢nodgd搬运自ContestHunter 【2013湖北省队互测week1】