F. Яичная рулетка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Яичную рулетку играют два игрока. Изначально 2R сырых яйца и 2C вареных яйца кладутся в коробку в случайном порядке. Яйца все еще в скорлупе, поэтому невозможно отличить сырое яйцо от вареного. По одному игроки выбирают одно яйцо и разбивают его о свой лоб. Если яйцо было вареное, ничего особенного не произойдет, но если оно было сырое, то оно все испачкает. Такое продолжается до тех пор, пока один из игроков не разобьет R сырых яиц. В этот момент игра заканчивается, этот игрок объявляется проигравшим, а его соперник — победителем.

Порядок, в котором ходят игроки, может быть представлен как строка из букв «A» и «B», где i-й символ обозначает игрока, который будет выбирать i-е яйцо. Традиционно игроки ходят по очереди, то есть, они следуют порядку «ABABAB...». Это не очень честно, так как второй игрок будет выигрывать чаще, чем первый. Мы хотим, чтобы вы нашли более честный порядок ходов. Определим нечестность порядка как модуль разности между вероятностью победы первого игрока и вероятностью победы второго игрока. Нам интересны порядки, в которых нечестность является минимально возможной. Мы считаем порядок корректным, если в нем одинаковое количество букв «A» и «B».

Вам будет дана строка S длины 2(R + C), содержащая только символы «A», «B» и «?». Порядок подходит под S, если он отличается от S только в позициях, где S содержит «?». Среди корректных порядков, минимизирующих нечестность, сколько подходят под S?

Входные данные

Первая строка содержит целые числа R и C (1 ≤ R, C ≤ 20, R + C ≤ 30).

Вторая строка содержит строку S, имеющею длину 2(R + C) и состоящую только из символов «A», «B», «?».

Выходные данные

Выведите количество корректных порядков, которые минимизируют нечестность и подходят под S.

Примеры
Входные данные
1 1
??BB
Выходные данные
0
Входные данные
2 4
?BA??B??A???
Выходные данные
1
Входные данные
4 14
????A??BB?????????????AB????????????
Выходные данные
314
Примечание

В первом тесте из примере минимальная нечестность равна 0, а порядки, минимизирующие ее, это «ABBA» и «BAAB», но ни один из них не подходит под S. Заметьте, что порядок «ABBB» также имеет нечестность 0, но он не является корректным, так как не содержит одинаковое число «A» и «B».

Во втором примере единственно подходящим порядком является «BBAAABABABBA».