Разочарованная очередь

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

Чтобы воспользоваться туалетом, следует заплатить $5$ крон. У половины людей в очереди есть монета в $5$ крон, а у другой половины — только монета в $10$ крон. Первоначально у оператора туалета нет монет, поэтому люди в очереди должны реорганизоваться так, чтобы каждый раз, когда кто-то хочет заплатить монетой в $10$ крон, у оператора была хотя бы одна монета в $5$ крон, доступная от предыдущих клиентов.

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

Входные данные

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

Считайте, что $n$ четное и что строка содержит не более $n/2$ открывающих скобок и не более $n/2$ закрывающих скобок.

Выходные данные

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

Примеры