In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence <A, B, D> is a subsequence of <A, B, C, D, E, F>. 
(http://en.wikipedia.org/wiki/Subsequence)

Given a string S, your task is to find out how many different subsequence of S is palindrome. Note that for any two subsequence X = <S _x1, S _x2, ..., S _xk> and Y = <S_y1, S _y2, ..., S _yk> , if there exist an integer i (1<=i<=k) such that xi != yi, the subsequence X and Y should be consider different even if S _xi = S _yi. Also two subsequences with different length should be considered different.

4

a

aaaaa

goodafternooneveryone

welcometoooxxourproblems

Case 1: 1

Case 2: 31

Case 3: 421

Case 4: 960

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<stack>

#include<set>

#include<vector>

#include<map>

#include<cmath>

const int maxn=1e5+;

const int mod=;

typedef long long ll;

using namespace std;

char str[];

ll dp[][];

int main()

{

   int T;

   int cnt=;

   cin>>T;

   for(int t=;t<=T;t++)

   {

       scanf("%s",str+);

       int len=strlen(str+);

       memset(dp,,sizeof(dp));

       for(int t=;t<=len;t++)

       {

           dp[t][t]=;

           if(t<len&&str[t]==str[t+])

           {

               dp[t][t+]=;

        }

        else

        {

            dp[t][t+]=;

        }

    }

    for(int l=;l<=len;l++)

    {

        for(int j=;j+l<=len;j++)

        {

            int r=j+l;

            if(str[j]==str[r])

            {

                dp[j][r]=(dp[j+][r]+dp[j][r-]+)%mod;

            }

            else

            dp[j][r]=(dp[j][r-]+dp[j+][r]-dp[j+][r-]+mod)%mod;

        }

    }

    printf("Case %d: %lld\n",cnt++,dp[][len]);

   }

   return ;

}