@RomanZemin

Легкий троллинг 2
Тролль Зумбагеш одинок. У него есть прямоугольная шоколадка, разделенная на n x m долек и огромное желание завести друзей. Он развесил объявления о поиске друзей (да-да, совсем как Чебурашка с Крокодилом Геной) и решил всех приходящих угощать шоколадом.

Его объявлениями заинтересовалось k троллей. Они приходят к Зумбагешу по очереди и беседуют с ним. На прощание Зумбагеш разламывает свою шоколадку по одной из линий на два куска и отдает один из кусков будущему другу, а второй оставляет себе. С оставленным себе куском он повторяет эту операцию для следующего гостя. Будучи натурой широкой и щедрой, он ломает шоколад так, чтобы отдать посетителю как можно больший кусок. Если разломить по линиям уже не получается, то он отдает оставшуюся дольку последнему другу и заканчивает прием посетителей.

Требуется выяснить, сколько друзей будет у Зумбагеша, если все, с кем он поделился шоколадкой, стали его друзьями.

Input format
Через пробел записаны три числа n, m, k. Все числа в пределах от 1 до 1018 включительно.

Output format
Вывести одно число — количество друзей, которые появятся у Зумбагеша.

Examples
Input Output
1 2 3
2
Notes
Методика проверки
При тестировании задачи выделяются следующие группы тестов:

n, m, k ≤ 10 (20 баллов)
n, m, k ≤ 109 (30 баллов)
Без ограничений к условию задачи. (50 баллов).
Баллы за группу тестов начисляются только в случае прохождения проверяемой программой всех тестов группы.

0