A mosaic band is a string s of lowercase English letters. You may split it into contiguous pieces in any way (each cut lands between two adjacent letters). A split is valid if every piece is a palindrome (reads the same forward and backward).
Count the number of valid splits. Two splits are different if their sets of cut positions differ. Because the count can be large, output it modulo 1000000007.
Input format
A single line containing the string s (lowercase English letters only).
Output format
A single integer: the number of valid palindromic splits, modulo 1000000007.
Constraints
- 1 <= length of
s<= 2000 scontains only lowercase English letters (a-z).