Chess Tableaux
Consider some partition of an integer number n = m_1 + m_2 + ... + m_k where m_1 ≥ m_2 ≥ ... ≥ m_k. This partition may be illustrated by the Young diagram - n boxes arranged in k rows, where k is the number of terms in the partition. A row representing the number m_i contains m_i boxes. All rows are left-aligned, and sorted from longest to shortest.
Young diagram can be converted to Young tableau by putting integer numbers from 1 to n to boxes, in such a way that the numbers in each row and each column increase from left to right, and from top to bottom, respectively.
The Young tableau is called a chess tableau is after coloring its boxes as on a chessboard (top left box colored black), black boxes contain odd numbers, and white boxes contain even numbers.
Clearly, not every Young diagram can be converted to a chess tableau. For example, none of the two diagrams below can be converted to a chess tableau.
Given n, find the number of partitions of n such that the corresponding Young diagram can be coverted to a chess tableau.
Input
Input file contains n (1 ≤ n ≤ 50).
Output
Output one integer number - the number of partitions of n for which there is a chess tableau.