题目描述

Scarlet 妄图构造字符集为 $k$，长度为 $L$ 的字符串，满足没有任何一个长度超过 $1$ 的回文连续子串。

看起来这样的字符串太多了，Scarlet 随手加了个限制：她指定了字符串的第 $s$ 位为 $w$。

这下 Scarlet 不会做了，请你来帮她计算究竟有多少满足条件的字符串。按照套路，你只要求出答案对 $p$ 取模后的结果。

输入格式

第一行三个整数 $k,L$ 和 $p$，分别表示构造的字符串的的字符集、长度和模数。

第二行两个整数 $s,w$，描述 Scarlet 给的限制。

注意：$s=0$ 表示该数据点中 Scarlet 十分良心地没有添加限制。

输出格式

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

3 3 233
1 1

2

提示

字符集：一个字符串中不同字符的数量。例如，字符集是 $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$。