Дужки
Дуже проста
Обмеження на час виконання 1 секунда
Обмеження на використання пам'яті 128 мегабайтів
Задано шаблон, який складається з круглих дужок та знаків питання.
Визначити, скількоми способами можна замінити знаки питання круглими дужками так, щоб отримати правильну дужкову послідовність.
Вхідні дані
Перший рядок містить заданий шаблон довжиною не більше 2000 символів.
Вихідні дані
Виведіть шукану кількість способів за модулем 301907.
Приклади
Вхідні дані #1
Відповідь #1
Відправки 1K
Коефіцієнт прийняття 37%