#3350. 相似回文串

内存限制:128 MiB 时间限制:10 Sec

题目描述

记S(i,j)为字符串S的第i个字母到第j个字母组成的子串。
给出一个长度为n由小写英文字母组成的字符串A。
若字符串B也由小写英文字母组成,长度为n,且对于任意1<=i<j<=n有:若A(i,j)是回文串,B(i,j)也是回文串;若A(i,j)不是回文串,B(i,j)也不是回文串。那么我们称B与A是ayq相似的。
求有多少个字符串与A ayq相似?输出答案对1000000007取模的余数。
 

输入格式

输入1行一个字符串A
 

输出格式

 
输出一行一个数表示所求答案
 

样例

样例输入


			
abcba

样例输出


			
15600

数据范围与提示

对于100%的数据,n<=1000000