#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
char input[1024];
int tlen;
int **reslt;
int f(const char *str, int extra, int rem) {
if (!rem)
return !extra;
if (reslt[extra][rem] >= 0)
return reslt[extra][rem];
int total = 0;
if (str[0] != ')' && str[1] != '(') // ab
total += f(str+2, extra, rem-2);
if (str[0] != '(' && str[1] != '(' && extra >= 2) // bb
total += f(str+2, extra-2, rem-2);
if (str[0] != ')' && str[1] != ')') // aa
total += f(str+2, extra+2, rem-2);
if (str[0] != '(' && str[1] != ')' && extra >= 1) // ba
total += f(str+2, extra, rem-2);
total %= 100000;
reslt[extra][rem] = total;
return total;
}
int main() {
int *inner = new int[1024*1024];
reslt = new int *[1024];
for (int i = 0; i < 1024; i++)
reslt[i] = inner+1024*i;
do {
char cur = getchar();
if (cur < '\n') break;
tlen = 0;
while (cur != '\n') {
input[tlen++] = cur;
cur = getchar();
}
if (!tlen) break;
input[tlen] = 0;
// vstup nacten
for (int i = 0; i <= tlen; i++)
for (int j = 0; j <= tlen; j++)
reslt[i][j] = -1;
int result = f(input, 0, tlen);
printf("%d\n", result);
} while (true);
delete [] inner;
delete [] reslt;
return 0;
}