Problem Description

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.

Input Format

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 Format

Output one integer: the answer modulo $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

Hint

For all testdata, it is guaranteed that $2\le n\le m\le 100$, $10^8<p<1.07\times 10^9$, and $p$ is a prime, and $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$.

Translated by ChatGPT 5