对于一棵多叉树，可以进行先序遍历：

每次递归，1.遍历根， 2. 遍历左边第一个儿子，并对这个儿子结点继续依据先序遍历的规则遍历， 3. 遍历从左到右第二个儿子，并对这个儿子结点继续依据先序遍历的规则遍历， 4. 。。。 5. 遍历从左到右最后一个儿子，并对这个儿子结点继续依据先序遍历的规则遍历。

有一次罗老师写了一个程序对一棵多叉树进行先序遍历，每到一个结点，就输出该结点的结点字母，得到如下序列： ABABABA

但这个时候罗老师又有一个困惑，这个遍历结果的二叉树显然有多种形状，具体有5种，如下图所示：

这里注意，如果某个节点下面只有一个直接儿子，那么不用考虑这个儿子在左边还是右边， 但如果这个结点下面有多个直接儿子，那么他们相对位置不一样算不同方案，比如(c), (d)就算不同方案。

罗老师想知道，给定一种遍历的结果，问这样的多叉树方案有多少种。这个结果可能会很大，那么结果要对 1000000000取余。如果这个遍历的结果有问题，即不是合法的遍历结果，那么输出0。

输入一行字符串，全部由大写字母构成，长度不超过300

输出方案数，如题目所述。

【样例说明】

输入AB

输出0

题解：

dp三要素，状态，转移，初值终值

树形类DP最好写成递归形式

那么要将(1, n)分成多少种方案，可以：

ll dfs(int st, int ed){ //以st,ed作为起点重点的遍历种类数量

    //printf("st=%d st=%d\n",st,ed);

    if(st==ed) {

        dp[st][ed]=1LL; //初值

        return dp[st][ed];

    }

    if(dp[st][ed]!=-1) return dp[st][ed]; //记忆化

    dp[st][ed]=0LL;

    if(str[st]!=str[ed]){

        return dp[st][ed];

    }

    for(int i=st+1; i<=ed; i++){

        //以st作为根

        dp[st][ed]+=dfs(st+1,i)*dfs(i+1,ed);

        //(st+1,i)这段独立一段作为左儿子，特点是只有一个st的直系儿子, str[i]不一定要等于str[st]

        //(i+1,ed)这段作为剩下的兄弟们，这些兄弟可以继续再分出一个儿子，然后剩下的继续兄弟们，特点是最终str[ed]必须要等于str[st],等于str[i+1]

        if(dp[st][ed]>=MOD) dp[st][ed]%=MOD;

    }

    //cout<<st<<" "<<ed<<" "<<dp[st][ed]<<endl;

    return dp[st][ed];

}

递归过程中，记录状态，这个状态就是，i到j这个区间可以构成多少种方案

递归终点就是一个结点时，只有一种方案

状态转移就是dp[st][ed]+=dfs(st+1,i)*dfs(i+1,ed);