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

...

We want to take the value of function CountPal(s) which is the number of different ways to use the palindromes to create the string s by the above method.

------ Input ------

The string s

------ Output ------

The value of function CountPal(s), taking the modulo of 1 000 000 007 (10^{9}+7)

------ Limitations ------

0 < |s| ≤ 1000

----- Sample Input 1 ------
bobseesanna
----- Sample Output 1 ------
18

见题面

见题面