Рабочее место участника

Страннику необходимо определить, каким образом можно установить уличные фонари на проспекте Неизвестных Отцов, застроенного одинаковыми типовыми домиками. Дома стоят с одной стороны проспекта и имеют последовательные номера с `A` до `B`. Обитатели Саракша имеют особое "счастливое" число `N` для всех работ, связанных с электричеством. Поэтому на проспекте нужно установить ровно `N` фонарей, каждый фонарь нужно установить у одного из домов, на равном расстоянии друг от друга, сумма номеров домов, у которых стоят фонари, должна без остатка делиться на `N`. Пусть дома на проспекте имеют номера от 1 до 10, и "счастливым" является число 4. Можно поставить фонари у домов 1, 4, 7 и 10, но сумма номеров этих домов (равная 22) не будет делиться на 4. Условиям соответствуют только следующие 4 способа: 1-3-5-7, 2-4-6-8, 3-5-7-9 и 4-6-8-10.

Напишите программу, которая позволит Страннику вычислить количество способов расстановки фонарей на проспекте, соответствующих всем указанным условиям.

Первая строка ввода содержит три целых числа - номера первого и последнего дома на проспекте `A` и `B` (`1 ≤\ A\ ≤\ B\ ≤\ 10^9`) и "счастливое" число `N` (`1\ ≤\ N\ ≤\ 10^9`).

Вывести одно целое число – количество способов провести освещение на проспекте.

1 10 4

4