A partition of an integer is a series of positive integers that add up to . For example, given the number 15, a partition could be , which adds up to 15. A palindromic partition is when that series of positive integers is a palindrome. For example, a palindromic partition of the number 15 can be .
To be specific, a palindromic series of integers count the integers as individual characters, so the series 10 + 1 + 10
is a palindrome, and just 21
is also a palindrome.
Given a number , please find the number of different palindromic partitions.
Constraints
Subtask 1 [30%]
Subtask 2 [50%]
Subtask 3 [20%]
Input Specification
One integer .
Output Specification
Output the number of different palindromic partitions.
Sample Input
7
Sample Output
8
Explanation of Sample
The palindromic partitions of are:
7 = 7
7 = 1 + 5 + 1
7 = 2 + 3 + 2
7 = 3 + 1 + 3
7 = 1 + 1 + 3 + 1 + 1
7 = 2 + 1 + 1 + 1 + 2
7 = 1 + 2 + 1 + 2 + 1
7 = 1 + 1 + 1 + 1 + 1 + 1 + 1
In total, there are 8 palindromic partitions.
Comments