Məsələlər
Множества
Множества
Для распределения участников Кубка Векуа по аудиториям разрабатывается система многопараметрической жеребьёвки. Вам досталась задача написать для системы отдельный модуль, используемый для определения параметров жеребьёвки.
Для заданного натурального \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}.
Giriş verilənləri #1
6 1234 3 2
Çıxış verilənləri #1
9