Шахові Таблиці
Розгляньмо розподіл цілого числа 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, для яких існує шахова таблиця.