P10005 [集训队互测 2023] 基础寄术练习题

对于长度为 $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\le n\le m\le 100$，$10^8