## MREPLBRC - Counting The Way of Bracket Replacement

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274509/problem/H
 English Vietnamese

A regular bracket sequence is a string of characters consisting only of opening and closing brackets, and satisfying the following conditions:

• An empty string is a regular bracket sequence.

• If A is a regular bracket0sequence, then (A), [A] and {A} are also regular bracket sequences.

• If A and B are regular bracket sequences, then AB is also a regular bracket sequence.

For example, the sequences [({})], [](){} i [{}]()[{}] are regular, but the sequences [({{([, []({)} and [{}])([{}] are not.

Ivica has found a string which looks like it could be a regular bracket sequence. Some of the characters have become smudged and illegible, and could have been any character.

Write a program that calculates how many ways the illegible characters in the string can be replaced by brackets so that the result is a regular bracket sequence. This number can be very large, so output only its last 5 digits.

### Input

The first line contains an even integer N (2 <= N <= 200), the length of the string.

The second line contains the string. Illegible characters are represented by the '?' character.

### Output

Output the number of regular bracket sequences the string could have read.

### Sample

```input

6
()()()

output

1

input

10
(?([?)]?}?

output

3

input

16
???[???????]????

output

92202

In  the  second example,  the  three matching  regular bracket sequences
are ({([()])}), ()([()]{}) and ([([])]{}).
```

 Added by: ~!(*(@*!@^& Date: 2009-03-09 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ERL JS-RHINO NODEJS PERL6 VB.NET Resource: COCI 1th 07