简单的普及组计数 (counting)

对于一个字符集 $\Sigma$ 上的字符串 $S$ 和常数 $k$，定义删去 $S$ 中的 $k$ 个相邻且相同的字符为一次操作。

现字符集的大小 $|\Sigma| = m$. 试求 $\Sigma$ 上能通过 $n$ 次操作得到空串的字符串数量。答案对质数 $p$ 取模。

比如字符集 $\Sigma = \{\text{a}, \text{b}, \text{c}\}$ 时 且 $k = 2$ 时，$\text{abbcca}$ 符合上述条件而 $\text{abbca}$ 不符合。

输入格式 (counting.in)

一行，四个正整数 $n$, $m$, $k$, $p$，用空格分隔。

输出格式 (counting.out)

一行，一个非负整数，符合条件的字符串个数对 $p$ 取模的结果。

样例输入

3 3 2 99991

样例输出

87

数据规模与子任务

对于所有数据，$1 \leq n, k \leq 10^9$, $1 \leq m < p < 10^5$, $p$ 是素数。

Subtask 1 ($10$ pts): $n \leq 3000, k = 2$；

Subtask 2 ($10$ pts): $n \leq 2 \times 10^5, k = 2$；

Subtask 3 ($10$ pts): $n \leq 5 \times 10^6$, $k = 2$;

Subtask 4 ($10$ pts): $k = 2$;

Subtask 5 ($10$ pts): $n \leq 3000$;

Subtask 6 ($10$ pts): $n \leq 2 \times 10^5$;

Subtask 7 ($10$ pts): $n \times k \leq 10^7$;

Subtask 8 ($30$ pts): 无特殊限制。

TL: $2s$

ML: $256MB$

提示

这是一道水题。