four.cpp

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
#define DEBUG(x) cerr << ">> " << #x << ": " << x << endl;
#define REP(i,a) for (int i =0; i < (a);++i)
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
 
long tabulka[1000][1000];
 
int main() {
  string s;
  while (getline(cin, s, '\n'))
  {
    if (s[0] == ')') 
    {
      printf("0\n");
      continue;
    }
    int len = s.length();
    for (int column = 0; column < len; column++)
    {
        for (int row = 0; row < len; row++)
	{
	  tabulka[row][column] = 0;
	}
    }
    tabulka[0][0] = 0;
    tabulka[0][1] = 1;
    for (int row = 1; row < len; row++)
    {
      for (int column = 0; column < row+2 && column < len/2+1; column++)
      {
	if (column == 0)
	{
	  if (s[row] != '(')
	  {
	    tabulka[row][column] = tabulka[row-1][column+1] % 1000000;
	  } else tabulka[row][column] = 0;
	}
	else
	{
	  tabulka[row][column] = 
	  (
	  (s[row] != ')' ? tabulka[row-1][column-1] : 0) + 
	  (s[row] != '(' ? tabulka[row-1][column+1] : 0)
	  )
	  % 1000000;
	}
      }
    }
    printf("%ld\n", tabulka[len-1][0]);
  }
  return 0;
}