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