Count palindromes

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 by some 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 by the modulo $10^9+7$.

Examples