A heraldic banner is a strip of lowercase letters. A herald cuts it into exactly k consecutive non-empty pieces, each of which must read the same forward and backward (a palindrome).
Count the number of distinct ways to cut the strip into exactly k palindromic pieces. Two ways differ if they cut at a different set of positions.
Input format
Line 1: the string s of lowercase English letters.
Line 2: the integer k.
Output format
A single integer: the number of ways to partition s into exactly k palindromic pieces.
Constraints
- 1 <= length of s <= 20
- 1 <= k <= 20
- All characters are lowercase English letters.