A mosaic band is a string s of lowercase English letters. You may split it into contiguous pieces in any way (each cut lands between two adjacent letters). A split is valid if every piece is a palindrome (reads the same forward and backward).
Count the number of valid splits. Two splits are different if their sets of cut positions differ. Because the count can be large, output it modulo 1000000007.
A single line containing the string s (lowercase English letters only).
A single integer: the number of valid palindromic splits, modulo 1000000007.
s <= 2000s contains only lowercase English letters (a-z).Example 1
Input
aab
Expected
2
Explanation
The valid splits are 'a|a|b' and 'aa|b', so the count is 2.
Example 2
Input
aaa
Expected
4
Explanation
Every contiguous run of 'a' is a palindrome, so all 4 splits ('a|a|a', 'aa|a', 'a|aa', 'aaa') are valid: 4.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →