记录编号	162130	评测结果	AAAAAAAAAAAAAAAAAAAAAA
题目名称	[ONTAK 2010] 回文等价	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	2.393 s
提交时间	2015-05-14 09:56:24	内存使用	80.42 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <set>
#include <vector>

#define N 2000010
#define A 26
#define LL long long
#define mod 1000000007LL

using namespace std;

void file(){
	//freopen("test.in","r",stdin);
	freopen("palindromic.in","r",stdin);
	freopen("palindromic.out","w",stdout);
}

set<int> D[N];
vector<int> G[N];
int ansv,fa[N];

int find(int x){
	if(fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}

void unionn(int x,int y){
	int r1=find(x);
	int r2=find(y);
	if(r1!=r2) fa[r2]=r1;
}

namespace PT{
	struct node{
		node *ch[A],*fail;
		int len;
	}*root[2],*now;
	
	int n,tot_n;
	char S[N];
	
	node* get_node(int x){
		node* tmp=new node();
		tmp->len=x;
		return tmp;
	}
	
	void init(){
		n=0;
		root[0]=get_node(-1);
		root[1]=get_node(0);
		root[1]->fail=root[0]->fail=root[0];
		now=root[1];
		S[n++]=-1;
	}
	
	node* get(node* p){
		while(S[n-p->len-2]!=S[n-1]){
			int tmp=n-p->len-2;
			if(tmp>0) G[n-1].push_back(tmp);
			p=p->fail;
		}
		unionn(n-p->len-2,n-1);
		node* tmp=p;
		return p;
	}
	
	int addin(char c){
		int t=c-'a'; S[n++]=c;
		node* p=get(now);
		if(!p->ch[t]){
			now=get_node(p->len+2);
			if(now->len==1) now->fail=root[1];
			else now->fail=get(p->fail)->ch[t];
			p->ch[t]=now;
		}
		now=p->ch[t];
		return now->len;
	}
};

int n;
char S[N];

int main(){
	file();
	scanf("%s",S);
	n=strlen(S);
	PT::init();
	for(int i=0;i<=n;i++) fa[i]=i;
	for(int i=0;i<n;i++) PT::addin(S[i]);
	LL ans=1;
	for(int x=1;x<=n;x++){
		int t=find(x);
		for(int i=G[x].size()-1;~i;i--){
			int p=find(G[x][i]);
			if(p<t) D[t].insert(p);
		}
	}
	for(int i=1;i<=n;i++){
		if(find(i)!=i) continue;
		ans=ans*(26-D[i].size())%mod;
	}
	printf("%lld\n",ans);
	return 0;
}