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

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

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

Формат входного файла

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

Формат выходного файла

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

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
????(?
2

0.128s 0.012s 13