В деревенскую школу наконец-то завезли компьютеры! Теперь можно убрать со столов счеты, логарифмические линейки и арифмометры и красиво расставить эти чудеса вычислительной техники.
В компьютерном классе парты стоят вдоль стен, образуя три непрерывных участка: два длинных и один короткий. Всего нужно расставить n компьютеров, соблюдая следующие ограничения:
1) количество компьютеров, расположенных на длинных участках, должно быть равным между собой, то есть если на одном участке a рабочих мест, то и на другом тоже a;
2) количество компьютеров, расположенных на коротком участке, должно быть строго меньше, чем на длинном, то есть если на коротком участке b рабочих мест, то b < a;
3) на каждом участке должен располагаться хотя бы один компьютер.
Помогите учителю информатики определить количество способов расставить все n компьютеров с учетом имеющихся ограничений.
Формат входных данных
Единственная строка входного файла содержит натуральное число n.
Формат выходных данных
Выведите одно неотрицательное целое число — ответ на вопрос задачи.
Ограничения
1 ≤ n ≤ 1018
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 105, получат не менее 40 баллов.
Пояснение к примеру
В примере дано n = 20.
В первом случае компьютеры можно расставить так: a = 9 и b = 2.
Был у Татьяны Владимировны любимый методический приём: если до конца урока оставалось несколько свободных минут, рассказывала она ребятам несложную математическую историю, а её четвероклассники должны были определить, могло ли это произойти на самом деле, или учительница их обманывает.
"Был у меня квадрат, — начала очередной рассказ Татьяна Владимировна. — Разрезала я его вдоль сторон на n квадратов со стороной a и m единичных квадратов (то есть квадратов со стороной 1). Могло ли такое быть?"
Задумались ребята, вычисляют, стараются. А Вы разгадаете эту загадку?
Формат входных данных
Три строки входного файла содержат три натуральных числа: n, a и m.
Формат выходных данных
Выведите "Yes" или "No" (без кавычек) — ответ на вопрос задачи.
Ограничения
1 ≤ n ≤ 10
2 ≤ a ≤ 10
1 ≤ m ≤ 100
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
В первом примере дано n = 4, a = 3 и m = 45. На рисунке приведен один из примеров разрезания квадрата со стороной 9 на указанные части.
Во втором примере не существует квадрата который можно было бы разрезать указанным образом.
Тимофей, как и любой другой нормальный дошкольник, не любит ложиться спать. Чтобы отсрочить неизбежное, он старается задать папе побольше разнообразных вопросов. Сегодня речь зашла о времени.
Больше всего Тимофея заинтересовало, откуда взялись числа 24, 60 и 60 в качестве количества часов в сутках, минут в часах и секунд в минуте. Когда папа, как мог, удовлетворил любопытство мальчика рассказом о шестидесятеричной системе счисления, тот задал новый вопрос — возможно ли выбрать другие числа? Папа ответил: "Да, конечно! Тебе какие нужны?" Тимофей захотел выбрать такие три числа, чтобы они "не сильно отличались". Тут папе пришлось задуматься...
В сутках на некоторой планете ровно n секунд. Представьте это число в виде произведения трех натуральных чисел, чтобы разность между наибольшим и наименьшим из них была минимальной.
Формат входных данных
Единственная строка входного файла содержит натуральное число n.
Формат выходных данных
Выведите через пробел в порядке не убывания три натуральных числа — ответ на вопрос задачи. Гарантируется, что искомая тройка чисел — единственная.
Ограничения
1 ≤ n ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 1000, получат не менее 40 баллов.
Пояснения к примерам
В первом примере дано n = 86400 (соответствует количеству секунд в земных сутках). Помимо традиционного разбиения 86400 = 24 × 60 × 60 можно найти еще, например 86400 = 4 × 100 × 216 или 86400 = 10 × 10 × 864 и так далее. Но самым оптимальным по признаку "чтобы не сильно отличались" будет разбиение, приведенное в ответе. Разность между наибольшим и наименьшим множителями равна 8.
Во втором примере миллион раскладывается в произведение трех равных чисел, интересующая Тимофея разность равна нулю.
