Main.java

 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    protected String line;
    protected final int MODULE = 1000000;
 
    public static void main(String[] args) throws Exception {
        Main p = new Main();
        p.run();
    }
 
    protected void run() throws Exception {
        while (input.ready()) {
            line = nextLine();
            if (line.charAt(0) == ')') {
                System.out.println("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;
    }
 
    StringTokenizer st = new StringTokenizer("");
    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
 
    public String nextToken() throws Exception {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(input.readLine());
        }
        return st.nextToken();
    }
 
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }
 
    public String nextLine() throws Exception {
        return input.readLine();
    }
 
}