题目描述

Recently, Student A has been studying strings. Certain peculiar strings caught his attention, so he named such strings quasi-palindromic strings.

A string $s$ is a quasi-palindromic string if and only if the following two conditions are both satisfied:

1. There does not exist any contiguous substring $t$ of $s$ with length greater than or equal to 2 that is a palindromic string.

2. Suppose the length of $s$ is $n$, there exist $l,r$ satisfying $1\leq l\leq r\leq n$, such that after reversing the substring $s[l...r]$, $s$ becomes a palindromic string.

For example: The string aac is not a quasi-palindromic string because it contains the contiguous substring aa of length 2, which is a palindrome. The string abdc is not a quasi-palindromic string because there do not exist $l,r$ such that reversing the substring $s[l...r]$ would turn $s$ into a palindrome. The string bcabca is a quasi-palindromic string.

Now, given a string $T$, Student A wants to know how many contiguous substrings of $T$ are quasi-palindromic strings.

Here, contiguous substrings are distinguished solely by their starting and ending positions in the original string. For instance, in the string aba, the contiguous substring [1,1] (the first a) and the contiguous substring [3,3] (the last a) are considered two different contiguous substrings, even though they are both the character a.

输入格式

A string $T(1\leq |T|\leq 5\times 10^5)$.

输出格式

An integer representing the number of contiguous substrings of $T$ that are quasi-palindromic strings.

abcabc

9

abc

3

提示

In the first sample, all contiguous substrings of length 1 are quasi-palindromic strings. Among substrings longer than 1, the quasi-palindromic strings are abcab, bcabc, and abcabc.