github.com/captn3m0/codechef.git

---
{"languages_supported":{"0":"NA"},"title":"COUNTPAL","category":"NA","old_version":true,"problem_code":"COUNTPAL","tags":{"0":"NA"},"layout":"problem"}
---

<h3> All submissions for this problem are available. </h3><p>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:<br /> * bobseesanna = bob + sees + anna<br /> * bobseesanna = bob + s + ee + s + anna<br /> * bobseesanna = b + o + b + sees + a + n + n + a<br /> ...<br /> 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.</p>
<h3>Input</h3>
<p>The string s</p>
<h3>Output</h3>
<p>The value of function CountPal(s), taking the modulo of 1 000 000 007 (10<sup>9</sup>+7)</p>
<h3>Limitations</h3>
<p>0 &lt; |s| &lt;= 1000</p>
<h3>Example</h3>
<pre><b>Input:</b>
bobseesanna

<b>Output:</b>
18
</pre>
<p></p>