A partition of an integer ~N~ is a series of positive integers that add up to ~N~. For example, given the number 15, a partition could be ~1 + 2 + 3 + 4 + 5~, 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 ~3 + 9 + 3~.

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 ~N~, please find the number of different palindromic partitions.

Constraints

Subtask 1 [30%]

~1 \le N \le 10~

Subtask 2 [50%]

~1 \le N \le 50~

Subtask 3 [20%]

~1 \le N \le 63~

Input Specification

One integer ~N~.

Output Specification

Output the number of different palindromic partitions.

Sample Input

7

Sample Output

8

Explanation of Sample

The palindromic partitions of ~7~ 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.