Problem Setter: Alve Rahman (AlveRahman)
Problem Tag: Palindromic Tree, Dfs and similar.
Tutorial: If we build a palindromic tree from the given string P, then each node of the tree will contain a distinct palindromic substring of P and we can also store in the node the number of occurrences of that palindrome in P. Let’s say, node u and v in the tree represents string S and T respectively. The distance between S and T is then the number of edges on the simple path from node u and v . Since a palindromic substring could occur multiple times in P, the contribution of a distinct unordered pair of palindromic substring (S,T) to the answer is no. of occurrences of S * no. of occurrences of T * the number of edges on the simple path from node u to v. We can solve this problem by calculating the contribution of each edge of the tree to the answer. Let’s say the value of a node is the number of occurrences of the string represented by that node. The contribution of the edge u to v is the sum of the product of pairs of values from the subtree of v and the values of nodes which are not in the subtree of v. To quickly count the sum of products, note that sum of product of each pair is the same as product of sum of the values of the 2 sets. So, we will count the sum of values in the subtree of v. Then the contribution of the edge u to v is sum[v] * (sum of values of all nodes - sum[v]). By adding the contribution of each edge, the problem is solved for a tree. For this problem, only traversing the tree for even length palindrome is enough.
Time Complexity: O(|P|), building palindromic tree is O(|P|) and finding subtree sum is also O(|P|).
Code :

#define _GLIBCXX_FILESYSTEM
#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 3e5+10, mod = 1e9+7;
string s;

struct PaliTree{
    #define sz 26
    struct node{
        int lng;
        int link;
        int next[sz];
        ll oc;
        node(int _lng){
            lng = _lng;
            link = 0;
            oc = 0;
            memset(next,-1,sizeof(next));
        }
    };

    vector<node> tree;
    int cur;
    
    PaliTree(){
        tree.push_back(node(-1)); //img
        tree.push_back(node(0)); //root
        cur = 1;
    }

    int get_id(char c){return c-'a';}

    int get_link(int now,int i){
        char c = s[i];
        while(1){
            if(now == 0 or (i-1-tree[now].lng > 0 and s[i-1-tree[now].lng] == c)) break;
            now = tree[now].link;
        }
        int id = get_id(c);
        return (tree[now].next[id] == -1)?now:tree[now].next[id];
    }

    void add(int i){
        char c = s[i];
        int id = get_id(c);
        while(1){
            if(cur == 0 or (i-1-tree[cur].lng > 0 and s[i-1-tree[cur].lng] == c)) break;
            cur = tree[cur].link;
        }
        if(cur == 0 and s[i] == s[i-1]) cur = 1;
        if(tree[cur].next[id] == -1){
            node tmp(tree[cur].lng+2);
            if(tmp.lng == 1) tmp.link = 1;
            else tmp.link = get_link(tree[cur].link,i);
            tree.push_back(tmp);
            tree[cur].next[id] = tree.size()-1;
        }
        // cerr << i << ' ' << cur << ' ';
        cur = tree[cur].next[id];
        // cerr << cur << '\n';
        tree[cur].oc++;
    }

    void calc(){
        for(int i = tree.size() - 1; i > 1; i--){
            tree[tree[i].link].oc += tree[i].oc;
        }
    }

    void clear() {
        tree.clear();
        tree.push_back(node(-1)); //img
        tree.push_back(node(0)); //root
        cur = 1;
    }
}pt;

ll sum[N],ans;

void dfs(int u) {
    if(u != 1) sum[u] = pt.tree[u].oc;
    for(int i = 0; i < 26; i++) {
        int nu = pt.tree[u].next[i];
        if(nu != -1) {
            dfs(nu);
            sum[u] += sum[nu];
        }
    }
}

void dfs2(int u) {
    for(int i = 0; i < 26; i++) {
        int nu = pt.tree[u].next[i];
        if(nu != -1) {
            ans += sum[nu] % mod * ((sum[1] - sum[nu]) % mod) % mod;
            ans %= mod;
            dfs2(nu);
        }
    }
}

void solve() {
    cin >> s;
    s = "#" + s;
    for(int i = 1; i < s.size(); i++) {
        pt.add(i);
    }
    pt.calc();
    for(int i = 1; i < pt.tree.size(); i++) {
        sum[i] = 0;
    }
    dfs(1);
    ans = 0;
    dfs2(1);
    cout << ans << '\n';
    pt.clear();
    return;
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int tc = 1;
    cin >> tc;
    for(int kase = 1; kase <= tc; kase++) {
        //cout << "Case " << kase << ": ";
        solve();
    }
    return 0;
}