No Palindromic Substring String Construction

Scarlet wants to construct a string of length L using an alphabet of size k (the first k letters of the English alphabet) such that the string does not contain any palindromic substring of length greater than 1. In other words, the string should not contain any contiguous substring of length ≥2 that is a palindrome.

Note that a substring of length 2 is a palindrome if both characters are the same; a substring of length 3 is a palindrome if the first and third characters are the same; and for longer substrings the palindrome property would force a violation of one of these local conditions. Hence the restrictions can be summarized as:

• For any adjacent positions, the characters must be different.
• For any 3 consecutive characters, the first and third must be different.

To make the problem even more challenging, Scarlet fixes the character at position s to a given letter w (1-indexed). Your task is to compute the number of strings satisfying these conditions, and output the answer modulo p.

The problem can be formally stated as: Count the number of strings S of length L over an alphabet of size k (using the first k letters) such that:

• For all 1 ≤ i < L, S[i] ≠ S[i+1].
• For all 1 ≤ i ≤ L-2, S[i] ≠ S[i+2].
• S[s] = w.

Output the answer modulo p.

inputFormat

The input consists of a single line containing five space-separated values:

1. k — the size of the alphabet (an integer).
2. L — the length of the string (an integer).
3. s — the fixed position (1-indexed) in the string (an integer).
4. w — the character that must appear at the s-th position (a lowercase letter from the first k letters).
5. p — the modulus (an integer).

outputFormat

Output a single integer representing the number of valid strings modulo p.

sample

3 3 2 b 100

2