#include <cstdio> #define MOD 1000000 using namespace std; char buffer[1024]; int pocet(int i, int v, int p, int d) { if (v < 0) return 0; if (p == 0 || d == 0) return 1; if (buffer[i] == '(') return pocet(i+1, v+1, p-1, d) % MOD; else if (buffer[i] == ')') return pocet(i+1, v-1, p, d-1) % MOD; return (pocet(i+1, v+1, p-1, d) % MOD) + (pocet(i+1, v-1, p, d-1) % MOD); } int main() { int n; while (scanf("%s%n%*c", buffer, &n) != EOF) { printf("%d\n", pocet(0, 0, n/2, n/2) % MOD); } return 0; }