팰린드롬 개수 구하기 (Small)

팰린드롬(palindrome)은 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어이다. 'aba'나 'a'는 팰린드롬이고, 'abaccbcb'나 'anavolimilana'는 팰린드롬이 아니다.

승수는 주어진 문자열의 부분수열 가운데 팰린드롬인 것이 몇 개인지 알고 싶다. 빈 부분수열은 세지 않는다. 부분수열은 고른 위치의 집합으로 구별하므로, 글자가 같더라도 고른 위치가 다르면 다른 부분수열로 센다.

예를 들어 'abb'의 부분수열은 'a', 'b', 'b', 'ab', 'ab', 'bb', 'abb'이고, 이 가운데 팰린드롬은 'a', 'b', 'b', 'bb'로 4개이다.

문자열이 주어질 때 팰린드롬인 부분수열의 개수를 출력하는 프로그램을 작성하시오.

첫째 줄에 문자열 $S$가 주어진다. $S$의 길이는 1 이상 30 이하이고, $S$는 알파벳 소문자로만 이루어져 있다.

$S$의 부분수열 가운데 팰린드롬인 부분수열의 개수를 출력한다.