부분집합

집합 $\{1, 2, \ldots, n\}$ 과 $1$ 보다 큰 정수 $x$ 가 주어진다. 이 집합의 부분집합 $P$ 중에서 다음 성질을 만족하는 것을 생각하자: 모든 자연수 $y$ 에 대해 $y$ 와 $x \cdot y$ 가 동시에 $P$ 에 속하지는 않는다. 즉, 어떤 $y$ 를 잡더라도 $y$ 와 $x \cdot y$ 중 적어도 하나는 $P$ 에 들어 있지 않아야 한다.

이 조건을 만족하면서 원소가 정확히 $k$ 개인 부분집합의 개수를 구하라. 이 개수는 매우 클 수 있으므로, 그 값을 $m$ 으로 나눈 나머지를 출력한다.

한 줄에 네 정수 $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$

조건을 만족하는 원소 $k$ 개짜리 부분집합의 개수를 $m$ 으로 나눈 나머지를 한 줄에 출력한다.

$n = 6$, $k = 3$, $x = 2$ 인 경우 조건을 만족하는 부분집합은 다음 $9$ 개이다: $\{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\}$.