N different palindromes

A palindrome is a string that reads same in both directions: forwards and backwards. For example, the strings radar and noon are palindromes, whereas the string chef is not a palindrome as being read backwards is becomes equal to fehc, which is not equal to chef. Let's say that the pair of indices (i, j) denotes a palindrome in some string S iff i ≤ j and the substring starting at the i-th chara