Задача F. Свадебный торт ≡

Условие

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

Сегодня невеста выбирает свадебный торт. Конечно, он должен быть красивым, вкусным и, самое главное, - многоэтажным. Согласно представлениям Тани об идеальном торте, на вершине должен располагаться корж радиуса 1, под ним - корж радиуса a или b, под ним (и каждым следующим) - корж радиусом в a или b раз больше предыдущего. Например, при a = 2 и b = 3 идеальный торт может быть таким: 1-2-6-12-24-... Или таким: 1-3-6-18-36-... Или таким: 1-3-9-27-81-...

Максимальный радиус нижнего коржа торта не может превышать r - в противном случае его невозможно будет вынести из кондитерского цеха. Помогите Тане - посчитайте по известным a, b и r количество идеальных тортов. Естественно, высота каждого такого отдельного торта должна быть максимально возможной, при этом высоты двух различных идеальных тортов могут отличаться. Два торта считаются различными, если перечисление их радиусов не совпадает хотя бы в одной позиции.

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

Первая строка входного файла содержит три натуральных числа, записанных через пробел: a, b и r.

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

Выведите одно натуральное число - ответ на задачу. Гарантируется, что он не превысит 10¹⁵.

Ограничения

2 ≤ a < b < r ≤ 10¹⁸

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

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

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

В примере Таня посчитает идеальными следующие пять тортов:

1-2-4-8.

1-2-4-12.

1-2-6-12.

1-3-6-12.

1-3-9.

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

2 3 12

5