Розчарована черга

Туалет у саду Фредді зламаний, тому його єдиний шанс — громадські туалети поблизу. Одного разу перед туалетом вишикувалася довга черга людей. Фредді дуже потрібно, тому він відчайдушно хоче, щоб черга обслуговувалася якнайшвидше.

Щоб скористатися туалетом, слід заплатити $5$ крон. У половини людей у черзі є монета в $5$ крон, а в іншої половини — лише монета в $10$ крон. Спочатку у оператора туалету немає монет, тому люди в черзі повинні реорганізуватися так, щоб кожного разу, коли хтось хоче заплатити монетою в $10$ крон, у оператора була хоча б одна монета в $5$ крон, доступна від попередніх клієнтів.

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

Вхідні дані

Складається з кількох тестів. Кожен тест складається з одного рядка, що містить непорожній рядок круглих дужок і крапок довжиною $n(n\le 1000)$. Крапка вказує на людину, яка бажає змінити свою позицію в черзі, відкрита дужка вказує на людину, яка не бажає змінювати позицію, у якої є монета номіналом в $5$ крон, а закрита дужка вказує на людину, яка не бажає змінювати позицію, у якої є монета в $10$ крон.

Вважайте, що $n$ парне і що рядок містить не більше $n/2$ відкритих дужок і не більше $n/2$ закритих дужок.

Вихідні дані

Для кожного тесту обчисліть кількість способів переупорядкувати чергу так, щоб були виконані умови, описані в умові задачі. Оскільки це число може бути занадто великим, то виведіть лише один рядок, що містить одне ціле число, рівне останнім $6$ цифрам (у десятковому представленні) числа.

Приклади