절망적인 줄

해빈시 공원에는 화장실이 두 개 있었는데, 얼마 전에 하나가 고장 났다. 이제 쓸 수 있는 것은 하나뿐이다.

문제는 해빈이가 당장 화장실에 가고 싶은데 화장실 앞 줄이 아주 길다는 것이다.

고통을 잊으려고 해빈이는 절망적인 줄을 바라보며 다음 문제를 풀기 시작했다.

화장실 사용료는 50원이다. 줄에 선 사람 중 절반은 50원 동전을 하나 가지고 있고, 나머지 절반은 100원 동전을 하나 가지고 있다. 관리인에게는 화장실을 열 때 거슬러 줄 동전이 하나도 없다. 100원 동전을 낸 사람에게는 50원을 거슬러 줘야 하는데, 이때 앞서 들어간 사람이 낸 50원 동전을 그대로 거스름돈으로 쓴다. 그래서 줄의 어느 지점에서든 그때까지 들어간 사람 가운데 50원을 낸 사람 수가 100원을 낸 사람 수보다 적어지면 거스름돈이 모자란다.

줄에 선 사람 가운데 일부는 자리를 절대 바꾸지 않는다. 앞으로도 뒤로도 움직이지 않는다. 나머지 사람은 자리를 마음대로 바꿀 수 있다. 관리인의 거스름돈이 한 번도 모자라지 않게 줄을 세우는 방법이 몇 가지인지 구하라. 모든 자리에서 그 자리에 선 사람이 내는 동전의 종류가 같은 두 줄은 같은 방법으로 센다.

입력은 여러 개의 테스트 케이스로 이루어진다. 파일의 끝까지 처리한다.

각 테스트 케이스는 길이가 $n$ ($1 \le n \le 1000$)인 문자열 한 줄이다. 문자열은 다음 세 문자로만 이루어진다.

• ( : 50원 동전을 가지고 있고 자리를 바꾸지 않는 사람
• ) : 100원 동전을 가지고 있고 자리를 바꾸지 않는 사람
• . : 자리를 바꿔도 되는 사람

(의 개수와 )의 개수는 각각 $n/2$ 이하이고, $n$은 항상 짝수이다.

각 테스트 케이스마다 조건을 만족하는 방법의 수를 1,000,000으로 나눈 나머지를 한 줄에 하나씩 출력한다. 나머지는 여섯 자리로 0을 채우지 않고 그대로 출력한다.