시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 14 2 2 14.286%

문제

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 wa,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 ≤ abn) such that the word wa,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.

입력

The first line of input contains the given sample w – a string of lower case letters of the English alphabet. (1 ≤ n ≤ 100 000)

출력

You must output the required maximal possible weight.

예제 입력

aaaa

예제 출력

10

예제 입력 2

baccb

예제 출력 2

9

예제 입력 3

slavko

예제 출력 3

7

힌트

Clarification of the first example: Each substring from the sample already is a palindrome, so it is best left unchanged.

Clarification of the second example: If we change the second letter of the sample to “c”, we will get the sample “bcccb” with a weight of 9.