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

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

승수는 주어진 문자열의 부분수열 가운데 팰린드롬인 것의 개수를 알고 싶다. 빈 부분수열은 세지 않는다. 고른 위치가 다르면 같은 문자열이 되더라도 서로 다른 부분수열로 센다.

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

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

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

$S$의 부분수열 가운데 팰린드롬인 부분수열의 개수를 $10\,007$로 나눈 나머지를 출력한다.