分析：

这一题给出的遍历的点的序列，不是树的中序遍历，前序遍历，只要遇到一个节点就打印一个节点。关键点就在，这个序列的首字母和尾字母一定要相同，因为最终都会回到根节点，那么每一个子树也一样。

状态：

d[i][j]表示i至j的状态数

d[i][j]= d[i][j]=(d[i][j]+dp(i,k)*dp(k+1,j-1)%mod)%mod;

#include 
     
      using namespace std;typedef long long ll;const int maxn=300+5;const ll mod=1e9;char s[maxn];ll d[maxn][maxn];ll dp(int i,int j){    if(i>j) return 0;    if(d[i][j]!=-1) return d[i][j];    if(s[i]!=s[j]) return d[i][j]=0;    if(i==j) return d[i][j]=1;    d[i][j]=0;    for(int k=i;k