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\).

One line a string. It contains only parenthesis and is perfect matched. The length of input will not exceed \(100000\).

One line an integer, denoting the score (mod \(514329\)).

\(score\Bigl(((()())())\Bigr) = ((1 + 1) * 2 + 1) * 2 = 10\)