hr-short-palindrome

/**
    * Author    : Arif Ahmad
    * Date      :
    * Algo      :
    * Difficulty:
*/

#include <bits/stdc++.h>
using namespace std;

#define INF_MAX     2147483647
#define INF_MIN     -2147483648
#define INF         (1 << 30)
#define EPS         1e-9
#define PI          acos(-1.0)
#define N           2 + 1000000
#define MOD         1000000007
#define sz(x)       (int)(x).size()
#define all(x)      (x).begin(), (x).end()
#define pb          push_back
#define mp          make_pair
#define ms(x, a)    memset((x), (a), sizeof(x))
#define F           first
#define S           second
#define rep(i,a,b)  for(int i=(a); i<(b); ++i)
#define repC(i,x)   for(size_t i=0; i<x.size(); ++i)
#define repIT(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define nn          '\n'

typedef long long       LL;
typedef pair<int,int>   pii;
typedef vector<int>     vi;
typedef vector<string>  vs;
typedef vector<char>    vc;
typedef vector<bool>    vb;
typedef vector< pii >   vii;
typedef map<string,int> msi;
typedef map<int,int>    mii;
typedef map<char,int>   mci;
typedef map<int,string> mis;

template<class T> T Abs(T x) {return x>0 ? x : -x;}
template<class T> T Max(T a, T b) {return a>b ? a : b;}
template<class T> T Min(T a, T b) {return a<b ? a : b;}
template<class T> T gcd(T a, T b) {return (b ? gcd(b,a%b) : a);}
bool isVowel(char ch){ch=tolower(ch);return(ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u');}

//int dx[4] = {-1, 0, 0, 1};
//int dy[4] = {0, -1, 1, 0};
//int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
//int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    #ifndef ONLINE_JUDGE
        /// comment it out before submission
        //freopen("in.txt", "r", stdin);
    #endif

    int i, j, k, n, tc;
    string s;
    int freq[26] = {0};
    int pair_freq[26][26] = {0};
    int triplet_freq[26] = {0};
    int ans = 0;

    cin >> s;
    for(char c : s) {
        int v = int(c - 'a');
        ans = (ans + triplet_freq[v]) % MOD;

        for(int i=0; i<26; i++) {
            triplet_freq[i] = (triplet_freq[i] + pair_freq[i][v]) % MOD;
        }

        for(int i=0; i<26; i++) {
            pair_freq[i][v] = (pair_freq[i][v] + freq[i]) % MOD;
        }

        freq[v]++;
    }

    cout << ans << '\n';
    return 0;
}