D. Блокнот
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
64 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Никиту привлекает всё нестандартное. Даже десятичная система ему больше не нравится, так что он решил изучить другие системы счисления. Его внимание привлекла система счисления с основанием b. Для начала её изучения он хочет записать в свой блокнот все числа длины n без ведущих нулей в этой системе счисления. На каждом листе бумаги в его блокноте достаточно места для написания ровно c чисел. Никита записывает каждое подходящее число ровно один раз, начиная с первого чистого листа бумаги и не оставляя на листах свободного места. Никита никогда не выпишет число 0, так как с ним у него связаны плохие воспоминания о делении чисел.

Помогите Никите выяснить, сколько чисел будет записано на последнем листе бумаги.

Входные данные

Единственная строка входных данных будет содержит три целых числа b, n и c записанные через пробел (2 ≤ b < 10106, 1 ≤ n < 10106, 1 ≤ c ≤ 109). Вы можете полагать, что у Никиты есть бесконечный запас терпения, листов бумаги и представлений цифр в виде символов. Числа не содержат ведущих нулей.

Выходные данные

В единственной строке выходных данных выведите количество чисел, записанных на том листе бумаги, на котором будет записано последнее число.

Примеры
Входные данные
2 3 3
Выходные данные
1
Входные данные
2 3 4
Выходные данные
4
Примечание

В обоих примерах существует ровно 4 числа длины 3 в двоичной системе счисления. В первом примере Никита запишет 3 числа на первом листе бумаги и 1 число на втором. Во втором примере все 4 числа поместятся на один лист бумаги.