Count palindromes#11592

Count palindromes

1 second

128 megabytes

Medium

Each palindrome can be always created from the other palindromes, if a single character is also a palindrome. For example, the string "bobseesanna" can be created in several ways:

bobseesanna = bob + sees + anna
bobseesanna = bob + s + ee + s + anna
bobseesanna = b + o + b + sees + a + n + n + a
...

Find the number of different ways to create the string $s$ from palindromes.

Input

One string $s$ of length no more than $1000$ .

Output

Print the number of different ways to create the string $s$ from palindromes. Print the answer modulo $1 0^{9} + 7$ 10^9 + 7.

Examples

Example 1

Loading

1 0^{9} + 7