P8946 The Lost Symbol


设二元运算符 $k\operatorname A n$ 为排列数 ${\rm A}_n^k$，$k \operatorname C n$ 为组合数 ${\rm C}_n^k$，定义 $k>n$ 时两者的值都为 $0$。 给定 $n,m$ 和一个长度为 $n-1$ 的仅包含 $\textrm A,\textrm C$ 的序列 ${\rm opt}_{[1,n-1]}$，对所有长度为 $n$，且每一个数都是 $[1,m]$ 中的整数的序列 $a_{[1,n]}$ 求 $(\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$ 的和。 答案对质数 $11417603$ 取模。

第一行两个整数 $n,m$。 接下来一行一个长度为 $n-1$ 的字符串表示 $\text{opt}$。

一行一个整数表示答案。

#### 【样例解释】 对于样例 #1： $1\operatorname C 1=1$，$1\operatorname C 2=2$，$2\operatorname C 1=0$，$2\operatorname C 2=1$，求和为 $4$。 对于样例 #2： $1\operatorname A 1=1$，$1\operatorname A 2=2$，$2\operatorname A 1=0$，$2\operatorname A 2=2$，求和为 $5$。 #### 【数据范围】 不开启捆绑测试，按点给分。 对于 $100\%$ 的数据，$2\leq n,m\leq 10^5$，${\rm opt}$ 仅包含 $\textrm A,\textrm C$。 | 测试点编号 | $n\leq$ | $m\leq$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | | $1\sim3$ | $8$ | $8$ | 无 | | $4\sim6$ | $314$ | $159$ | 无 | | $7\sim10$ | $2718$ | $2818$ | 无 | | $11\sim13$ | $10^5$ | $10^5$ | $\rm opt$ 仅由 $\rm A$ 构成 | | $14\sim16$ | $10^5$ | $10^5$ | $\rm opt$ 仅由 $\rm C$ 构成 | | $17\sim20$ | $10^5$ | $10^5$ | $\rm opt$ 由不超过 $10$ 段连续的 $\rm A$ 和连续的 $\rm C$ 拼接而成 | | $21,22$ | $8492$ | $10^5$ | 无 | | $23\sim25$ | $10^5$ | $10^5$ | 无 |