Since length < 700

Choose all pairs of indices i, j such that s[i] == s[j]. and j > i + 1 in the string s.

At indexes i and j find out count of all the characters (26 alphabets ) prior to i and after j.

To count occurrences of all chars prior to index i use standard prefix sums.

To count occurrences of all chars post index j use standard suffix sums and precompute these 2 values.

The number of palindromes such that the first and fourth index of that 5 length palindrome in string s are i and j respectively will be

summation of following expression over all 26 chars.

```
int ans = 0;
for(int ch= 0; ch< 26; ch ++) {
ans += prefix[i - 1][ch] * suffix[j +1][ch] * ( j - i - 1)
}
```

At the end answer will be summation of all the answers in the code snippet above.

Time Complexity O(N^2) space O(N) where N = length of string

Space Complexity O(N)