Description：

给定一个串，把串分为偶数段，假设分为了 $s_1,s_2,s_3\dots s_k$ ，求满足 $s_1=s_k,s_2=s_{k-1}\dots$ 的方案数。

$1\leqslant n\leqslant 10^6$

Solution：

直接做是肯定没法做的，这个时候有一个非常妙的转化：

构造串 $S'=S[1]S[n]S[2]S[n-1]\cdots$ ，这个时候我们发现每一个原来的一对在这个串里是一个偶数长度的回文子串，于是构建出回文树，然后在上面 $dp$ 一下，每次从 $fail[i],fail[fail[i]],\dots$ 那里转移过来，只有偶数的时候转移。

但是这样的复杂度是错的，因为可能会一直跳 $fail$ ，这个时候有一个重要性质，就是一个串的若干回文后缀如果长度 $>len/2$ ，那么他们等差，如果把这些看成一组，那么长度每次 $/2$ ，那么我们可以把这些等差的组放在一起转移，复杂度就是 $O(n\log n)$ 的了。

代码是抄的yyb的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 1000100

#define MOD 1000000007

int n;

char c[MAXN],S[MAXN];

struct node

{

	int tr[26];

	int len,fail;

}s[MAXN];

int ptr,last;

int newnode(int l){s[ptr].len = l;return ptr++;}

void init()

{

	ptr = last = 0;

	newnode(0);

	newnode(-1);

	s[0].fail = 1;

	return;

}

int getfail(int i,int p)

{

	while(c[i - s[p].len - 1] != c[i])p = s[p].fail;

	return p;

}

int diff[MAXN],anc[MAXN];

void extend(int i,int k)

{

	int p = getfail(i,last);

	if(s[p].tr[k] == 0)

	{

		int np = newnode(s[p].len + 2);

		s[np].fail = s[getfail(i,s[p].fail)].tr[k];

		s[p].tr[k] = np;

		diff[np] = s[np].len - s[s[np].fail].len;

		anc[np] = (diff[np] == diff[s[np].fail] ? anc[s[np].fail] : s[np].fail);

	}

	last = s[p].tr[k];

	return;

}

int f[MAXN],ans[MAXN];

int main()

{

	scanf("%s",S + 1);

	n = strlen(S + 1);

	if(n & 1){puts("0");return 0;}

	init();

	int cur = 0;

	for(int i = 1,j = n;i < j;++i,--j)

	{

		c[++cur] = S[i];

		c[++cur] = S[j];

	}

	ans[0] = 1;

	for(int i = 1;i <= n;++i)

	{

		extend(i,c[i] - 'a');

		for(int p = last;p != 0;p = anc[p])

		{

			f[p] = ans[i - s[anc[p]].len - diff[p]];

			if(anc[p] != s[p].fail)f[p] = (f[p] + f[s[p].fail]) % MOD;

			if(i % 2 == 0)ans[i] = (ans[i] + f[p]) % MOD;

		}

	}

	cout << ans[n] << endl;

	return 0;

}