inline int I(const char i){return i-'a';} // convert character into index 'a'=0 ..

inline void SUM(long & s,long & x){s = (s + x)% 1000000007;} // add x into s with modulo

int shortPalindrome(string s) {

long count = 0;

constexpr int l_count='z'-'a'+1;

long c3[l_count]={0}; // c3[x] count of previous tri-characters starting with x

long c2[l_count][l_count]={0}; // c2[x][y] count of duo-characters xy, e.g. c2[0][1] = count of "ab"

long c1[l_count]={0};// count of each character so far.

for (auto & x:s)

{
    SUM(count,c3[I(x)]); // add count of all tri-characters which need x to complete palindrome.

    for (int i=0;i<l_count;++i)

    {
        SUM(c3[i],c2[i][I(x)]); // add new combinations of tri-characters which could be created from due-characters by adding x.

    }
    for (int i=0;i<l_count;++i)

    {
        SUM(c2[i][I(x)],c1[i]); // add new combinations of duo-characters which could be created from single characters by adding x

    }
    ++c1[I(x)];// increase count of single characters of x

}
return count;

}