Count Different Palindrome Substrings

A string S is considered palindrome if it reads same way if spelled backwards, for example "nolemonnomelon", "ASANtaLivedAsAdeviLatNASA".

Any non-empty string has substrings that are palindromes. For example, in the string S = "hellolle", there are many of such "subpalindromes":

• ellolle
• ll, ll - note that these are two distinct substrings that only happen to be equal.
• lol and lloll
• And each single letter can be considered a palindrome - 8 of them.

Please write a function that, given a string S (only contains lowercase letters), returns number of different ways are there to pick a palindrome substring fro mS.