fq.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
 
#define vi vector <int>
#define vl vector <long long>
#define vpii vector <pair <int,int> >
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define FOR(i,n) for(ll i=0;i<int(n);i++)
#define READ(v,n) {FOR(i,n){ll x;cin>>x;v.pb(x);} }
#define gmin(a,b) {if (b<a) a=b;}
#define gmax(a,b) {if (b>a) a=b;}
#define pb push_back
#define ppb pop_back
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
 
int main(){
  string s;
 
  while(cin>>s) {
    int count = 0;
    long a[501];
    long b[501];
    for (int i = 0; i <= 500; ++i) { a[i] = 0; b[i] = 0; }
    a[0] = 1;
    int l = s.length();
    for(int i = 0; i < l; ++i){
      if (s[i] == '.') {
        b[0] = a[1];
        for (int j = 1; j <= count; ++j) {
          b[j] = (a[j+1] + a[j-1]) % 1000000;
        }
        if (count < 499) {
          ++count;
          b[count] = (a[count-1] + a[count+1]) % 1000000;
        }
        else {
          b[500] = a[499];
        }
      }
      else if (s[i] == '(') {
        b[0] = 0;
        for (int j = 1; j <= count; ++j) {
          b[j] = a[j-1];
        }
        if (count < 499) {
          ++count;
          b[count] = a[count-1];
        }
        else {
          b[500] = a[499];
        }
      }
      else if (s[i] == ')') {
        b[0] = a[1];
        for (int j = 1; j <= count; ++j) {
          b[j] = a[j+1];
        }
        b[500] = 0;
      }
      for(int j = 0; j <= 500; ++j) a[j] = b[j];
    }
    cout << a[0]<<endl;
  }
 
  return 0;
}