CF865F.Egg Roulette

The game of Egg Roulette is played between two players. Initially 2_R_ raw eggs and 2_C_ cooked eggs are placed randomly into a carton. The shells are left on so there is no way to distinguish a raw egg from a cooked egg. One at a time, a player will select an egg, and then smash the egg on his/her forehead. If the egg was cooked, not much happens, but if the egg was raw, it will make quite the mess. This continues until one player has broken R raw eggs, at which point that player is declared the loser and the other player wins.

The order in which players take turns can be described as a string of 'A' and 'B' characters, where the i-th character tells which player should choose the i-th egg. Traditionally, players take turns going one after the other. That is, they follow the ordering "ABABAB...". This isn't very fair though, because the second player will win more often than the first. We'd like you to find a better ordering for the players to take their turns. Let's define the unfairness of an ordering as the absolute difference between the first player's win probability and the second player's win probability. We're interested in orderings that minimize the unfairness. We only consider an ordering valid if it contains the same number of 'A's as 'B's.

You will also be given a string S of length 2(R + C) containing only 'A', 'B', and '?' characters. An ordering is said to match S if it only differs from S in positions where S contains a '?'. Of the valid orderings that minimize unfairness, how many match S?

蛋类轮盘赌（Egg Roulette）游戏在两名玩家之间进行。初始时，将 $2R$ 个生鸡蛋和 $2C$ 个熟鸡蛋随机放入一个蛋盒中。蛋壳均保持完整，因此无法通过外观区分生蛋与熟蛋。玩家轮流进行操作：每次选择一枚鸡蛋，并将其砸在自己的额头上。若为熟蛋，则几乎不会发生任何事；但若为生蛋，则会弄得一团糟。游戏持续进行，直至某位玩家已砸破 $R$ 个生鸡蛋为止，此时该玩家判负，另一位玩家获胜。

玩家行动顺序可用一个仅含字符 'A' 和 'B' 的字符串描述，其中第 $i$ 个字符表示应由哪位玩家选择第 $i$ 枚鸡蛋。传统上，玩家依次轮流行动，即遵循顺序 "ABABAB..."。然而这种方式并不公平，因为第二位玩家的胜率高于第一位玩家。我们希望你为玩家寻找一种更公平的行动顺序。定义一个顺序的不公平度为：第一位玩家的获胜概率与第二位玩家的获胜概率之差的绝对值。我们的目标是找出使不公平度最小化的顺序。我们仅考虑有效顺序，即其中 'A' 的个数与 'B' 的个数相等。

此外，你还会收到一个长度为 $2(R + C)$ 的字符串 $S$，其字符仅包含 'A'、'B' 和 '?'。若一个顺序仅在 $S$ 中字符为 '?' 的位置上与 $S$ 不同，则称该顺序匹配 $S$。在所有使不公平度最小的有效顺序中，有多少个顺序匹配 $S$？

The first line of input will contain integers R and C (1 ≤ R, C ≤ 20, R + C ≤ 30).

The second line of input will contain the string S of length 2(R + C) consisting only of characters 'A', 'B', '?'.

输入的第一行包含两个整数 $R$ 和 $C$（$1 \leq R, C \leq 20$，且 $R + C \leq 30$）。

输入的第二行包含一个长度为 $2(R + C)$ 的字符串 $S$，该字符串仅由字符 'A'、'B' 和 '?' 组成。

Print the number of valid orderings that minimize unfairness and match S.

输出最小化不公平度且匹配 S 的有效排序数量。

In the first test case, the minimum unfairness is 0, and the orderings that achieve it are "ABBA" and "BAAB", neither of which match S. Note that an ordering such as "ABBB" would also have an unfairness of 0, but is invalid because it does not contain the same number of 'A's as 'B's.

In the second example, the only matching ordering is "BBAAABABABBA".

在第一个测试用例中，最小不公平度为 0，达到该值的排列有 “ABBA” 和 “BAAB”，但二者均不匹配 S。注意，类似 “ABBB” 的排列虽然不公平度也为 0，但由于其中 'A' 和 'B' 的数量不相等，因此是无效的。

在第二个例子中，唯一匹配的排列是 “BBAAABABABBA”。