[an error occurred while processing the directive]

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

Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте: 3 секунды

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

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

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

Пример

input.txt output.txt
????(?
2
[an error occurred while processing the directive]