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.

### Input

The input contains a line of *n* lowercase Latin letters (1 ≤ *n* ≤ 3 · 10^{5}).

### Output

### Sample

**Problem Author: **Mikhail Rubinchik

**Problem Source: **Palindromic Contest, July 11, 2015