Для распределения участников Кубка Векуа по аудиториям разрабатывается система многопараметрической жеребьёвки. Вам досталась задача написать для системы отдельный модуль, используемый для определения параметров жеребьёвки. Для заданного натурального \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}.