from collections import defaultdict

def shortPalindrome(s):
    MOD = 10**9 + 7
    total_num = 0  # ABBA
    single_count = defaultdict(int)  # A
    pair_count = defaultdict(int)  # AB
    triplet_count = defaultdict(int)  # ABB
    
    for char in s:
        total_num = (total_num + triplet_count[char]) % MOD
        
        for c in single_count:
            triplet_count[c] = (triplet_count[c] + pair_count[(c, char)]) % MOD
        
        for c in single_count:
            pair_count[(c, char)] = (pair_count[(c, char)] + single_count[c]) % MOD
            
        single_count[char] += 1
        
    return total_num

public static int shortPalindrome(String s) {
            int MOD = 1_000_000_007;
            int n = s.length();
            
            long[] singleCount = new long[26];
            long[][] pairCount = new long[26][26];
            long[] tripletCount = new long[26];
            
            long palindromeCount = 0;

            for (char ch : s.toCharArray()) {
                int charIndex = ch - 'a';

                palindromeCount = (palindromeCount + tripletCount[charIndex]) % MOD;

                for (int i = 0; i < 26; i++) {
                    tripletCount[i] = (tripletCount[i] + pairCount[i][charIndex]) % MOD;
                }

                for (int i = 0; i < 26; i++) {
                    pairCount[i][charIndex] = (pairCount[i][charIndex] + singleCount[i]) % MOD;
                }

                singleCount[charIndex] = (singleCount[charIndex] + 1) % MOD;
            }

            return (int) palindromeCount;
        }

def shortPalindrome(s):
    upper = 1000000007
    # css1[ord('x') - ord('a')] is the number of subsequences x
    css1 = [0 for _ in range(26)]
    # css2[ord('x') - ord('a')][ord('y') - ord('a')] is the number of ss xy
    css2 = [[0 for _ in range(26)] for _ in range(26)]
    # css3[ord('x') - ord('a')] is the count of all ss xaa, xbb, xcc, ...
    css3 = [0 for _ in range(26)]
    
    ans = 0
    for c in s:
        k = ord(c) - ord('a')
        
        ans = (ans + css3[k]) % upper
        for i in range(26):
            css3[i] = (css3[i] + css2[i][k]) % upper
        for j in range(26):
            css2[j][k] = (css2[j][k] + css1[j]) % upper
        
        css1[k] = (css1[k] + 1) % upper
    
    return ans % upper

public static int shortPalindrome(string s)
{
    var (mod, occ1, occ2, occ3) = (1000000007, new int[26], new int[26, 26], new int[26, 26, 26]);
    return s.Select(c => c - 'a').Aggregate(0, (acc, c) =>
    {
        for (var i = 0; i < 26; i++)
        {
            acc = (acc + occ3[c, i, i]) % mod;
            occ3[i, c, c] = (occ3[i, c, c] + occ2[i, c]) % mod;
            occ2[i, c] = (occ2[i, c] + occ1[i]) % mod;
        }
        occ1[c]++;
        return acc;
    });
}

public static int shortPalindrome(String s) {
    // Write your code here
        int n = s.length();
        final int NUM_OF_CHARs = 26;
        final long MOD = 1000 * 1000 * 1000 + 7;
        long res = 0;
        
        long[] charsCount = new long[NUM_OF_CHARs];
        long[][] pairsCount = new long[NUM_OF_CHARs][NUM_OF_CHARs];
        long[] trippletsCount = new long[NUM_OF_CHARs];
        
        for (int i = 0; i < n; i ++) {
            char c = s.charAt(i);
            int cIdx = (int) (c - 'a');
    
    //in the last turn, the pattern was '*' 'c' 'c'
    //this turn's pattern turns into 'c' '*' '*' 
    //another 'c' is needed to complete the palindrome of 4 chars
    //so if current char satisfies, include the count of 'c' '*' '*' 
    
            res = (res + trippletsCount[cIdx]) % MOD;
            
            for (int j = 0; j < NUM_OF_CHARs; j++) {
                
    //below line usage should be to keep tab on '*' 'c' 'c' tripllets
    //it depends on pairsCount which monitors '*''c'
                
                trippletsCount[j] = (trippletsCount[j] + pairsCount[j][cIdx]) % MOD;
    
    //this pairsCount means finding pairs that are '*''c' ('c' as in currently parsing char)
    //this depends on the preceeding '*', not 'c' 
    //therefore it should be delay 1 turn, hence placed before charsCount update
    
                pairsCount[j][cIdx] = (pairsCount[j][cIdx] + charsCount[j]) % MOD;   
            }
            
    //this charsCount is straight forward, 
    //it is to track frequency of appeared CURRENT characters 'c'
     
            charsCount[cIdx]++;
        }
        
        return (int) (res % MOD);
    }