Дана последовательность, состоящая из символов двух типов. Эта последовательность должна быть преобразована в правильную скобочную последовательность путем последовательной замены всех символов по следующему правилу:

• выбираются два символа разного типа,
• символ, стоящий в последовательности левее, заменяется на открывающую скобку,
• символ, стоящий правее, — на закрывающую.

Определите количество способов осуществить такое преобразование. Способы, отличающиеся только последовательностью замен, считаются одинаковыми.

Правильной скобочной последовательностью называется строка, состоящая из символов '(' и ')', определяющаяся следующим образом:

• пустая строка является правильной скобочной последовательностью;
• если A – правильная скобочная последовательность, то строка (A) – также правильная скобочная последовательность;
• если A и B – правильные скобочные последовательности, то строки AB и BA также являются правильными скобочными последовательностями.