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