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

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

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