865_F. Egg Roulette_10338
The game of Egg Roulette is played between two players. Initially 2R raw eggs and 2C 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?

Input

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', '?'.

Output

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

Examples

Input

1 1
??BB


Output

0


Input

2 4
?BA??B??A???


Output

1


Input

4 14
????A??BB?????????????AB????????????


Output

314

Note

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".
#include <bits/stdc++.h>
using namespace std;
long long C[777][777];
int r, c;
long long total;
long long best = (long long)1e18, best_z = -1;
void dfs(long long x, long long y, int v1, int v2) {
  long long diff = abs(x - y);
  if (best <= 1 || diff - C[v1][r] * C[v2][r] >= best) {
    return;
  }
  if (v1 == r - 1 && v2 == r - 1) {
    long long diff = abs(x - y);
    if (diff < best) {
      best = diff;
      best_z = x;
    }
    return;
  }
  if (v1 >= r) {
    long long cur1 = C[v1][r] - C[v1 - 1][r];
    long long sum2 = C[v2][r];
    dfs(x, y + cur1 * sum2, v1 - 1, v2);
  }
  if (v2 >= r) {
    long long sum1 = C[v1][r];
    long long cur2 = C[v2][r] - C[v2 - 1][r];
    dfs(x + sum1 * cur2, y, v1, v2 - 1);
  }
}
char s[12345];
int cntA[12345], cntB[12345];
map<long long, long long> mp;
long long solve(long long x, long long y, int v1, int v2) {
  long long state = x * 10000 + v1 * 100 + v2;
  if (mp.find(state) != mp.end()) {
    return mp[state];
  }
  long long &res = mp[state];
  long long diff = abs(x - y);
  if (diff - C[v1][r] * C[v2][r] > best) {
    return res = 0;
  }
  if (v1 < r || v2 < r) {
    if (v1 >= cntA[v1 + v2] && v2 >= cntB[v1 + v2]) {
      int sum = v1 + v2;
      v1 -= cntA[sum];
      v2 -= cntB[sum];
      return res = C[v1 + v2][v1];
    }
    return res = 0;
  }
  res = 0;
  char c = s[v1 + v2 - 1];
  if (c != 'B') {
    long long cur1 = C[v1][r] - C[v1 - 1][r];
    long long sum2 = C[v2][r];
    res += solve(x, y + cur1 * sum2, v1 - 1, v2);
  }
  if (c != 'A') {
    long long sum1 = C[v1][r];
    long long cur2 = C[v2][r] - C[v2 - 1][r];
    res += solve(x + sum1 * cur2, y, v1, v2 - 1);
  }
  return res;
}
int main() {
  scanf("%d %d", &r, &c);
  for (int i = 0; i <= 2 * (r + c); i++) {
    for (int j = 0; j <= 2 * (r + c); j++) {
      if (j == 0)
        C[i][j] = 1;
      else if (i == 0)
        C[i][j] = 0;
      else
        C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]);
    }
  }
  total = C[r + c][r] * C[r + c][r];
  {
    long long x = 0, y = 0;
    int v1 = r + c, v2 = r + c;
    while (v1 >= r && v2 >= r) {
      if (x > y) {
        long long cur1 = C[v1][r] - C[v1 - 1][r];
        long long sum2 = C[v2][r];
        y += cur1 * sum2;
        v1--;
      } else {
        long long sum1 = C[v1][r];
        long long cur2 = C[v2][r] - C[v2 - 1][r];
        x += sum1 * cur2;
        v2--;
      }
    }
    best = abs(x - y);
  }
  dfs(0, 0, r + c, r + c);
  scanf("%s", s);
  cntA[0] = cntB[0] = 0;
  for (int i = 0; i < 2 * (r + c); i++) {
    cntA[i + 1] = cntA[i] + (s[i] == 'A');
    cntB[i + 1] = cntB[i] + (s[i] == 'B');
  }
  long long ans = solve(0, 0, r + c, r + c);
  cout << ans << endl;
  return 0;
}

1 1
??BB
 2 4
?BA??B??A???
 4 14
????A??BB?????????????AB????????????
 4 6
BB???A??????A???????
 2 8
??A???AB?AB?A??BBA?B
 6 4
A??????????BAB?????B
 10 20
BBAA?AAABBAAAABABBBBBBBBA?BB?AAA?A?AAAA???BABBBBA?B?AAAAABAB
 10 20
?AABBA??AA????BB?A?????B??B??AA?????AAA?B??AB?B?A?B?AA?AABAB
 13 17
????????????ABBBBBBBBBBBBBBBBBBB????????????????????????????
 16 14
????????????????????????????????????????????????????????????
 10 10
ABABABAAABBBAAAAAAAAABAABBAABBBBBBBBBBBA
 14 16
??????????????????????????AA????????????????????????????????
 7 3
B???AAABB?B???BA?A?B
 10 20
?B?BBAAABA?B?AA?BB?????ABAAAABB?ABBBBBBAA???A??AB?ABB?B?BA?A
 20 10
??????????????????????????????????????????????????BBBBBBBBBB
 1 20
??????????????????????????????????????????
 13 17
