Nhiệm vụ của bạn là tính toán số lượng chuỗi dấu ngoặc hợp lệ có độ dài \(n\) khi một tiền tố của chuỗi đã cho trước.
Input
- Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 10^6\)), là độ dài của chuỗi.
- Dòng thứ hai chứa một chuỗi có \(k\) ký tự, là tiền tố của chuỗi dấu ngoặc hợp lệ (\(1 \le k \le n\)).
Output
- In ra số lượng chuỗi hợp lệ modulo \(10^9+7\).
Example
Test 1
Input
6
(()Output
2Note
Có hai chuỗi hợp lệ có thể được tạo ra:
- (())()
- (()())
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.