Đếm dãy ngoặc

View as PDF

All submissions

Best submissions

Time limit:

Clang++ 2.0s

Memory limit:

Clang++ 512M

Problem type

Points: 2000 Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

Một dãy ngoặc hợp lệ được quy định như sau:

Xâu rỗng
A hợp lệ thì (A), [A] và {A} cũng thế.
A, B hợp lệ thì AB cũng thế.

Ví dụ: [({})], {} và [{},[{}] là hợp lệ, [({{([, []} và [{}])([{}] không hợp lệ.

Cho một xâu chỉ gồm ( ) { } [ ] và ?. Dấu ? có thể thay thế bằng ngoặc bất kỳ. Tính số cách thay thế mà thu được 1 dãy ngoặc hợp lệ. Bạn chỉ cần in ra 5 chữ số cuối cùng của kết quả.

Input

Dòng đầu là \(n\) - độ dài xâu (\(2 \leq n \leq 200\)), Dòng thứ hai là xâu mô tả.

Output

5 chữ số cuối cùng của dẫy ngoặc hợp lệ thu được. (<= 5 chữ số thì in ra hết cả kết quả).

Example

Test 1

Input

6 
()()()

Output

Test 2

Input

10 
(?([?)]?}?

Output

Note

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

Comments

There are no comments at the moment.