Bộ bốn palindrome

Cho \(S\) là một xâu chỉ gồm các chữ cái.

Hãy đếm số lượng bộ bốn chỉ số \((i,j,k,t)\) thỏa mãn \(1 \le i \le j < k \le t \le |S|\) sao cho xâu ghép \(S[i..j] + S[k..t]\) (nối trực tiếp xâu con \(S[i..j]\) với xâu con \(S[k..t]\)) là một xâu đối xứng (palindrome).

Lưu ý: chỉ cần \(j < k\), không bắt buộc \(k = j+1\) — các ký tự nằm giữa vị trí \(j\) và \(k\) (nếu có) không được sử dụng trong xâu ghép.

Input

Một dòng duy nhất chứa xâu \(S\) (\(1 \le |S| \le 5000\)) chỉ gồm các chữ cái.

Output

In ra một số nguyên duy nhất là số lượng bộ bốn chỉ số thỏa mãn yêu cầu đề bài.

Example

Input:

abbaca

Output:

14