Chef and Programming Contest by His Friend

Fehc is Chef's best friend. They grew up with each other, and often help each other with competitive programming. Chef is participating in a programming contest prepared by Fehc and finds the following problem in Fehc's problem set: given a string s[1..N], count the number of pairs of indices 1 ≤ i ≤ j ≤ N such that s[i..j] is palindrome and j-i is even. The characters that may appear in s are 0,