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