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