fq.cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
int main(){
string vstup;
while(cin>>vstup){
vector<vector<long long> > dynamika;
dynamika.resize(vstup.size()+1, vector<long long> (vstup.size()+3, 0));
dynamika[vstup.size()][0] = 1;
for(int i = vstup.size() -1; i>=0; i--){
if(vstup[i]!='('){
for(int j = 0; j < vstup.size()+2; j++){
dynamika[i][j+1]+= dynamika[i+1][j];
dynamika[i][j+1]%=1000000;
}
}
if(vstup[i]!=')'){
for(int j = 1; j < vstup.size()+3; j++){
dynamika[i][j-1]+= dynamika[i+1][j];
dynamika[i][j-1]%=1000000;
}
}
}
cout<<dynamika[0][0]<<endl;
}
}