#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
vector<pair<int, int>> find_even_palindromes(const string &s) {
    int n = s.size();
    vector<pair<int, int>> even_palindromes;
    vector<int> radius(n);

    for (int center = 0; center < n - 1; center++) {
        int l = center, r = center + 1, rad = 0;
        while (l >= 0 && r < n && s[l] == s[r]) {
            rad++;
            even_palindromes.emplace_back(l, r);
            l--;
            r++;
        }
    }

    return even_palindromes;
}

int calculate_distances(const vector<pair<int, int>> &palindromes) {
    int n = palindromes.size();
    vector<int> lengths;
    for (const auto &[l, r] : palindromes) {
        lengths.push_back((r - l + 1));
    }

    sort(lengths.begin(), lengths.end());

    int64_t total_distance = 0, sum_lengths = 0;
    for (int i = 0; i < n; i++) {
        total_distance = (total_distance + (int64_t)lengths[i] * i - sum_lengths) % MOD;
        sum_lengths = (sum_lengths + lengths[i]) % MOD;
    }

    return (int)total_distance;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        string P;
        cin >> P;

        vector<pair<int, int>> palindromes = find_even_palindromes(P);

        int result = calculate_distances(palindromes);
        cout << result / 2 << '\n';
    }

    return 0;
}