import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
protected final int MODULE = 1000000;
Main p = new Main();
p.run();
}
while (input.ready()) {
line = nextLine();
if (line.charAt(0) == ')') {
} else {
System.
out.
println(computeResults
(1,
0,
1)); }
}
}
protected int computeResults(int fiveCount, int tenCount, int position) {
if (fiveCount > line.length() / 2) {
return 0;
}
if (position == line.length()) {
if (fiveCount == tenCount) {
return 1;
}
return 0;
}
char c = line.charAt(position);
if (c == '(') {
return computeResults(fiveCount + 1, tenCount, position + 1);
}
if (c == ')') {
if (fiveCount == tenCount) {
return 0;
}
return computeResults(fiveCount, tenCount + 1, position + 1);
}
int res = 0;
if (fiveCount > tenCount) {
res += computeResults(fiveCount, tenCount + 1, position + 1);
}
res += computeResults(fiveCount + 1, tenCount, position + 1);
return res % MODULE;
}
while (!st.hasMoreTokens()) {
}
return st.nextToken();
}
return Integer.
parseInt(nextToken
()); }
return input.readLine();
}
}