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