Problem Description

Scarlet wants to construct a string with an alphabet size of $k$ and length $L$, such that it has no palindromic contiguous substring with length greater than $1$.

It seems there are too many such strings, so Scarlet casually adds a restriction: she fixes the $s$-th character of the string to be $w$.

Now Scarlet cannot solve it. Please help her compute how many strings satisfy the conditions. As usual, you only need to output the answer modulo $p$.

Input Format

The first line contains three integers $k, L$ and $p$, representing the alphabet size, the string length, and the modulus.

The second line contains two integers $s, w$, describing the restriction given by Scarlet.

Note: $s=0$ means that in this test case Scarlet kindly did not add any restriction.

Output Format

Output one integer in a single line, representing the number of valid strings modulo $p$.

3 3 233
1 1

2

Hint

Alphabet size: the number of distinct characters in a string. For example, if the alphabet size is $3$, you may assume the string consists only of the three letters “A”, “B”, and “C”.

Sample explanation: if the first character is fixed to A, then the valid strings are ABC and ACB. The string AAB contains the palindromic substring AA, and ACA itself is a palindrome, and so on.

Constraints for $50\%$ of the testdata: $k\leq5, L\leq10$.

Constraints for another $30\%$ of the testdata: $s=0$.

Constraints for $100\%$ of the testdata: $1\leq k, L\leq 10^{18}, 0\leq s\leq L, 1\leq w\leq k, 1\leq p\leq 10^9$.

Translated by ChatGPT 5