long pairPalindrome(int i, int j, const vector<vector<int>>& count) {
    if (i >= j) return 0;
    long sum = 0;
    for (int k=0; k < 26; k++) sum = (sum + ((count[j][k] - count[i-1][k]) * (count[j][k] - count[i-1][k] - 1) / 2)) % 1000000007;
    return sum;
}

long shortPalindrome(const string& s) {
    vector<int> TEMP1(26), TEMP2(26);
    vector<vector<int>> count = {TEMP1}, mostRecent = {TEMP2};
    for (int i=1; i <= s.size(); i++) {
        TEMP1[s[i-1]-'a']++;
        count.push_back(TEMP1);
        mostRecent.push_back(TEMP2);
        TEMP2[s[i-1]-'a'] = i;
    }
    long total = 0;
    vector<long> result(s.size()+1);
    vector<vector<int>> cache(s.size()+1, vector<int>(26));
    for (int i=1; i <= s.size(); i++) {
        int index = mostRecent[i][s[i-1]-'a'];
        if (index == 0) continue;
        result[i] = result[index] + (count[index][s[i-1]-'a']-1) * pairPalindrome(index, i-1, count) + pairPalindrome(index+1, i-1, count);
        for (int k=0; k < 26; k++) {
            result[i] = (result[i] + (long)cache[index][k] * (count[i-1][k] - count[index-1][k])) % 1000000007;
            cache[i][k] = (cache[index][k] + (long)(count[index][s[i-1]-'a']-1)*(count[i-1][k] - count[index-1][k])
                          + count[i-1][k] - count[index][k]) % 1000000007;
        }
        total = (total + result[i]) % 1000000007;
    }
    return total;
}