算协是北大的众多学生社团中的一个。

今天是社团招新的日子，可怜和六花作为负责人， 她们打算在招新现场(三角地)和新生玩一些小游戏。

六花估计在招新现场总共有 $n$ 名新生来这里玩游戏，但是六花并不知道每一个人什么时候会过来玩游戏，因此她假设每一个人到来的时间是 $[0,m]$ 中等概率随机的一个实数。

六花和可怜会和新生玩游戏，由于她们有着优秀的控场水平，每一局游戏都会进行恰好 $k$ 秒。每一名新生到的时候，如果六花和可怜两个人都在进行对局，则他会离开现场，否则他会等概率从六花和可怜中随机一名没有进行游戏的，并且与其开始游戏。不妨假设这位新生在第 $T$ 秒到达，并且和可怜进行了游戏，则可怜在 $[T，T+k)$ 秒处于游戏状态，此时她无法和其余选手进行新的游戏。在第 $0$ 秒开始的时候，六花和可怜没有进行对局。

可怜不希望有新生因为她和六花两人都在对局而离开招新现场。她很好奇，有多大的概率，使得所有新生都成功的进行了一次游戏。由于答案表达式可能非常复杂，你只需要输出对质数 $p$ 取模的结果即可。

输入格式

一行四个正整数 $n,m,k,p$。

输出格式

一行一个数字，表示答案对 $p$ 取模的结果。

具体的，如果答案最简分式为 $\frac{x}{y}$，你只需要输出 $x \times y^{p-2} \bmod p$ 的结果。

出题人保证对于所有数据，最简分式中的分母 $y$ 和 $p$ 互质。

样例数据

样例 1 输入

2 9 8 1000000007

样例 1 输出

1

样例 1 解释

由于只有两名新生，因而不论他们在什么时候到来，Rikka 和 Karen 总有至少一个是有空的。因而不论什么情况下所有新生均成功进行了游戏。

样例 2 输入

4 6 3 998244353

样例 2 输出

873463809

样例 2 解释

答案是 $\frac{1}{8}$

样例 3 输入

7 20 2 998244353

样例 3 输出

591287283

子任务

对于 $10 \%$ 的数据，满足 $n \le 3$

对于 $20 \%$ 的数据，满足 $n \le 4$

对于 $35 \%$ 的数据，满足 $n \le 6$

对于 $50 \%$ 的数据，满足 $n \le 10$

对于 $60 \%$ 的数据，满足 $n \le 15$

对于 $70 \%$ 的数据，满足 $n \le 25$

对于 $80 \%$ 的数据，满足 $n \le 35$

对于 $90 \%$ 的数据，满足 $n \le 45$

对于 $100 \%$ 的数据，满足 $n \le 50$

对于所有测试数据，满足 $1 \le n \le 50, 1\le k \le m \le 150, 10^8 < p \le 10^9+9$。