An emblem is encoded as a string of lowercase letters. Count the number of DISTINCT non-empty subsequences of the string that are palindromes. Two palindromic subsequences are considered the same if they spell the identical string (regardless of which positions were chosen), so each distinct palindrome string is counted once. Because the count can be large, output it modulo 1000000007.
Input format
Line 1: the emblem string s.
Output format
A single integer: the number of distinct non-empty palindromic subsequences, modulo 1000000007.
Constraints
- 1 <= length of
s<= 40 sconsists of lowercase English letters only.