Apartitionof a positive integerNis a sequence of integers which sum toN, usually written with plus signs between the numbers of the partition. For example

15 = 1+2+3+4+5 = 1+2+1+7+1+2+1

A partition ispalindromicif it reads the same forward and backward. The first partition in the example isnotpalindromic while the second is. If a partition containingmintegers is palindromic, its left half is the firstfloor(m/2)integers and its right half is the lastfloor(m/2)integers (which must be the reverse of the left half. (floor(x)is the greatest integer less than or equal tox.)

A partition isrecursively palindromicif it is palindromic and its left half is recursively palindromic or empty. Note that every integer has at least two recursively palindromic partitions one consisting of all ones and a second consisting of the integer itself. The second example above is also recursively palindromic.

For example, the recursively palindromic partitions of 7 are:

7, 1+5+1, 2+3+2, 1+1+3+1+1, 3+1+3, 1+1+1+1+1+1+1

Write a program in Java which takes as input an integerNand outputs the number of recursively palindromic partitions ofN.