Задача B. Компьютерный класс ≡

Условие

В деревенскую школу наконец-то завезли компьютеры! Теперь можно убрать со столов счеты, логарифмические линейки и арифмометры и красиво расставить эти чудеса вычислительной техники.

В компьютерном классе парты стоят вдоль стен, образуя три непрерывных участка: два коротких и один длинный. Всего нужно расставить n компьютеров, соблюдая следующие ограничения:

1) количество компьютеров, расположенных на коротких участках, должно быть равным между собой, то есть если на одном участке b рабочих мест, то и на другом тоже b;

2) количество компьютеров, расположенных на коротком участке, должно быть строго меньше, чем на длинном, то есть если на коротком участке b рабочих мест, то b < a;

3) на каждом участке должен располагаться хотя бы один компьютер.

Помогите учителю информатики определить количество способов расставить все n компьютеров с учетом имеющихся ограничений.

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

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

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

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

4 ≤ n ≤ 10¹⁸

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

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

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

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

В примере дано n = 10.

В первом случае компьютеры можно расставить так: a = 8 и b = 1.

Во втором: a = 6 и b = 2.

В третьем: a = 4 и b = 3.

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

10

3