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