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.
One string s of length no more than 1000.
Print the number of different ways to create the string s from palindromes. Print the answer by the modulo 109+7.