Sequence Binary Operation Sum

Consider the following binary operations defined on two integers. For any two integers \(k\) and \(n\), define:

• \(k \operatorname{A} n = {\rm A}_n^k\) which is the number of permutations, i.e. \(\displaystyle{\rm A}_n^k = n \times (n-1) \times \cdots \times (n-k+1)\) if \(k \le n\), and \(0\) if \(k > n\).
• \(k \operatorname{C} n = {\rm C}_n^k\) which is the number of combinations, i.e. \(\displaystyle{\rm C}_n^k = \binom{n}{k}\) if \(k \le n\), and \(0\) if \(k > n\).

For the sake of consistency, when \(k=0\) we define both
\(0 \operatorname{A} n = {\rm A}_n^0 = 1\) and \(0 \operatorname{C} n = {\rm C}_n^0 = 1\) (since \(\binom{n}{0}=1\) and \({\rm A}_n^0=1\)).

You are given two integers \(n\) and \(m\) and a string of length \(n-1\) consisting only of the letters A and C. For every sequence \(a_1, a_2, \dots, a_n\) where each \(a_i \in [1, m]\), define the value of the expression as follows:

$$ S(a) = (\cdots(((a_1 \operatorname{opt}_1 a_2) \operatorname{opt}_2 a_3) \operatorname{opt}_3 a_4) \cdots \operatorname{opt}_{n-1}a_n, $$

where \(\operatorname{opt}_i\) is the \(i\)th character of the given string, and the operator used is determined by the character as per the definitions above.

Your task is to compute the sum of \(S(a)\) over all sequences \(a_1, a_2, \dots, a_n\) (each \(a_i \in [1, m]\)) and output the answer modulo 11417603.

inputFormat

The first line contains two integers \(n\) and \(m\).

The second line contains a string of length \(n-1\) comprised only of the characters A and C.

outputFormat

Output a single integer — the sum of the expression values taken over all sequences \(a_1, a_2, \dots, a_n\) (with each \(a_i \in [1,m]\)) modulo 11417603.

sample

2 3
A

20