226. Palindrome Partitioning (Count)

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

Input: A quoted string s.

Output: Integer — number of palindrome partitionings.

Examples

Example 1

Input: "aab"
Output: 2
Explanation: ['a','a','b'] and ['aa','b'].

Example 2

Input: "a"
Output: 1
Explanation: ['a'].

Example 3

Input: "abc"
Output: 1
Explanation: Only all-singletons.