|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Васе дается строка из N букв латинского алфавита и всего пара правильных скобок и очевидно, что в алфавит кроме букв ничего не входит. Васе нужно узнать, а сколькими вариантами можно правильно расставить правильные скобки. Например: для строки ABC их можно расставить только так: (ABC), (AB)C, (A)BC, A(BC), A(B)C, AB(C). Формат входных данных В единственной строке содержится строка состоящая из букв латинского алфавита длиной до 255 символов. Формат выходных данных Одно целое число - количество вариантов расстановки скобок.
|