Олимпиадный тренинг

Задача 23412. Восстановление скобок


Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.
 
Входные данные: вводится строка, которая содержит заданный шаблон длиной не более 80 символов.
 
Выходные данные: выведите искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет \( 2 \cdot 10^9\).
 
 
Примеры
Входные данные Выходные данные
1 ????(? 2