A string S is called palindrome if it reads the 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":

• 1) ellolle
• 2) ll, ll - note that these are two distinct substrings that only happen to be equal
• 3) lol and lloll
• 4) And, of course, each letter can be considered a palindrome - all 8 of them.

Write a function that, given a string S (that only consists of lowercase English letters), counts how many different ways are there to pick a palindrome substring from S.