fq.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	string s;
	while(getline(cin,s)) {
		int N =s.length();
		vector<int> A(N+1,0);
		A[0] =1;
		int mod =1000000;
		for(int i =0; i < N; i++) {
			vector<int> An(N+1,0);
			for(int j =0; j <= N; j++) {
				if(j > 0 && s[i] != '(') An[j-1] =(An[j-1]+A[j])%mod;
				if(j < N && s[i] != ')') An[j+1] =(An[j+1]+A[j])%mod;}
			A =An;}
		cout << A[0] << "\n";}
	return 0;}