Palindrome Splitting

Given a string s, return the number of ways to partition the string such that each part is a palindrome.

Constraints

• n ≤ 15 where n is the length of s.

https://binarysearch.com/problems/Palindrome-Splitting

Examples

Example 1

Input

• s = abba

Output

• answer = 3

Explanation

We can have the following splits: ["a", "bb", "a"], ["a", "b", "b", "a"], ["abba"]

Solution