P8946 The Lost Symbol


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

The first line contains two integers $n,m$. The next line contains a string of length $n-1$ representing $\text{opt}$.

Output one integer, the answer.

#### 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$. | Test Point ID | $n\leq$ | $m\leq$ | Special Property | | :----------: | :----------: | :----------: | :----------: | | $1\sim3$ | $8$ | $8$ | None | | $4\sim6$ | $314$ | $159$ | None | | $7\sim10$ | $2718$ | $2818$ | None | | $11\sim13$ | $10^5$ | $10^5$ | $\rm opt$ consists only of $\rm A$ | | $14\sim16$ | $10^5$ | $10^5$ | $\rm opt$ consists only of $\rm C$ | | $17\sim20$ | $10^5$ | $10^5$ | $\rm opt$ is formed by concatenating at most $10$ consecutive blocks of $\rm A$ and consecutive blocks of $\rm C$ | | $21,22$ | $8492$ | $10^5$ | None | | $23\sim25$ | $10^5$ | $10^5$ | None | Translated by ChatGPT 5