Задача D. Баба Яга и волшебные часы ≡

Условие

Говорят, что у Бабы Яги есть волшебные механические часы, висящие напротив печки. Поскольку время в Зачарованном лесу идет не так, как на остальной земле, циферблат часов разбит на n секторов, обозначенных числами от 1 до n.

И если разбить циферблат часов мечом-кладенцом на две части таким образом, чтобы суммы чисел на обеих частях были равны, то лишится Баба Яга всей своей магической силы. Да вот только возможно ли это?

Формат входных данных

Единственная строка входного файла содержит натуральное число n.

Формат выходных данных

Выведите одно неотрицательное целое число — количество различных способов разбиения циферблата часов отрезком на две части с равной суммой чисел.

Ограничения

2 ≤ n ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 12, получат не менее 20 баллов.

Решения, верно определяющие, при каких n ответ гарантированно будет равен нулю, получат не менее 20 баллов.

Решения, верно работающие при n ≤ 500, получат не менее 60 баллов.

Пояснение к примерам

В первом примере дано n = 3. В одной части останутся числа 1 и 2, в другой — 3. Суммы равны, других решений нет.

Во втором примере n = 5. Нет никаких способов разбить набор чисел от 1 до 5 на две равные по сумме части.

Во третьем примере n = 8. Есть два решения:

Первое: 3, 4, 5 и 6 по одну сторону отрезка и 7, 8, 1 и 2 по другую.

Второе: 5, 6 и 7 по одну сторону отрезка и 8, 1, 2, 3 и 4 по другую. Во всех случаях суммы чисел равны 18.

Примеры тестов

3

1

5

0

8

2