{"code":"bracketcount","name":"Đếm dãy ngoặc","description":"Một dãy ngoặc hợp lệ được quy định như sau:\r\n\r\n - Xâu rỗng\r\n - A hợp lệ thì (A), [A] và {A} cũng thế.\r\n - A, B hợp lệ thì AB cũng thế.\r\n\r\nVí dụ: [({})], {} và [{},[{}] là hợp lệ, [({{([, []} và [{}])([{}] không hợp lệ.\r\n\r\nCho 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ệ. Bạn chỉ cần in ra 5 chữ số cuối cùng của kết quả.\r\n\r\n#### Input\r\n\r\n - Dòng đầu là $n$ - độ dài xâu ($2 \\leq n \\leq 200$), Dòng thứ hai là xâu mô tả.\r\n\r\n#### Output\r\n\r\n - 5 chữ số cuối cùng của dẫy ngoặc hợp lệ thu được. (<= 5 chữ số thì in ra hết cả kết quả).\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n\t\t6 \r\n\t\t()()()\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1\r\n        ```\r\n!!! question \"Test 2\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n\t\t10 \r\n\t\t(?([?)]?}?\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        3\r\n        ```\r\n\r\n    ??? warning \"Note\"\r\n        Ví dụ thứ hai, 3 dãy ngoặc hợp lệ là ({([()])}), ()([()]{}) và ([([])]{}).","points":2000.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}