Задача 75. Строгий капрал ≡

Условие

...

Пехота топчется в пыли,

Капрал орет: "Рубай, коли!",

А мы хотим рубать компот!

Капрал, голубчик, не ори,

Ты отпусти меня к Мари,

Пока еще девчонка ждет.

А впрочем, черт тебя дери,

Не отпускай меня к Мари,

А через восемьдесят лет

Тебе, капрал, за долгий труд

Штаны с лампасами сошьют,

А может быть, и нет?!

...

Михаил Танич, "Как хорошо быть генералом" ("Строгий капрал"), 1969 г.

Видеоклип

У капрала в роте ровно 2ⁿ солдат. Во время строевых занятий он выстраивает их по росту в порядке возрастания (глаз у него намётанный, он всегда может определить, кто из двух солдат выше). После этого, капрал отдаёт одну их двух команд:

«Первые номера — вперёд!». Солдаты рассчитываются на первый-второй, после чего первые становятся в начало шеренги (в том же порядке по отношению друг к другу, что и перед этим), а после них становятся вторые (тоже сохраняя своё взаимное расположение). Например, солдаты, стоящие в порядке 12345678, после такой команды становятся в порядке 13572468.

«Вторые номера — вперёд!». Команда аналогична предыдущей, только в начало шеренги становятся вторые номера, а потом — первые. Солдаты, стоящие в порядке 12345678, после такой команды становятся в порядке 24681357.

Если вдруг получается так, что после выполнения одной из этих команд солдаты снова выстраиваются в порядке возрастания роста, тогда капрал испытывает тихую радость. Однажды на занятиях произошла такая история: капрал, как обычно, выстроил солдат по росту и отдал a команд «Первые номера — вперёд!». После перерыва он снова выстроил солдат по росту и отдал b команд «Вторые номера — вперёд!». Сколько раз радовался капрал?

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

В единственной строке записаны три натуральных числа n, a и b.

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

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

Ограничения

1 ≤ n, a, b ≤ 10⁹.

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

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

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

3 10 15

5