Subsets

You are given the set $\{1, 2, \ldots, n\}$ and an integer $x$ with $x > 1$. Consider the subsets $P$ of this set with the following property: for every natural number $y$, the numbers $y$ and $x \cdot y$ are never both in $P$ at the same time. In other words, for any $y$, at least one of $y$ and $x \cdot y$ is missing from $P$.

Count how many such subsets contain exactly $k$ elements. This number can be very large, so output its remainder modulo $m$.

A single line contains four integers $n$, $m$, $k$, and $x$, separated by single spaces.

• $1 \le n \le 10^{18}$
• $2 \le m \le 10^6$
• $0 \le k \le 1000$
• $2 \le x \le 10$

Print, on a single line, the number of $k$-element subsets satisfying the condition, taken modulo $m$.

For $n = 6$, $k = 3$, and $x = 2$, the $9$ subsets that satisfy the condition are: $\{1, 3, 4\}$, $\{1, 3, 5\}$, $\{1, 4, 5\}$, $\{1, 4, 6\}$, $\{1, 5, 6\}$, $\{2, 3, 5\}$, $\{2, 5, 6\}$, $\{3, 4, 5\}$, $\{4, 5, 6\}$.