Подмножество сумм
Набор последовательных целых чисел от 1 до n (1 ≤ n ≤ 39) можно разбить на два подмножества так, чтобы суммы их элементов совпадали.
Например для 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, если требуемого разбиения не существует.