Задано шаблон, який складається з круглих дужок та знаків питання.
Визначити, скількоми способами можна замінити знаки питання круглими дужками так, щоб отримати правильну дужкову послідовність.
Перший рядок містить заданий шаблон довжиною не більше 2000 символів.
Виведіть шукану кількість способів за модулем 301907.