Задано шаблон, який складається з круглих дужок та знаків питання.

Визначити, скількоми способами можна замінити знаки питання круглими дужками так, щоб отримати правильну дужкову послідовність.

Вхідні дані

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

Вихідні дані

Виведіть шукану кількість способів за модулем 301907.