Sets#4306
To allocate participants of the Vekua Cup into rooms, a multi-parameter lottery system is being devised. Your task is to develop a module for this system that determines the lottery parameters.
Given a natural number x > 1, construct all sets consisting of distinct natural numbers, each less than or equal to , such that for any natural number , at least one of the numbers or x \cdot y is not included in the set. Your task is to calculate the remainder when the total number of such sets is divided by a given natural number .
The input file contains four integers: , , , (1 \leq n \leq 10^{18}, 2 \leq m \leq 10^6, 0 \leq k \leq 1000, 2 \leq x \leq 10).
In the output file, print the remainder of the division of the total number of sets, as described, by .
Example 1