????????????????????????????????????????????????????????????
 12 18
???????????????AA???????????????????????????????????????????
 11 19
???????????????????A?????????????????A????????????A?????????
 5 3
?BB?BBBBB?BBBBB?
 5 5
BB????B?????????B???
 14 11
??????????????????????????????????????????????????
 2 3
ABBAABBAAB
 11 19
???????????????????A?????????????????A????????????B?????????
 16 14
??????????????????????????????????????????????????????????AA
 12 18
???A??B???B???????????A?????????????????????????????????????
 3 7
AB??AA??B?????A?????
 20 1
??????????????????????????????????????????
 13 17
??????????????????A????B????????????????????A???????????????
 20 10
????????????????????????????????????????????????????????????
 10 20
A??????????BA?B?????????B???????????????????????????????????
 10 20
BBBBBBBBBB??????????????????????????????????????????????????
 10 20
????????????A??????????????????????????????A??B??????A?A?B??
 18 12
???????????????????????????A????????????????????????????????
 14 16
???????????????AA????????????????????????????????B??????????
 19 11
???????????????????A????????????????????????????????????????
 20 1
AAAAAAAAAAAAAAAAAAAA??????????????????????
 15 15
????????????????????AA?????????????????????????????????????B
 20 1
????????????????????????????????????????BB
 11 19
???A??????B?????????B???????????????????????????????A???????
 1 20
?AB??????BA????B???BA????????AAB??????????
 7 9
BBBBBBAAAAABBBAAAAAAAABBBBAABBBA
 16 14
????????????????????????????????????????B????????????A??????
 10 20
A?A???A??B?A????B??B???????B???????????????A??B?????????????
 20 10
???????????????????????????????????????????????????????????B
 17 13
????A?B?????????????????????????????????????????????????????
 15 15
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
 20 10
AAAAAAAAAAA????????????????????????????????????????????????A
 10 20
??????????????????????????????????????????????????????????BA
 20 10
AAAAAAAAAAAAAAAAAAAAAAAAAA??????????????????????????????????
 10 20
????????????????????????????????????????????????????????????
 20 10
A??B??A???B???A??B?????????????????B?A??????????????????????
 2 4
A??????????BAB?????B
 6 20
BBAA?AAABBAAAABABBBBBBBBA?BB?AAA?A?AAAA???BABBBBA?B?AAAAABAB
 2 20
?AABBA??AA????BB?A?????B??B??AA?????AAA?B??AB?B?A?B?AA?AABAB
 13 14
????????????????????????????????????????????????????????????
 7 16
??????????????????????????AA????????????????????????????????
 7 3
B?A?AB???B?BBAAA???B
 20 10
BBBBBBBBBB??????????????????????????????????????????????????
 1 17
????????????????????????????????????????????????????????????
 11 10
???????????????????A?????????????????A????????????A?????????
 2 1
ABBAABBAAB
 11 14
???????????????????A?????????????????A????????????B?????????
 16 11
??????????????????????????????????????????????????????????AA
 10 1
????????????A??????????????????????????????A??B??????A?A?B??
 18 12
????????????????????????????????A???????????????????????????
 14 16
???????????????AA??????????????????????>?????????B??????????
 15 2
????????????????????AA?????????????????????????????????????B
 11 14
???A??????B?????????B???????????????????????????????A???????
 10 14
????????????????????????????????????????B????????????A??????
 10 10
???????????????????????????????????????????????????????????B
 20 2
AAAAAAAAAAA????????????????????????????????????????????????A
 10 20
?B?????????????????????????????????????????????????????????A
 20 8
AAAAAAAAAAAAAAAAAAAAAAAAAA??????????????????????????????????
 10 7
????????????????????????????????????????????????????????????
 3 10
A??B??A???B???A??B?????????????????B?A??????????????????????
 5 14
????????????????????????????????????????????????????????????
 20 1
BBBBBBBBBB??????????????????????????????????????????????????
 12 1
????????????A??????????????????????????????A??B??????A?A?B??
 18 7
????????????????????????????????A???????????????????????????
 15 3
????????????????????AA?????????????????????????????????????B
 8 14
???A??????B?????????B???????????????????????????????A???????
 11 14
????????????????????????????????????????B????????????A??????
 11 10
???????????????????????????????????????????????????????????B
 20 3
AAAAAAAAAAA????????????????????????????????????????????????A
 4 7
????????????????????????????????????????????????????????????
 3 10
??????????????????????A?B?????????????????B??A???B???A??B??A
 5 12
????????????????????????????????????????????????????????????
 14 7
????????????????????????????????A???????????????????????????
 16 14
???A??????B?????????B???????????????????????????????A???????
 11 16
???????????????????????????????????????????????????????????B
 20 3
A????????????????????????????????????????????????AAAAAAAAAAA
 4 8
????????????????????????????????????????????????????????????
 2 10
??????????????????????A?B?????????????????B??A???B???A??B??A
 14 1
????????????????????????????????A???????????????????????????
 16 4
???A??????B?????????B???????????????????????????????A???????
 11 14
???????????????????????????????????????????????????????????B
 20 5
