A palindrome is a word that reads the same backwards as forwards. For example, “a”, “abba” and
“anavolimilovana” are palindromes A sample is a string of one or more lower case letters of the English
alphabet, and the weight of a sample is the number of its substrings (words) that are palindromes, counting
each word occurrence separately.
More precisely, let \(w\) be a sample of length \(n\). The word \(w\)a,b is obtained by taking all characters from
position \(a\) to position \(b\) in sample \(w\). The weight of sample \(w\) is defined as the number of different pairs of
integers \(a\), \(b\) (\(1 \le a \le b \le n\)) such that the word \(w_{a,b}\) is a palindrome.
You are given the sample \(w\). It can either be left unchanged, or exactly one position can be chosen and
the letter on that position arbitrarily changed. Find the maximal possible sample weight that can be
obtained as described above.

Let \(n\) be the length of the given sample.
Subtask
Score
Limitations
1
17
\(1 \le n \le 100\)
2
37
\(101 \le n \le 5\,000\)
3
46
\(5001 \le n \le 100\,000\)

The first line of input contains the given sample \(w\) – a string of lower case letters of the English alphabet.

You must output the required maximal possible weight.

생성자가 기록되지 않았습니다.

출처 COCI 2015/2016 Olympiad