All problems

Mirror Charm Cuts

Medium · dynamic programming

A jeweller has a strip of lettered tiles, written as the string s. They want to saw it into exactly k charms: k non-empty pieces of consecutive tiles that together cover the whole strip, in order.

A charm is a mirror charm if its letters read the same from left to right as from right to left. A single tile is always a mirror charm.

Return the number of different ways to saw s into exactly k pieces so that every piece is a mirror charm, modulo 10^9 + 7. Two ways are different if the cuts are in different places. If there is no way, return 0.

Examples

Example 1

Input: s = "aab", k = 2

Output: 1

Cut after the second tile to get "aa" and "b", both mirror charms. Cutting after the first tile gives "a" and "ab", and "ab" is not a mirror charm.

Example 2

Input: s = "aaa", k = 2

Output: 2

Cut into "a" and "aa", or into "aa" and "a". Every piece is a mirror charm in both.

Example 3

Input: s = "abc", k = 2

Output: 0

Neither "ab" nor "bc" is a mirror charm, so no cut into two pieces works.

Constraints

• 1 <= len(s) <= 50
• s contains only lowercase letters
• 1 <= k <= len(s)