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. InputThe string s Output

The value of function CountPal(s),

taking the modulo of 1 000 000 007

(10^{9}+7)Limitations

0 < |s| <= 1000 Example

Input: bobseesanna

Output: 18

I’ve been struggling through this problem for quite a few days. I know it must be DP but somehow I couldn’t find a way to formalize the recursive formula. The only thing I have so far is for the base case, when the length of the string is 1, then there is only one way. Could anyone help me understand this problem? I really don’t want to look at the solution because by doing that I won’t learn anything. Any suggestion or idea would be greatly appreciated.