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;
}

def shortPalindrome(s):
  arr1 = [0]*26
  arr2 = [[0]*26 for i in range(26)]
  arr3 = [0]*26
  ans = 0
  for i in range(len(s)):
      idx = ord(s[i]) - ord('a')
      ans += arr3[idx]
      for j in range(26):
          arr3[j] += arr2[j][idx]
      for j in range(26):
          arr2[j][idx] += arr1[j]
      arr1[idx] += 1
  return ans % (10**9+7)

static size_t const alphabetSize{26};
static size_t const aASCII{97};
static size_t const modulo{static_cast<size_t>(std::pow(10, 9)) + 7};

size_t shortPalindrome(
    std::string const & str
){
    using namespace std;
    size_t tuplesCount = 0;
    auto char1{vector<size_t>(alphabetSize, 0)}; 
    auto chars12{vector<size_t>(alphabetSize * alphabetSize, 0)}; 
    auto chars123{vector<size_t>(alphabetSize, 0)};
    size_t chNum{0};
    size_t chCopy{0};
    for(auto const & ch: str){
        chNum = static_cast<size_t>(ch) - aASCII;
        chCopy = chNum;
        tuplesCount = (tuplesCount % modulo) + chars123.at(chCopy);
        for(auto i = 0; i < alphabetSize; ++i){
            chars123.at(i) += chars12.at(chCopy);
            chars12.at(chCopy) += char1.at(i);
            chCopy += 26;
        }
        ++char1.at(chNum);
    } 
    return tuplesCount % modulo;
}

const alphabet = "abcdefghijklmnopqrstuvwxyz".split("")
const mod = (10 ** 9 + 7)
function shortPalindrome(s: string): number {
    let total = 0;
    
    // i
    const firstCharCount: Record<string, number> = {};
    // ij
    const charPairCount: Record<string, number> = {};
    // ijj
    const charDoublePairCount: Record<string, number> = {};
    
    for(const currChar of s){
        for(const char of alphabet){
            const ij = char + currChar; 
            const ijj = char + currChar + currChar; 
            const ijji = currChar + char + char;
            
            total += charDoublePairCount[ijji] || 0;
            total = total % mod;
            
            if(!charDoublePairCount[ijj])
                charDoublePairCount[ijj] = 0
            charDoublePairCount[ijj] += charPairCount[ij] || 0;
            charDoublePairCount[ijj] = charDoublePairCount[ijj] % mod;
            
            if(!charPairCount[ij])
                charPairCount[ij] = 0
            charPairCount[ij] += firstCharCount[char] || 0;
            charPairCount[ij] = charPairCount[ij] % mod;
        }
        if(!firstCharCount[currChar])
            firstCharCount[currChar] = 0;
        firstCharCount[currChar] += 1;
        firstCharCount[currChar] = firstCharCount[currChar] % mod;
    }
    return total;
}

def shortPalindrome(s):
    charCount = {}
    pairCount = {}
    pairHash = {}
    totalCount = 0
    MOD = 10**9 + 7

    for char in s:
        charIndex = ord(char) - ord('a')
        pairIndex = charIndex
        totalCount = (totalCount + pairCount.get(charIndex, 0)) % MOD

        for pairChar in range(26):
            pairCount[pairChar] = (pairCount.get(pairChar, 0) + pairHash.get(pairIndex, 0)) % MOD
            pairHash[pairIndex] = (pairHash.get(pairIndex, 0) + charCount.get(pairChar, 0)) % MOD
            pairIndex += 26

        charCount[charIndex] = charCount.get(charIndex, 0) + 1

    return totalCount