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