The Hopeless Queue

The park in Haebin City had two restrooms, but one of them broke down a while ago. Only one is left.

The trouble is that Haebin needs the restroom right now and the queue in front of it is very long.

To take his mind off the pain, Haebin stares at the hopeless queue and starts solving the problem below.

Using the restroom costs 50 won. Half of the people in the queue carry a single 50 won coin, and the other half carry a single 100 won coin. The attendant has no coins for change when the restroom opens. Anyone who pays with a 100 won coin has to get 50 won back, and the attendant hands over a 50 won coin that an earlier visitor already paid. So at any point in the queue, if the number of people who have paid 50 won so far falls below the number who have paid 100 won, the attendant runs out of change.

Some people in the queue never move. They will not step forward and they will not step back. Everyone else can be rearranged freely. Count how many ways there are to line the queue up so that the attendant never runs out of change. Two queues count as the same way when every position holds the same kind of coin.

The input consists of several test cases. Process the input until the end of the file.

Each test case is one line holding a string of length $n$ ($1 \le n \le 1000$). The string uses only these three characters.

• ( : a person who carries a 50 won coin and will not move
• ) : a person who carries a 100 won coin and will not move
• . : a person who can be moved

The number of ( and the number of ) are each at most $n/2$, and $n$ is always even.

For each test case, print the number of valid queues modulo 1,000,000 on its own line. Print the remainder as it is, without padding it to six digits.