Hi guys,

I encountered a problem requiring us to find how many "Double Palindromes" are in the given input String.

A "Double Palindrome" is a string of concatenation of two palindromes with the same size. For example, "aabb", "aaaa" are the "Double Palindromes", but "abba" or "aaaabb" are not. Given an input string, the task is to calculate how many "Double Palindromes" exist in it. On the other word, our task is to calculate how many distinct pairs (l, r) satisfy the condition that S(l)S(l+1)...S(r) is "Double Palindromes".

Sample Input : "abacac" then output will be 6 because of : "ab", "ba", "ac", "ca", "ac" and "abacac" are "Double Palindromes".

Sorry for the missing: n <= 500000