Множини#4306
Для розподілення учасників Кубку Векуа по аудиторіях розробляється система багатопараметричного жеребкування. Вам дісталась задача написати для системи окремий модуль, який використовується для визначення параметрів жеребкування.
Для заданого натурального x > 1 побудуємо усі множини, які складаються з різних натуральних чисел, менших або рівних , такі, що для довільного натурального числа як мінімум одне з чисел та x \cdot y не належить даній множині. Ваша задача — обчислити залишок від ділення загальної кількості таких множин на задане натуральне число .
У вхідному файлі записано чотири цілі числа , , , (1 \leq n \leq 10^{18}, 2 \leq m \leq 10^6, 0 \leq k \leq 1000, 2 \leq x \leq 10).
У вихідний файл виведіть залишок від ділення загальної кількості описаних у умові множин на .
Приклад 1