Задача D. Новая школа ≡

Условие

Как похорошела школа при новом директоре! В классах заменили старые деревянные рамы на новые стеклопакеты, на месте разбитого стадиона раскинулось современное футбольное поле с трибунами и беговыми дорожками, в столовой полностью заменили ржавое оборудование, восстановлена теплица и даже принят на работу непьющий трудовик! Особенно довольны учителя информатики — теперь все их кабинеты (в полном соответствии с санитарными нормами) светлые, просторные и имеют лаборантские комнаты. Ведь когда школа только проектировалась, о таком учебном предмете даже не знали, вот и приходилось кабинеты информатики размещать где только можно — в бывшей библиотеке, например... Новый директор все учебные кабинеты перетасовал, какие-то объединил, какие-то разделил. В результате — красота и порядок: на каждом из n школьных этажей ровно k учебных кабинетов.

Естественно, пришлось менять и нумерацию кабинетов. Поступили просто: номер каждого кабинета состоит из двух частей, разделенных дефисом, первым идет номер этажа, вторым — номер кабинета на этаже. Например "3 − 14" — всем сразу ясно, что это 14-й кабинет на третьем этаже. Садись на лифт и поднимайся. Я же про лифты упоминал? Нет? Теперь и лифты тоже есть.

Единственное, что смазало начало нового учебного года — в электронном расписании занятий не отображается разделитель, совсем, как будто его и не было, сразу за номером этажа идет номер кабинета, без разделителя ("314"). Теперь ребятам и учителям приходится бегать по коридорам в поисках "своего" кабинета для занятий... Но системный администратор уже в курсе проблемы и скоро все будет в порядке. А пока попробуйте ответить на вопрос — сколько школьных аудиторий может быть одинаковым образом закодировано данным номером?

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

Первая строка входного файла содержит два натуральных числа, записанных через пробел: n и k — количество этажей в школьном здании и кабинетов на каждом этаже. Во второй строке приведено натуральное число m — номер без разделителя.

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

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

Ограничения

1 ≤ n, k ≤ 10⁹

11 ≤ m ≤ 10¹⁸

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

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

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

В первом примере есть два подходящих варианта: "3 − 14" и "31 − 4".

Во втором примере лишь один подходящий вариант: "10 − 24". Вариант "1 − 024" невозможен — номер кабинета на этаже не может начинаться с нуля, а вариант "102 − 4" не подходит потому, что в здании школы всего 50 этажей.

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

100 100
314

2

50 50
1024

1