题目描述

有两个人要和 $n$ 个小朋友进行游戏，每个小朋友到达的时刻是在 $[0, m]$ 中等概率随机选择的一个实数。

一个人不能同时和两个小朋友进行游戏。如果一个小朋友到达的时候两个人都在进行游戏，那么这个小朋友就会不开心；否则他就会等概率随机选择一个不在进行游戏的人，并和他进行游戏。

在时刻 $t$ 前来的小朋友，在时间段 $[t, t + k)$ 都会进行游戏。

求没有小朋友不开心的概率。对质数 $p$ 取模，保证答案的分母不是 $p$ 的倍数。

输入格式

一行四个整数 $n, k, m, p$ 含义如上。

输出格式

一行一个整数表示答案。

样例

input1

2 3 4 99844353 

output1

1

input2

10 3 4 1000000007 

output2

0

input3

4 3 6 1000000007

output3

125000001

数据范围与提示

对于 20% 的数据满足 $n ≤ 3$。

对于另外 50% 的数据满足 $n ≤ 10$。

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

数据有梯度。