시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 50 12 10 41.667%

문제

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

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

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

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

입력

첫째 줄에 길이가 30을 넘지 않는 문자열 S 가 주어진다.

출력

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

예제 입력

abb

예제 출력

4

힌트

출처