410221: GYM103985 G Коробка конфет

G. Коробка конфетограничение по времени на тест2 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Председателю жюри в честь 15-летия московской командной олимпиады подарили коробку конфет с фантиками синего и красного цвета.

Председатель, пребывая в приятных размышлениях о предстоящей олимпиаде, через некоторое время все конфеты съел. При этом он придерживался следующего алгоритма: в каждый момент времени он выбирал конфету того цвета, которого в коробке было больше, а если красных и синих конфет было поровну, то председатель предпочитал красную.

Каждый раз, съедая очередную конфету, председатель клал фантик на стол справа от всех предыдущих пустых фантиков. Таким образом, когда всё содержимое коробки было съедено, все фантики были выложены на столе в порядке употребления содержавшихся в них конфет. Правда из-за того, что некоторые фантики лежат лицом вниз, по ним нельзя точно сказать, какого они цвета.

У вас есть фотография стола, сделанная до того, как уборщица выкинула все фантики. Выясните, сколько существует различных коробок с конфетами, которые могли соответствовать получившейся последовательности фантиков. Коробки считаются разными, если в них разное количество конфет с фантиками какого-то цвета.

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

В первой строке находится число n (1 ≤ n ≤ 200 000) — число фантиков на столе.

Во второй строке записана строка длины n, задающая последовательность фантиков. Строка состоит из символов «r», «b» и «?», соответствующих красному фантику, синему и перевёрнутому (то есть, либо красному, либо синему).

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

Выведите одно число — количество возможных коробок с конфетами, соответствующих получившей последовательности. Если последовательность фантиков не могла соответствовать никакой коробке конфет, выведите 0.

ПримерыВходные данные

4
??rb

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

3

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

5
rrrrb

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

1

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

3
bbr

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

0

Примечание

В первом тесте подходит коробка, состоящая из 3 красных и 1 синей конфеты, коробка из 2 красных и 2 синих конфет, а также коробка состоящая из 1 красной и 3 синих конфет.

Во втором примере существует лишь одна коробка, подходящая под описание, в ней 4 красных и 1 синяя конфета.

В третьем примере задана несуществующая последовательность, если бы у председателя было 2 синих и 1 красная конфета, то он бы получил последовательность «brb».