Problem Description

Define the binary operator $k\operatorname A n$ as the permutation number ${\rm A}_n^k$, and $k \operatorname C n$ as the combination number ${\rm C}_n^k$. When $k > n$, both values are defined as $0$.

Given $n, m$ and a sequence ${\rm opt}_{[1,n-1]}$ of length $n-1$ containing only 'A' and 'C', compute the sum of $(\cdots(((a_1\operatorname{opt}_1 a_2)\operatorname{opt}_2 a_3)\operatorname{opt}_3 a_4)\cdots\operatorname{opt}_{n-2}a_{n-1})\operatorname{opt}_{n-1}a_n$ for all sequences $a_{[1,n]}$ of length $n$ where each element is an integer in the range $[1, m]$.

The answer should be taken modulo $11417603$.

Input Format

The first line contains two integers $n, m$.

The next line contains a string of length $n-1$ representing ${\rm opt}$.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

2 2
C

Sample Output #1

4

Sample Input #2

2 2
A

Sample Output #2

5

Sample Input #3

8 8
CCACAAC

Sample Output #3

399968

Notes

Sample Explanation

For Sample #1:

$1\operatorname C 1=1$, $1\operatorname C 2=2$, $2\operatorname C 1=0$, $2\operatorname C 2=1$, the sum is $4$.

For Sample #2:

$1\operatorname A 1=1$, $1\operatorname A 2=2$, $2\operatorname A 1=0$, $2\operatorname A 2=2$, the sum is $5$.

Data Range

No bundled tests, scored per test case.

For $100\%$ of the data, $2 \leq n, m \leq 10^5$, ${\rm opt}$ contains only 'A' and 'C'.

见题面 Input 部分

见题面 Output 部分