Egg Roulette

Egg Roulette 게임은 두 명의 플레이어가 진행한다. 처음에 날달걀 2R개와 익힌 달걀 2C개를 상자에 무작위로 넣는다. 껍데기는 그대로이므로 날달걀과 익힌 달걀을 구별할 방법은 없다. 한 번에 한 명씩 플레이어가 달걀 하나를 고른 다음 자신의 이마에 내리쳐 깨뜨린다. 달걀이 익었다면 별일이 일어나지 않지만, 날달걀이라면 상당히 엉망이 된다. 한 플레이어가 날달걀 R개를 깨뜨릴 때까지 이를 계속하며, 그 시점에 해당 플레이어는 패자로 선언되고 다른 플레이어가 승리한다.

플레이어들이 차례를 진행하는 순서는 'A'와 'B' 문자로 이루어진 문자열로 나타낼 수 있으며, i-th 문자는 어느 플레이어가 i-th 달걀을 골라야 하는지를 나타낸다. 전통적으로 플레이어들은 한 명씩 번갈아 차례를 진행한다. 즉, "ABABAB..." 순서를 따른다. 하지만 이는 그다지 공정하지 않다. 두 번째 플레이어가 첫 번째 플레이어보다 더 자주 승리하기 때문이다. 플레이어들이 차례를 진행할 더 나은 순서를 찾아야 한다. 한 순서의 불공정도를 첫 번째 플레이어의 승리 확률과 두 번째 플레이어의 승리 확률 간 차이의 절댓값으로 정의하자. 불공정도를 최소화하는 순서에 관심이 있다. 'A'와 'B'가 같은 개수만큼 포함된 순서만 유효하다고 간주한다.

또한 'A', 'B', '?' 문자로만 이루어진 길이 2(R + C)의 문자열 S가 주어진다. 어떤 순서가 S와 다른 위치가 모두 S에서 '?'인 위치라면, 그 순서는 S와 일치한다고 한다. 불공정도를 최소화하는 유효한 순서 중 S와 일치하는 것은 몇 개인가?

입력의 첫 번째 줄에는 정수 R and C (1 ≤ R, C ≤ 20, R + C ≤ 30)가 주어진다.

입력의 두 번째 줄에는 'A', 'B', '?' 문자로만 이루어진 길이 2(R + C)의 문자열 S가 주어진다.

불공정도를 최소화하고 S와 일치하는 유효한 순서의 개수를 출력한다.

첫 번째 테스트 케이스에서 최소 불공정도는 0이고, 이를 달성하는 순서는 "ABBA"와 "BAAB"이며, 둘 다 S와 일치하지 않는다. "ABBB"와 같은 순서도 불공정도가 0이지만, 'A'와 'B'가 같은 개수만큼 포함되어 있지 않으므로 유효하지 않다는 점에 유의한다.

두 번째 예제에서 일치하는 유일한 순서는 "BBAAABABABBA"이다.