对于长度为 $ n $ 的序列 $ a $，定义 $ f(a)=\dfrac{1}{\prod\limits_{i=k}^ns_i} $，其中 $ s_i $ 为 $ \{a_n\} $ 的前缀和数组，$ k $ 是给定的常数且 $ 1\le k\le 2 $。
考虑所有满足以下三个条件的序列 $ a $：
- $ a $ 的长度为 $ n $。
- $ \forall i,j $，$ a_i\ne a_j $。
- $ 1\le a_i\le m $。
求它们的 $ f(a) $ 之和，答案对 $ p $ 取模。保证 $ p $ 是一个质数。
输入格式
第一行三个整数 $ n,m,k,p $，分别代表序列长度，序列元素的上界和模数。
输出格式
一行一个整数表示答案对 $ p $ 取模后的结果。
样例
输入样例 1
2 3 2 1000000007
输出样例 1
966666675
输入样例 2
3 5 2 998244353
输出样例 2
148276980
输入样例 3
6 10 2 1004535809
输出样例 3
622165218
输入样例 4
30 40 1 265371653
输出样例 4
179937201
限制与约定
对于所有数据，保证 $ 2\le n\le m\le 100 $，$ 10^8<p<1.07\times 10^9 $ 且 $ p $ 为质数，$ 1\le k\le 2 $。
- Subtask 1 (10 pts)：$ m\le 20 $。
- Subtask 2 (25 pts)：$ k=1 $。
- Subtask 3 (15 pts)：$ n=m\le 30 $。
- Subtask 4 (10 pts)：$ m\le 30 $。
- Subtask 5 (15 pts)：$ m\le 40 $。
- Subtask 6 (10 pts)：$ m\le 70 $。
- Subtask 7 (15 pts)：$ m\le 100 $。
时间限制：$ 2\text{s} $。
空间限制：$ 512\text{MB} $。