Скобки

Очень простая

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 128 мегабайт

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

Определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильная скобочная последовательность.

Входные данные

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

Выведите искомое количество способов по модулю 301907.

Ввод #1

Ответ #1

Отправки 1K

Коэффициент принятия 37 %