我们考虑集合 $\{1, \ldots, n\}$ 的子集 $P$。我们感兴趣的子集需满足：对于给定的自然数 $x > 1$，对于任意自然数 $y$，数字 $y$ 和 $x \cdot y$ 中至少有一个不属于 $P$。我们希望计算满足该条件的恰好包含 $k$ 个元素的子集数量。由于该数量可能非常巨大，因此只需计算结果除以 $m$ 的余数。

编写一个程序：

• 从标准输入读取四个整数：$n$、$m$、$k$ 和 $x$；
• 计算集合 $\{1, \ldots, n\}$ 中满足上述要求的 $k$ 元子集数量除以 $m$ 的余数；
• 将结果写入标准输出。

输入格式

标准输入的第一行也是唯一一行包含四个整数 $n$、$m$、$k$ 和 $x$（$1 \le n \le 10^{18}$，$2 \le m \le 1\,000\,000$，$0 \le k \le 1\,000$，$2 \le x \le 10$），以空格分隔。

输出格式

第一行也是唯一一行应包含一个整数，即满足指定要求的 $k$ 元子集数量除以 $m$ 的余数。

样例

输入

6 1234 3 2

输出

9

说明

符合条件的子集为：{1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {1, 4, 6}, {1, 5, 6}, {2, 3, 5}, {2, 5, 6} 和 {4, 5, 6}。