Counting Palindromic Subsequences (Large)

A palindrome is a word that reads the same forward and backward. Words such as 'aba' and 'a' are palindromes, while words such as 'abaccbcb' and 'anavolimilana' are not.

Seungsu wants to know how many subsequences of a given string are palindromes. The empty subsequence is not counted. Subsequences taken from different sets of positions are counted separately, even if they spell the same string.

For example, the subsequences of 'abb' are 'a', 'b', 'b', 'ab', 'ab', 'bb', and 'abb'. Of these, 'a', 'b', 'b', and 'bb' are palindromes, so there are 4.

Given a string, write a program that prints the number of its subsequences that are palindromes.

The first line contains a string $S$ of length at most 1000. $S$ consists only of lowercase English letters.

Print the number of palindromic subsequences of $S$, modulo $10\,007$.