Задача E. Erasing numbers ≡

Условие

В Научно-исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день его коллеги открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать. Сегодня Тимофей, как обычно, выписал на доске в ряд натуральные числа от 1 до n и пытается ответить на вопрос, возможно ли стереть в середине списка несколько (не менее одного) чисел, идущих подряд, чтобы сумма оставшихся чисел слева равнялась сумме оставшихся чисел справа?

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

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

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

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

Ограничения

3 ≤ n ≤ 10⁵

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

В первом примере дано n = 5. Перечислим все способы стереть числа в середине ряда:

• 1 # 3 4 5
• 1 2 # 4 5
• 1 2 3 # 5
• 1 # # 4 5
• 1 2 # # 5
• 1 # # # 5

Ни в одном из них нужное свойство не достигается.

Во втором примере дано n = 21. Перечислим все хорошие способы стереть числа в середине ряда:

• 1 2 3 4 5 6 # # # ## ## ## ## ## ## ## ## ## ## ## 21
• 1 2 3 4 5 6 7 8 9 10 11 12 ## ## ## ## ## 18 19 20 21

В первом списке сумма чисел слева и справа равны 21, во втором — 78. Всего два способа.

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

5

0

21

2