题目背景

题目描述

设二元运算符 $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}$。

输出格式

一行一个整数表示答案。

2 2
C

4

2 2
A

5

8 8
CCACAAC

399968

提示

【样例解释】

对于样例 #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$。