LowbieH and Peggy are in the playroom to figure out an interesting problem. Given a string of matched parenthesis \(s\), the scoring rules are defined by:

1. If \(s=()\), then \(score(s)=1\).

2. If \(t\) is another string of matched parenthesis, then \(score(s+t)=score(s)+score(t)\).

3. \(score\Bigl((s)\Bigr) = score(s)*2\).

LowbieH and Peggy want to calculate the score of given string quickly, can you help them? Since the answer may be very large, you only need to tell them the score after **mod** \(514329\).