鸡蛋轮盘游戏在两名玩家之间进行。最初将2R生鸡蛋和2C熟鸡蛋随机放入纸箱中。蛋壳保留在上面,因此无法区分生鸡蛋和熟鸡蛋。玩家一次选择一个鸡蛋,然后将鸡蛋砸在他/她的额头上。如果鸡蛋煮熟了,不会发生什么事情,但如果鸡蛋是生的,那就会变得很混乱。这种情况一直持续到一名玩家打破了 R 个生鸡蛋,此时该玩家被宣布为失败者,另一名玩家获胜。
玩家轮流的顺序可以描述为一串“A”和“B”字符,其中第 i 个字符告诉哪个玩家应该选择第 i 个鸡蛋。传统上,玩家轮流一个接一个地进行游戏。也就是说,它们遵循“ABABAB...”的顺序。但这不太公平,因为第二个玩家比第一个玩家更容易获胜。我们希望您能找到更好的顺序让玩家轮流进行。让我们将排序的不公平性定义为第一个玩家的获胜概率和第二个玩家的获胜概率之间的绝对差。我们对最大限度地减少不公平现象的订单感兴趣。仅当包含与“B”相同数量的“A”时,我们才认为订单有效。
您还将获得一个长度为 2(R + C) 的字符串 S,仅包含 'A'、'B' 和 '?'人物。如果某个排序仅在 S 包含“?”的位置与 S 不同,则称该排序与 S 匹配。在最小化不公平性的有效排序中,有多少匹配 S?
输入
输入的第一行将包含整数 R 和 C (1 ≤ R, C ≤ 20, R + C ≤ 30)。
输入的第二行将包含长度为 2(R + C) 的字符串 S,仅包含字符 'A'、'B'、'?'。
输出
打印最小化不公平性并匹配 S 的有效排序的数量。
示例
输入 #1
1 1 ??BB
输出 #1
0
输入 #2
2 4 ?BA??B??A???
输出 #2
1
输入 #3
4 14 ????A??BB?????????????AB????????????
输出 #3
314
注意
在第一个测试用例中,最小不公平性为 0,实现它的排序是“ABBA”和“BAAB”,两者都不匹配 S。请注意,诸如“ABBB”之类的排序也会有不公平性 0,但它是无效的,因为它不包含与“B”相同数量的“A”。
在第二个示例中,唯一匹配的顺序是“BBAAABABABBA”。