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