#include <cmath>

#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

long long lcs(string &a, string &b)

{

    int sizea = a.length();

    int sizeb = b.length();

    vector<vector<long long>> dp(sizea, vector<long long>(sizeb));

    //  We only consider prefixes with a[0] matched

    //  to avoid duplicate counting

    for(int i = ; i < sizeb; i ++)

    {

        if(a[] == b[i]) dp[][i] = ;

        if(i) dp[][i] += dp[][i - ]; // we count accumulated

        dp[][i] %= ;

    }

    for(int i = ; i < sizea; i ++)

    {

        dp[i][]  = dp[i - ][]; // all from dp[0][0]; part of init

        for(int j = ; j < sizeb; j ++)

        {

            dp[i][j] = dp[i - ][j] + dp[i][j - ]; // accumulated version of LCS.

            if(a[i] != b[j]) dp[i][j] -= dp[i-][j-]; // TODO: need 2nd thought on why

            dp[i][j] %= ;

        }

    }

    return dp.back().back();

}

int main()

{

    int t; cin >> t;

    string str;

    while(t--)

    {

        cin >> str;

        long long ans = ;

        for(int i = ; i < str.length(); i ++)

        {

            string sb = str.substr(i, str.length()- i);

            string sa = str.substr(, i);

            ans += lcs(sb, sa);

            ans %= ;

        }

        cout << ans << endl;

    }

    return ;

}