给定一个由 和 组成的长字符串 和一个整数 。计算将 分解为若干子序列的方式数，其中每个子序列形如 （恰好包含 个 ），结果对 取模。
由于字符串非常长，我们不直接给出 。而是给定一个整数 （）和一个长度为 的字符串 （）。字符串 是 重复 次拼接而成。
第一行包含 、 和 。
第二行包含长度为 的字符串 ，每个字符是 或 。
保证 的分解方式数不为零。
输出字符串 的分解方式数，对 取模。
2 6 1 MOOMOO
1
2 6 1 MMOOOO
6
1 4 2 MMOO
4
1 4 100 MMOO
976371285
样例一解释：唯一分解方式是将前三个字符组成一个 ，后三个字符组成另一个 。
样例二解释：共有六种不同的分解方式（大写字母组成一个 ，小写字母组成另一个 ）：
样例四解释：注意：结果需对 取模。