//
// File: fq.cc
// Author: cteam019
//
// Created on October 19, 2013, 12:23 PM
//
#include <stdlib.h>
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
#include <map>
struct state{
int rem5; int rem10;
};
struct stack_entry{
state _st;
stack_entry* parent;
int sum;
bool visited;
};
struct state_less{
bool operator()(const state& a, const state& b){
return a.rem5 < b.rem5 || ( a.rem5 == b.rem5 && a.rem10 < b.rem10);
}
};
typedef std::map<state, int, state_less> StateTable;
typedef StateTable::iterator STIter;
char g_Buffer[1024];
//char g_Buffer[] = {"...."};
int g_Total;
stack_entry make_se(int rem5, int rem10, stack_entry* p) {
stack_entry se;
se._st.rem5 = rem5;
se._st.rem10 = rem10;
se.parent = p;
se.sum = 0;
se.visited = false;
return se;
}
void do_stuff(){
StateTable table;
std::stack<stack_entry> stack;
stack_entry surface;
surface.sum = 0;
state s;
s.rem5 = 0, s.rem10 = 0;
table[s] = 1;
stack.push(make_se(g_Total/2, g_Total/2, &surface));
while(!stack.empty())
{
stack_entry& top = stack.top();
if ( top.visited ) {
table[top._st] = top.sum;
top.parent->sum += top.sum;
top.parent->sum %= 10000000;
stack.pop();
continue;
}
STIter rv = table.find(top._st);
if ( rv != table.end() ) {
int val = rv->second;
top.parent->sum += rv->second;
top.parent->sum %= 10000000;
stack.pop();
} else {
top.visited = true;
int rem5 = top._st.rem5;
int rem10 = top._st.rem10;
int pos = g_Total - rem5 - rem10;
int bank = rem10 - rem5;
switch(g_Buffer[pos]) {
case '.' :
if ( rem5 > 0 )
stack.push(make_se(rem5-1,rem10, &top));
if ( rem10 > 0 && bank > 0 )
stack.push(make_se(rem5,rem10-1, &top));
break;
case '(' :
if ( rem5 > 0 )
stack.push(make_se(rem5-1,rem10, &top));
break;
case ')' :
if ( bank > 0 && rem10 > 0)
stack.push(make_se(rem5,rem10-1, &top));
}
}
}
printf("%d\n", surface.sum % 1000000);
}
//
//
//
int main(int argc, char** argv) {
while(!feof(stdin)) {
g_Buffer[0] = 0;
gets(g_Buffer);
g_Total = strlen(g_Buffer);
if ( g_Total == 0 )
break;
do_stuff();
}
return (EXIT_SUCCESS);
}