시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB175556148239.868%

문제

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

승수는 주어진 문자열의 부분수열 중 팰린드롬이 되는 부분수열의 개수를 알고싶어한다. (공집합은 포함하지 않는다)

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

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

입력

첫째 줄에 길이가 30을 넘지 않는 문자열 S가 주어진다. 문자열 S는 알파벳 소문자로만 이루어져 있다.

출력

주어진 문자열 S 의 부분수열 중 팰린드롬이 되는 부분수열의 개수를 출력한다.

예제 입력 1

abb

예제 출력 1

4

출처

University > 고려대학교 > 2017 고려대학교 프로그래밍 대회 > Div 1 C1번