fq.cpp

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <cstring>
 
using namespace std;
 
#define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++)
#define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--)
#define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--)
 
#define PB push_back
#define MP make_pair
 
#define MM(co, cim) memset((co), (cim), sizeof((co)))
 
#define DEB(x) cerr << ">>> " << #x << " : " << x << endl;
 
int n, nh, dp[1014][1014];
string line;
 
int go (int pos, int cnt)
{
  if (cnt > nh) return 0;
  if (pos == n) 
  {
    if (!cnt) return 1;
    else return 0;
  }
  if (dp[pos][cnt] != -1) return dp[pos][cnt];
  int res = 0;
  if (line[pos] == '.')
  {
    if (cnt > 0) res = (res + go(pos + 1, cnt - 1)) % 1000000;
    res = (res + go(pos + 1, cnt + 1)) % 1000000;
  }
  else 
  {
    if (line[pos] == '(') res = (res + go(pos + 1, cnt + 1)) % 1000000;
    else 
    {
      if (cnt > 0) res = (res + go(pos + 1, cnt - 1)) % 1000000;
    }
  }
  //printf("dp[%d][%d] = %d\n", pos, cnt, res);
  return dp[pos][cnt] = res;
}
 
int main ()
{
  while (getline(cin, line))
  {
    n = line.length();
    nh = n / 2;
    FOR(i, 0, 1014) MM(dp[i], -1);
    printf("%d\n", go(0, 0));
  }
  return 0;
}