Sets

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 (k) distinct natural numbers, each less than or equal to (n), such that for any natural number (y), at least one of the numbers (y) 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 (m).

Input

The input file contains four integers: (n), (m), (k), (x) ((1 $\le$ n $\le$ 10^18), (2 $\le$ m $\le$ 10^6), (0 $\le$ k $\le$ 1000), (2 $\le$ x $\le$ 10)).

Output

In the output file, print the remainder of the division of the total number of sets, as described, by (m).

Examples