P4925 [1007] Scarlet 的字符串不可能这么可爱

Scarlet 妄图构造字符集为 $k$，长度为 $L$ 的字符串，满足没有任何一个长度超过 $1$ 的回文连续子串。 看起来这样的字符串太多了，Scarlet 随手加了个限制：她指定了字符串的第 $s$ 位为 $w$。 这下 Scarlet 不会做了，请你来帮她计算究竟有多少满足条件的字符串。按照套路，你只要求出答案对 $p$ 取模后的结果。

第一行三个整数 $k,L$ 和 $p$，分别表示构造的字符串的的字符集、长度和模数。 第二行两个整数 $s,w$，描述 Scarlet 给的限制。 **注意：$s=0$ 表示该数据点中 Scarlet 十分良心地没有添加限制。**

一行一个整数，表示答案对 $p$ 取模后的结果。

字符集：一个字符串中不同字符的数量。例如，字符集是 $3$ 的话，你可以认为字符串仅由 $\texttt A$、$\texttt B$、$\texttt C$ 三个字母组成。 样例解释：第一个字符固定 $\texttt A$，那么符合要求的字符串是 $\texttt{ABC},\texttt{ACB}$。而 $\texttt{AAB}$ 字符串包括 $\texttt{AA}$ 这个回文子串，$\texttt{ACA}$ 本身就是回文串，以此类推。 对于 $50\%$ 的数据，$k\leq5$，$L\leq10$。 对于另 $30\%$ 的数据，$s=0$。 对于 $100\%$ 的数据，$1\leq k,L\leq 10^{18}$，$0\leq s\leq L$，$1\leq w\leq k$，$1\leq p\leq 10^9$。