FQ.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author cteam94
*/
public class FQ {
int n;
while((new FQ()).readLine(br));
}
line = br.readLine();
if (line == null) return false;
n = line.length();
int x = p(0, 0);
System.
out.
println(x
% 1000000);
return true;
}
public int p(int o, int c){
if (o<c || o>n/2) return 0;
if (o+c==n) return 1;
if (line.charAt(o+c)=='(') return p(o+1,c);
if (line.charAt(o+c)==')') return p(o,c+1);
if (line.charAt(o+c)=='.') return p(o+1,c) + p(o,c+1);
return 0;
}
}