Question
Winning Speech
In the celestial kingdom, a heavenly icon delivers an ancient winning speech written in a mysterious language. The speech is represented as a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression.
The scholars of the kingdom believe that certain parts of the speech possess magical symmetry. A substring is considered magical if it is a palindrome — meaning it reads the same forward and backward.
Your task is to determine the total number of palindromic substrings present in the speech.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the length of the string.
The second line contains the string KaTeX can only parse string typed expression, consisting of lowercase English letters.
The second line contains the string KaTeX can only parse string typed expression, consisting of lowercase English letters.
Output
Print a single integer — the total number of palindromic substrings in the string KaTeX can only parse string typed expression.
Example
Input
5
level
Output
7
Explanation
The palindromic substrings are:
"l", "e", "v", "e", "l", "eve", "level"
Total = 7 palindromic substrings.
5
level
Output
7
Explanation
The palindromic substrings are:
"l", "e", "v", "e", "l", "eve", "level"
Total = 7 palindromic substrings.