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

Формат вхідних даних

У стандартному потоці міститься заданий шаблон довжиною не більше 80 символів.

Формат вихідних даних

У стандартний потік вивести шукану кількість способів. Вхідні дані будуть такі, що ця кількість не перевершить \(2 \cdot 10^9\).

Приклад вхідних даних

????(?

Приклад вихідних даних

2