Your task is to calculate number of triplets (i, j, k) such that i ≤ j < k and s[i..j] is a palindrome and s[j+1 .. k] is a palindrome.

The input contains a line of n lowercase Latin letters (1 ≤ n ≤ 3 · 10⁵).

Output the answer.