给出一个长度为 ，由 ，， 三种字符组成的字符串 ，你需要把每一个 染成 或 中的一个。
对于给出的 ，问有多少种染色方式使得存在整数 使得：
由于方法可能很多，因此只需要输出最后的答案对 取模的结果。
第一行输入两个正整数 。
第二行输入一个长度为 的字符串 。
输出一行，包含一个整数，表示答案
5 2 XXXXX
4
对于 的数据，。 对于 的数据，。 对于 的数据，。
中国国家队清华集训 2012-2013 第一天
