fq.cpp

#include <iostream>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <string>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
 
using namespace std;
 
#define DEBUG(x) cout << ">>> " #x << " : " << x << endl;
 
 
unsigned solve(std::string & str)
{
   unsigned fixedOpeners(0);
   unsigned fixedClosers(0);
   unsigned visitedFixedOpeners(0);
   unsigned visitedFixedClosers(0);
 
   for (std::string::iterator pnter(str.begin()); pnter!=str.end(); ++pnter)
   {
      if (*pnter == ')')
        ++fixedClosers;
      if (*pnter == '(')
         ++fixedOpeners;
   }
 
   std::vector<unsigned> states(str.size()/2 + 2, 0);
   states[0]=1;
   for(unsigned index(0); index<str.size(); ++index)
   {
      std::vector<unsigned> newStates(str.size()/2 + 2, 0);
 
      // opener
      if (str[index] == '(')
      {
          ++visitedFixedOpeners;
          for(unsigned state(0); state<=str.size()/2; ++state)
          {
             newStates[state + 1] += states[state];
             newStates[state + 1] %= 1000000;
          }
      }
      // closer
      else if (str[index] == ')')
      {
          ++visitedFixedClosers;
          for(unsigned state(1); state<=str.size()/2; ++state)
          {
             newStates[state - 1] += states[state];
             newStates[state - 1] %= 1000000;
          }
      }
      // rational
      else
      {
         for(unsigned state(0); state<=str.size()/2; ++state)
         {
            int availableOpeners(str.size()/2 - fixedOpeners - (index - state)/2 + visitedFixedOpeners - state);
            int availableClosers(str.size()/2 - fixedClosers - (index - state)/2 + visitedFixedClosers);
            if (state && availableClosers>0)
            {
               newStates[state - 1] += states[state];
               newStates[state - 1] %= 1000000;
            }
            if (availableOpeners > 0)
            {
               newStates[state + 1] += states[state];
               newStates[state + 1] %= 1000000;
            }
         }
      }
 
      // swap
      states.swap(newStates);
   }
 
   return states[0];
}
 
int main() 
{
	std::string line;
	while (std::cin>>line)
	   std::cout << solve(line) << std::endl;
 
	return 0;
}