Let $S$ be a string consisting only of letters. Count the number of tuples $(i, j, k, t)$ such that $ 1 \leq i \leq j < k \leq t \leq |S|$ and $S[i..j] + S[k...t]$ is a palindrome.
### Input
- Only line contains a string $S$.
### Output
- Print the number of quadruples that satisfy the conditions.
### Constraints
$|S| \le 5000 $
### Example
Input:
```
abbaca
```
Output:
```
14
```
