Counting Palindromic Subsequences (Large)

Time limit2sMemory limit512 MB

Summary

Count subsequences of a string (positions distinguish repeats) that read as palindromes, modulo 10007.

Level: Medium7 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Problem

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.

Input

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

Output

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

Examples1

Example 1
Input
```
abb
```
Expected output
```
4
```