#include <bits/stdc++.h>
using namespace std;

// Modulo
static const int MOD = 1000000007;

// Manacher's for Even-Length Palindromes
// d[i] = maximum radius of even-length palindrome centered between (i-1) and i.
vector<int> evenManacher(const string &s) {
    int n = (int)s.size();
    vector<int> d(n, 0);
    int l = 0, r = -1;
    for(int i = 0; i < n; i++){
        int k = (i > r ? 0 : min(d[l + r - i + 1], r - i + 1));
        while(i + k < n && i - k - 1 >= 0 && s[i - k - 1] == s[i + k]) {
            k++;
        }
        d[i] = k;
        if(i + k - 1 > r){
            l = i - k;
            r = i + k - 1;
        }
    }
    return d;
}

// Fast exponent for 2 or simple approach to get inverse(2) is (MOD+1)/2
long long inv2 = (MOD + 1) / 2;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; 
    cin >> T;
    while(T--){
        string P;
        cin >> P;
        int n = (int)P.size();

        // 1) Compute even-manacher array
        vector<int> d = evenManacher(P);

        // We will gather:
        // (A) Total number of even palindromes "M"
        // (B) Sum of lengths, but we specifically need "r" = (length / 2)
        // (C) Sum of r^2
        // (D) Each boundary (L,R) for overlap counting
        long long M = 0, halfLenSum = 0, sumR2 = 0;

        // expansions for boundary (L,R)
        vector<pair<int,int>> expansions;

        // For center i, we have radii r in [1..d[i]] => each gives a palindrome of length = 2*r
        for(int i=0; i<n; i++){
            int rmax = d[i];
            // Add r=1..rmax
            // That means "rmax" palindromes
            M += rmax;

            // Summations for half-length "r"
            // sum_{r=1..rmax} r = rmax*(rmax+1)/2
            // sum_{r=1..rmax} r^2 = rmax*(rmax+1)*(2*rmax+1)/6
            long long rr = (long long)rmax;
            long long sum_r  = rr * (rr + 1) / 2; 
            long long sum_r2 = rr * (rr + 1) * (2*rr + 1) / 6;
            halfLenSum = (halfLenSum + sum_r) % MOD;
            sumR2      = (sumR2      + sum_r2) % MOD;

            // Record boundaries
            // For each radius r in [1..rmax], boundaries => [i-r, i+r-1]
            for(int r=1; r<=rmax; r++){
                int L = i - r;
                int R = i + r - 1;
                expansions.push_back({L,R});
            }
        }
        M %= MOD;

        // Part A: sum_{(S,T), S<T} (|S|+|T|)/2 = sum_{(S,T), S<T} (rS + rT)
        // Identity => ( (Σ rS)^2 - Σ(rS^2 ) ) / 2
        long long halfLenSumSq = (halfLenSum * halfLenSum) % MOD;
        long long partA = ( (halfLenSumSq + MOD) - sumR2 ) % MOD;
        partA = (partA * inv2) % MOD; 

        // Part B: Overlap counting
        // freq(L,R) => how many palindromes share boundary (L,R)
        unordered_map<long long,int> freq;
        freq.reserve(expansions.size());
        freq.max_load_factor(0.7f);

        auto pairToLL = [&](int l, int r){
            // Combine (l,r) into 64-bit
            return ((long long)l << 32) ^ (long long)(r & 0xffffffffULL);
        };

        for(auto &pr : expansions){
            long long key = pairToLL(pr.first, pr.second);
            freq[key]++;
        }

        long long sumOverlap = 0;
        for(auto &kv : freq){
            long long f = kv.second;
            if(f > 1){
                // Each boundary with freq f => comb(f,2) = f*(f-1)/2
                long long c2 = f*(f-1)/2;
                sumOverlap = (sumOverlap + c2) % MOD;
            }
        }

        // Final answer => partA - sumOverlap
        long long answer = (partA + MOD - sumOverlap) % MOD;

        cout << answer << "\n";
    }

    return 0;
}