Dãy ngoặc hợp lệ gồm:

• Xâu rỗng.
• A hợp lệ thì (A), [A] và {A} cũng thế.
• A, B hợp lệ thì AB cũng thế.

Ví dụ : [({})], [](){} và [{}]()[{}] là hợp lệ, [({{([, []({)} và [{}])([{}] không hợp lệ.

Cho một xâu chỉ gồm ( ) { } [ ] và ?. Dấu ? có thể thay thế bằng ngoặc bất kỳ. Tính số cách thay thế mà thu được 1 dãy ngoặc hợp lệ. Chỉ hiện 5 chữ số cuối cùng.

Input

Dòng đầu là ~N~, độ dài xâu ~(2~ ~\le~ ~N~ ~\le~ ~200)~, Dòng thứ hai là xâu mô tả.

Output

5 chữ số cuối cùng của dẫy ngoặc hợp lệ thu được. (~\le~ 5 chữ số thì in ra hết cả kết quả).

Sample Input 1

6
()()()

Sample Output 1

1

Sample Input 2

10
(?([?)]?}?

Sample Output 2

3

Sample Input 3

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

Sample Output 3

92202

Note

Ví dụ thứ hai, 3 dãy ngoặc hợp lệ là (([()])), ()([()]) và ([([])]).