Double Palindrome

문제

Vanya works at the factory producing palindromes. The factory has a workpiece --- a string $ss$ line of length $nn$, consisting of lowercase English letters, from which Vanya can cut out any substring for sale. We remind you that palindrome --- is a string that reads in the same way from left to right and from right to left.

A lot of people are fed up with a usual palindromes, so Vanya decided to produce double palindromes instead. Double palindrome is a string formed by a concatenation of two palindromes of equal length. For example, the strings "aabb", "aaaa" are double palindromes, while strings "abba" and "aaaabb" are not.

Vanya wonders how many ways are there to cut out double palindrome from $ss$. In other words, how many there are pairs $(l,r)(l,\; r)$, such that substring $s_l{s}_{l+1}\dots s_{r}s\_l\; s\_\{l+1\}\; \backslash ldots\; s\_r$ is a double palindrome. Please help Vanya to find an answer to this question.

입력

The first line contains an integer $nn$ ($1\le n\le 5000001\; \backslash leq\; n\; \backslash leq\; 500\backslash ,000$) --- the length of the string $ss$. The second contains a string $ss$, consisting of lowercase English letters.

출력

Print a single integer --- the number of double palindrome substrings.

힌트

In the first example, there are 5 double palindromes of length 2 ("ab", "ba", "ac", "ca" and "ac"), and the whole string is a double palindrome as well ("abacac").

6
abacac

6

5
aaaaa

6