Count Palindromic Substrings

Given a string (S) of length (N), your task is to count the total number of palindromic substrings present in (S). A substring is a contiguous sequence of characters from (S) and is considered palindromic if it reads the same backwards as forwards.

For example, for the string "ababa", the palindromic substrings are: "a", "b", "a", "b", "a", "aba", "bab", "aba", "ababa". In this problem, you need to output the count of all such palindromic substrings.

Note: An (O(N^2)) solution is acceptable for this problem.

inputFormat

The input consists of two lines. The first line contains a single integer (N) ((1 \leq N \leq 10^5)), the length of the string. The second line contains the string (S) itself.

outputFormat

Output a single integer, which is the total number of palindromic substrings in the string (S).## sample

5
ababa

9