Підмножина сум
Для багатьох наборів послідовних цілих чисел від 1 до n, можна розбити цю множину на дві підмножини так, що суми їх елементів співпадають.
Наприклад, якщо n = 3, то можна зробити наступне розбиття множини {1, 2, 3} на підмножини так, що їх суми будуть ідентичні:
{3} и {1, 2}
Це вважається одним розбиттям (тобто аналогічне розбиття у зворотному порядку вважається як одне розбиття і, відповідно, не збільшить кількості розбиттів).
Якщо n = 7, то існує чотири способи розбиття множини {1, 2, 3, ..., 7} таких, що кожне розбиття має одну і ту ж суму:
{1, 6, 7} та {2, 3, 4, 5}
{2, 5, 7} та {1, 3, 4, 6}
{3, 4, 7} та {1, 2, 5, 6}
{1, 2, 4, 7} та {3, 5, 6}
Для заданого n необїідно вивести кількість способів розбиття множини, яка містить усі цілі числа від 1 до n на дві групи так, що суми елементів підмножин співпадають. Вивести 0, якщо таких способів немає.
Вхідні дані
Ціле число n (1 ≤ n ≤ 39).
Вихідні дані
Кількість способів, якими можна здійснити розбиття заданої множини {1, 2, ..., n} на дві підмножини таким чином, що суми елементів цих підмножин будуть однакові. Вивести 0, якщо необхідного розбиття не існує.