eolymp
bolt
Try our new interface for solving problems

Три K

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

"Не беспокойтесь о Ваших проблемах с математикой, Уверяю Вас, мои намного больше."

Альберт Эйнштейн

Жители планеты MCA очень любят леденцы. Куша и Кейвин - жители MCA. Но любят они леденцы не больше, чем друг друга. Кеви захватил в качестве трофеев очень много леденцов в войне с жителями планеты ACM. Теперь, как владелец большого количество леденцов, он хочет разделить их между Кушей и Кейвином. Учитывая, что если кто-то один из них съест больше чем 7 леденцов и пострадает от зубной боли, Кеви решил разделить леденцы так, чтобы их количество у каждого не превышало 7. Куша и Кеви доверяют Кейвину в делёже леденцов, так как знают, что каждый из них получит хотя бы один леденец, ну а дружба - дороже леденцов!

Но существует ещё одна проблема, которую тройка друзей должна решить. Куша и Кеви в своей одежде имеют одинаковый запас пакетов для леденцов. И в каждом пакете должно быть одинаковое количество леденцов, иначе их равновесие при ходьбе может нарушится и они не смогут передвигаться.

Например, Кейвин хочет разделить 10 леденцов между Кушей и Кеви, и максимальное количество леденцов, которое может получить каждый равно 7. У каждого есть по два пакета. Тогда существует 2 способа разделить леденцы: Куша получит 4 леденца, а Кеви 6 и наоборот. Если количество любителей леденцов равно 2, то эта задача легко решается, но ТриК (Кейвин, Кеви И Куша) хотят решить эту задачу для любого количества любителей леденцов, любого количества леденцов, любого максимального количества леденцов и любого количества пакетов.

Giriş verilənləri

Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай расположен в отдельной строке, числа в нем разделены пробелом. Первое число m указывает количество леденцов (0 < m60). Второе число n это количество любителей леденцов (0 < nm). Третье число показывает какое максимальное количество леденцов p может получить один человек (0 < pm). Все люди имеют в карманах своей одежды k пакетов (km и m mod k = 0). Люди так любят леденцы, что пакетов у них может быть достаточно много. Для них получение леденцов - это не сюрприз!

Çıxış verilənləri

Для каждой строки, полученной на входе, выведите в отдельной строке одно число, указывающее количество способов разделить леденцы между их любителями.

Nümunə

Giriş verilənləri #1
10 2 7 2
2 1 1 1
Çıxış verilənləri #1
2
0