Chess Tableaux#3443

Chess Tableaux

1 second

64 megabytes

Very hard

Consider some partition of an integer number $n = m_{1} + m_{2} + \dots + m_{k}$ n = m_1 + m_2 + \ldots + m_k where $m_{1} \geq m_{2} \geq \dots \geq m_{k}$ m_1 \ge m_2 \ge \ldots \ge 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}$ m_i contains $m_{i}$ 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 if 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 converted to a chess tableau.

Input

Input file contains $n$ ( $1 \leq n \leq 50$ 1 \le n \le 50).

Output

Output one integer number - the number of partitions of $n$ for which there is a chess tableau.

Examples

Example 1

Loading

n = m_{1} + m_{2} + \dots + m_{k}

m_{1} \geq m_{2} \geq \dots \geq m_{k}

m_{i}

m_{i}

1 \leq n \leq 50