Background

Problem Description

Let the binary operator $k\operatorname A n$ denote the number of permutations ${\rm A}_n^k$, and $k \operatorname C n$ denote the number of combinations ${\rm C}_n^k$. Define both values to be $0$ when $k>n$.

Given $n$, $m$, and a sequence ${\rm opt}_{[1,n-1]}$ of length $n-1$ that contains only $\textrm A$ and $\textrm C$, consider all sequences $a_{[1,n]}$ of length $n$ where every number is an integer in $[1,m]$. 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$ over all such sequences.

Output the answer modulo the prime $11417603$.

Input Format

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

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

Output Format

Output one integer, the answer.

2 2
C

4

2 2
A

5

8 8
CCACAAC

399968

Hint

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

Constraints

Bundled test is not enabled, and scoring is by test points.

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

Translated by ChatGPT 5