给定一个长度为 的字符串 ，字符串仅由字符 、 和 组成。
你可以对字符串 进行任意次（包括 次）“压缩”操作。一次压缩操作的定义如下：选择字符串中两个相邻且均不为 的字符，删除其中的任意一个。剩余部分的字符将自动拼接在一起。
现给定一个目标长度 。请计算：在进行若干次操作后，最终能够得到多少种不同的、长度恰好为 的字符串。由于答案可能很大，请输出方案数对 取模后的结果。
第一行包含两个整数 和 ，分别表示初始字符串的长度和目标长度。
第二行包含一个长度为 且仅由字符 、、 组成的字符串 。
输出一个整数，表示能够得到的不同字符串的数量对 取模后的值。
6 4 010#11
5
能够得到的不同字符串为：
共 种。
对于 的评测用例，，字符串 中字符 的数量不超过 ；
对于所有评测用例，，，且 ，字符串 中字符 的数量不超过 。
