题目描述

对于长度为 $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$ 取模后的结果。

2 3 2 1000000007

966666675

3 5 2 998244353

148276980

6 10 2 1004535809

622165218

15 20 2 1064822107

53789887

30 40 1 265371653

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$。