P10005 [CTT Mutual Test 2023] Basic Technique Practice Problem.

For a sequence $a$ of length $n$, define $f(a)=\dfrac{1}{\prod\limits_{i=k}^n s_i}$, where $s_i$ is the prefix sum array of $\{a_n\}$, and **$k$ is a given constant with $1\le k\le 2$**. Consider all sequences $a$ that satisfy the following three conditions: - The length of $a$ is $n$. - $\forall i,j$, $a_i\ne a_j$. - $1\le a_i\le m$. Find the sum of $f(a)$ over all such sequences. Output the answer modulo $p$. It is guaranteed that $p$ is a prime.

The first line contains four integers $n,m,k,p$, representing the sequence length, the upper bound of the sequence elements, and the modulus.

Output one integer: the answer modulo $p$.

For all testdata, it is guaranteed that $2\le n\le m\le 100$, $10^8