A????????????????????????????????????????????????AAAAAAAAAAA
 4 15
????????????????????????????????????????????????????????????
 14 1
???????????????????????????A????????????????????????????????
 20 5
AAAAAAAAAAA????????????????????????????????????????????????A
 6 15
????????????????????????????????????????????????????????????
 12 15
????????????????????????????????????????????????????????????
 1 10
A??B??A???B???A??B?????????????????B?A??????????????????????
 1 16
A??B??A???B???A??B?????????????????B?A??????????????????????
 1 14
A??B??A???B???A??B?????????????????B?A??????????????????????
 1 1
??????????????????????????????????????????
 13 3
????????????????????????????????????????????????????????????
 12 15
???????????????AA???????????????????????????????????????????
 11 19
?????????A????????????A?????????????????A???????????????????
 14 16
??????????B????????????????????????????????AA???????????????
 1 8
?AB??????BA????B???BA????????AAB??????????
 16 11
????????????????????????????????????????B????????????A??????
 6 20
A?A???A??B?A????B??B???????B???????????????A??B?????????????
 16 10
???????????????????????????????????????????????????????????B
 17 8
????A?B?????????????????????????????????????????????????????
 10 1
??????????????????????????????????????????????????????????BA
 5 20
????????????????????????????????????????????????????????????
 7 10
A??B??A???B???A??B?????????????????B?A??????????????????????
 1 19
????????????????????????????????????????????????????????????
 10 2
????????????A??????????????????????????????A??B??????A?A?B??
 4 10
???????????????????????????????????????????????????????????B
 10 20
A?????????????????????????????????????????????????????????B?
 17 1
BBBBBBBBBB??????????????????????????????????????????????????
 5 4
???B?????????B????BB
 12 2
????????????A??????????????????????????????A??B??????A?A?B??
 18 10
????????????????????????????????A???????????????????????????
 2 14
???A??????B?????????B???????????????????????????????A???????
 20 2
A????????????????????????????????????????????????AAAAAAAAAAA
 11 7
???????????????????A?????????????????A????????>???A????>????
 16 2
???A??????B?????????B???????????????????????????????A???????
 4 13
????????????????????????????????????????????????????????????
 2 9
??????????????????????A?B?????????????????B??A???B???A??B??A
 11 8
???????????????????????????????????????????????????????????B
 3 15
????????????????????????????????????????????????????????????
 3 13
????????????????????????????????????@???????????????????????
 19 1
????????????????????????????????A???????????????????????????
 10 5
AAAAAAAAAAA????????????????????????????????????????????????A
 6 18
????????????????????????????????????????????????????????????
 2 15
????????????????????????????????????????????????????????????
 1 18
A??B??A???B???A??B?????????????????B?A??????????????????????
 1 12
A??B??A???B???A??B?????????????????B?A??????????????????????
 1 2
??????????????????????????????????????????
 11 3
????????????????????????????????????????????????????????????
 6 15
???????????????AA???????????????????????????????????????????
 5 20
A?A???A??B?A????B??B???????B???????????????A??B?????????????
 16 4
???????????????????????????????????????????????????????????B
 17 8
?????????????????????????????????????????????????????B?A????
 10 2
??????????????????????????????????????????????????????????BA
 7 11
A??B??A???B???A??B?????????????????B?A??????????????????????
 7 20
????????????????????????????????AA??????????????????????????
 19 4
??????????????????????????????????????????????????????????AA

0
 1
 314
 21
 1
 120
 1
 126
 12
 459823234112
 1
 2911594896
 35
 20
 0
 10685501398
 451585680
 68934450
 0
 0
 10
 7124934600
 0
 817190
 0
 13813800
 1
 137846528820
 54627300
 23083695792960
 6435
 1
 48620
 1749695026860
 2310789600
 4568648125690
 1
 7898654920
 0
 293930
 13118212
 1
 151532656696
 1716
 11541847896480
 303065313392
 0
 17672631900
 92378
 1540
 184756
 80450690112
 3
 0
 382
 172986450
 38760
 15
 35508275440
 113093022
 10015005
 1
 3268760
 126864549792
 92378
 1749695026860
 2310789600
 70538355
 1307504
 3124550
 13813800
 24322155
 48620
 20
 4085950
 4
 924
 30045015
 1352078
 151584480450
 129454695
 8008
 5311735
 60090030
 60480225
 70
 60
 660
 573166440
 35240152720
 16872570
 244662670200
 440
 880
 40116600
 471435600
 10623470
 446775310800
 1112
 20058300
 357891900
 97384
 109254600
 717
 1197096
 96573
 2
 34767720
 28381080
 319770
 3562467300
 131
 23206929840
 35
 80450690112
 30942573120
 184756
 185534
 1144
 1470597342
 167960
 140
 43758
 346104
 165
 2496144
 686353797976
 17597
 131282408400
 8436285
 145422675
 3002
 1206
 26246220
 32650
 5064
 17672631900
 220
 4422
 342848
 4261270
 8092
 6
 2288132
 31332
 281
 3711935040
 125704203300
 335920
 330
 1716
 226760523600
