Восстановление скобок

Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.

Исходные данные

Первая строка содержит заданный шаблон длиной не более 80 символов.

Результат

Выведите искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2*10⁹.

Пример