#include <iostream>
#include <string>
#include <vector>

using std::string;
using std::vector;
using std::cout; using std::endl;

class Solution {
public:
    int countPalindromicSubsequences(string S) {
        int n = S.length();
        vector<vector<long>> dp(n, vector<long>(n, 0));
        for (int i = 0; i < n; i++)
            dp[i][i] = 1;
        for (int len = 1; len < n; len++) {
            for (int i = 0; i + len < n; i++) {
                int j = i + len;
                if (S[i] == S[j]) {
                    dp[i][j] = 2 * dp[i + 1][j - 1];
                    int l = i + 1, r = j - 1;
                    for (; l <= r && S[l] != S[i]; l++);
                    for (; l <= r && S[r] != S[j]; r--);
                    if (l == r)
                        dp[i][j] += 1;
                    else if (l > r)
                        dp[i][j] += 2;
                    else
                        dp[i][j] -= dp[l + 1][r - 1];
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
                }
                dp[i][j] = dp[i][j] % MOD;
            }
        }
        return dp[0][n - 1];
    }

private:
    static constexpr long MOD = 1000000007;
};


// Input: 
// S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
// Output: 104860361

// bccb
// len 0:
// len 1: b c
// len 2: bb cc
// len 3: bcb
// len 4: bccb

// dp[i][j] means different palindroms count between i and j
// loop len, i, j
// init:
//      dp[i][i] = 1
// s[i] == s[j]:
// CASE1: b ccbcc b   ->   +"bb"
//          2 * count(ccbcc) + 1
// CASE2: b c b       ->   +"b" +"bb"
//          2 * count(c) + 2
// CASE3: b ca b      ->   +"b" +"bb"
//          2 * count(ca) + 2
// CASE4: b bcab b    ->   -"bcb" -"bab"
//          2 * count(bcab) - count(ca)
// s[i] != s[j]:
//      dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]


int main() {
    Solution* sol = new Solution;
    string input;

    input = "addd";
    cout << "actual: " << sol->countPalindromicSubsequences(input) << ", expected: " << 4 << endl;

    input = "bccb";
    cout << "actual: " << sol->countPalindromicSubsequences(input) << ", expected: " << 6 << endl;

    input = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba";
    cout << "actual: " << sol->countPalindromicSubsequences(input) << ", expected: " << 104860361 << endl;

    input = "baaddaaabaddccbbbdcbcccbdbdabdabdbadabddbbcbbcabbccdaccdbcbbcdcdbaadbcadacabcaaaadbcaddbbacddcdabaadcacacdcabaadacadcccdcbbcdabdcdacaacdcdbdacbdbcdcbaddaccabaaaabcadacdaddbcccbcdbadbdddaaabbdbdbcbcdab";
    cout << "actual: " << sol->countPalindromicSubsequences(input) << ", expected: " << 431300010 << endl;

    input = "bdccbdbdcaacaadbdacaadabbdaababacbdbadaccccbbbccbdbddcacdbbcdaaababddadbbcabaddbbaabcdacdcddcbacdcadddbaadcbbccdcbdcaaabcbddacaccadacdcadacadccabdbadcdabaaccbcabbacdcbbbabddbcccbcbcddacaccabbabccdbbabacadbbdbcccbddaaadcdaddcccddaacbddabddabadbcbaadcaddbdccabaddcccdccbacaccccbcdccacbabddcbcbbbdbbddaabbcaddbddddaacbbccbcdbadacccbadbccdddadcbacbbdcabcbdbbaabcdcbdacabacdccdaabcbbddbdddcacdbdccbbabbaccdcbabcdacdabdddaddacdbddabcbbbdcccacbdadddbbdbcabccadbcbadddcbcddaababcabbbcbbabadaddabcbdacaadcababcbacadcdabcdbddadaadddddbaaacddaacadcdbaaacbacaabdabccbacabbabddacddcdacdcddbacbddbdcadcddabdadcdbcbbcadbcdabbbbdcdadadbbcadbcbbcccccabdaabcdacbdbcadabcdbaaaaacdaaabcdcaabddcacdcacabbaadbdbcbaaabadbdadadaccddacababbdcbaaaccaabbdaddadcabaabbdaadadcabcabbdbbdccbabbbabbcbcbdcacccbdbabdbaadccdaddaddaadadccabdcbbbccacbbaaabccaccdcabbbddbdbbacdaabbdcdacbdddbacbadccabbbdbbbdbdbcadcacddddcdbdcabccdccabaadbcbacaaababdddcbcdaaabaaabddbcabcbbcdddccdcbccbbccadccaaccccbdadcaacdcbcabacacadaabacddaadcccbcabdad";
    cout << "actual: " << sol->countPalindromicSubsequences(input) << ", expected: " << 739921586 << endl;

    return 0;
}