#include <algorithm>
#include <cmath>
#include<cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define REP(i,n) for ( int i = 0; i < (n); i++)
#define FOR(i,a,b) for ( int i = (a); i <= (b); i++ )
#define FORD(i,a,b) for ( int i = (a); i>= (b); i-- )
#define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl;
struct node {
int i,j;
int previ, prevj;
};
string s;
queue<node> q;
int m = 100000,len;
int table [1010][1010];
bool states [1010][1010];
void bfs () {
node n, pos;
n.i = n.j = 0;
n.previ = n.prevj = 0;
q.push(n);
while (!q.empty()) {
pos = q.front();
q.pop();
//cout << s[pos.i+pos.j-1] << endl;
if (pos.previ < pos.i && s[pos.i+pos.j-1] == ')') continue;
if (pos.prevj < pos.j && s[pos.i+pos.j-1] == '(') continue;
if (2*pos.i > len) continue;
if (pos.j > pos.i) continue;
if (pos.i != pos.previ || pos.j!=pos.prevj) {
table[pos.i][pos.j] += table[pos.previ][pos.prevj];
table[pos.i][pos.j] %= m;
}
//if (pos.i == 2 && pos.j == 2) cout << pos.previ << " " << pos.prevj << endl;
if (states[pos.i][pos.j]) continue;
n.i = pos.i+1;
n.j = pos.j;
n.previ = pos.i;
n.prevj = pos.j;
q.push(n);
n.i = pos.i;
n.j = pos.j+1;
q.push(n);
states[pos.i][pos.j] = true;
}
}
int main() {
while (cin >> s) {
len = s.length();
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
table[i][j]=0;
states[i][j] = false;
}
}
table [0][0] = 1;
bfs ();
/*for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
cout << table[i][j] << " ";
}
cout << endl;
}*/
cout << table [len/2][len/2] << endl;
}
return 0;
}