Background

Xiao Fang does not want to become Xiao Cube.

Problem Description

You are given a string consisting of lowercase letters. Find how many intervals $[l,r]$ satisfy that the substring represented by this interval is a palindrome, and the number of occurrences of each character does not exceed $2$.

Input Format

One line contains a string $S$ ($\lvert S\rvert\leq 5\times 10^4$).

Output Format

One line contains one number, which is the answer.

ababa

8

Hint

Translated by ChatGPT 5