AT_abc468_d [ABC468D] Pre-Palindrome

A string consisting of lowercase English letters is called a **good string** if it satisfies the following condition. - It can be turned into a palindrome by rewriting at most one character. For example, `a`, `iwai`, and `abcdcza` are good strings, but `abcd` and `atcoder` are not good strings. Note that, in particular, a palindrome is also a good string. You are given a string $ S $ consisting of lowercase English letters. Find the number of non-empty substrings (contiguous subsequences) of $ S $ that are good strings. Two substrings taken from different positions of $ S $ are counted separately even if they are equal as strings. What is a substring?A **substring** of $ S $ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $ S $ . For example, `ab` is a substring of `abc`, but `ac` is not a substring of `abc`.

The input is given from Standard Input in the following format: > $ S $

Output the answer.

### Sample Explanation 1 The substring `ba` from the $ 2 $ nd through $ 3 $ rd characters of $ S $ and the substring `ababa` from the $ 1 $ st through $ 5 $ th characters are some good strings. Among the $ 15 $ substrings, the good strings are the $ 13 $ substrings other than `abab` from the $ 1 $ st through $ 4 $ th characters and `baba` from the $ 2 $ nd through $ 5 $ th characters. ### Constraints - $ S $ is a string of length between $ 1 $ and $ 10^4 $ , inclusive, consisting of lowercase English letters.