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