A banner is woven as a single strip of lowercase letters. A tailor wants to cut the strip into consecutive non-empty pieces so that every piece reads the same forward and backward (a palindrome).
Count the number of distinct ways to cut the strip into palindromic pieces. Two ways differ if they cut at a different set of positions.
Input format
A single line: a string s of lowercase English letters.
Output format
A single integer: the number of ways to partition s into palindromic pieces.
Constraints
- 1 <= length of s <= 20
- All characters are lowercase English letters.