Шахові Таблиці

Розгляньмо розподіл цілого числа n = m_1 + m_2 + ... + m_k, де m_1 \ge m_2 \ge ... \ge m_k. Цей розподіл можна зобразити за допомогою діаграми Юнга - $n$ клітинок, розташованих у $k$ рядках, де $k$ - це кількість доданків у розподілі. Рядок, що відповідає числу m_i, містить m_i клітинок. Усі рядки вирівняні по лівому краю та впорядковані від найдовшого до найкоротшого.

Діаграму Юнга можна перетворити на таблицю Юнга, заповнивши клітинки цілими числами від $1$ до $n$ так, щоб числа в кожному рядку та кожному стовпці зростали зліва направо та зверху вниз відповідно.

Таблиця Юнга називається шаховою таблицею, якщо після зафарбовування її клітинок як на шаховій дошці (верхня ліва клітинка зафарбована в чорний колір), чорні клітинки містять непарні числа, а білі клітинки містять парні числа.

Очевидно, що не кожну діаграму Юнга можна перетворити на шахову таблицю. Наприклад, жодну з двох діаграм нижче не можна перетворити на шахову таблицю.

Дано $n$, знайдіть кількість розподілів $n$, для яких відповідна діаграма Юнга може бути перетворена на шахову таблицю.