Шахматные Таблицы
Рассмотрим разбиение целого числа n = m_1 + m_2 + ... + m_k, где m_1 ≥ m_2 ≥ ... ≥ m_k. Такое разбиение можно представить с помощью диаграммы Юнга — это n ячеек, расположенных в k строках, где k — количество слагаемых в разбиении. Строка, соответствующая числу m_i, содержит m_i ячеек. Все строки выровнены по левому краю и упорядочены от самой длинной к самой короткой.
Диаграмма Юнга может быть преобразована в табло Юнга путем размещения чисел от 1 до n в ячейки так, чтобы числа в каждой строке и каждом столбце увеличивались слева направо и сверху вниз соответственно.
Табло Юнга называется шахматным табло, если после раскраски его ячеек как на шахматной доске (верхняя левая ячейка черная), черные ячейки содержат нечетные числа, а белые ячейки содержат четные числа.
Очевидно, не каждая диаграмма Юнга может быть преобразована в шахматное табло. Например, ни одна из двух диаграмм ниже не может быть преобразована в шахматное табло.
Дано n, найдите количество разбиений n, таких что соответствующая диаграмма Юнга может быть преобразована в шахматное табло.
Входные данные
Входной файл содержит n (1 ≤ n ≤ 50).
Выходные данные
Выведите одно целое число — количество разбиений n, для которых существует шахматное табло.