P4925 [1007] Scarlet’s Strings Can’t Be This Cute

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$.

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 one integer in a single line, representing the number of valid strings modulo $p$.

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