对于长度为 $ 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} $。