Cho tổng độ dài n và một tiền tố ngoặc s có độ dài k, với 1≤k≤n≤106. Nhiệm vụ là đếm số cách nối thêm ngoặc mở/đóng để thu được một xâu ngoặc đúng độ dài đúng bằng n.
Nếu tiền tố đã vi phạm điều kiện cân bằng ở một vị trí thì không có cách hoàn thành. In đáp án modulo 1000000007.
Input
Dòng đầu chứa tổng độ dài n.
Dòng thứ hai chứa tiền tố ngoặc s.
Output
In kết quả theo yêu cầu, lấy modulo như đã nêu trong phần mô tả.
Constraints
1≤∣s∣≤n≤106; s chỉ gồm ( và ).
Scoring
Subtask 1 (50% số điểm): các test nhỏ trong 10 test đầu của bộ dữ liệu.
Subtask 2 (50% số điểm): không có giới hạn bổ sung.
Example
Test 1
Input
2
(
Output
1
Giải thích: Tiền tố ( chỉ cần nối thêm ) để trở thành xâu ngoặc đúng độ dài 2.
Lời giải tóm tắt
Phân tích: Quét s, đặt b = #('(')-#(')'). Nếu ở bất kỳ tiền tố nào b<0, đáp án bằng 0. Gọi r=n-k là số ký tự cần thêm. Hậu tố cần có o ngoặc mở và c ngoặc đóng thỏa
Phân tích:o+c=r, b+o-c=0, suy ra o=(r-b)/2.
Phân tích: Nếu r<b hoặc r-b lẻ thì vô nghiệm. Bỏ điều kiện không âm, có C(r,o) hậu tố. Theo ballot/reflection, các hậu tố xấu - lần đầu đưa độ cao từ 0 xuống -1 - tương ứng với C(r,o-1) chuỗi. Vậy
Phân tích:ans = C(r,o) - C(r,o-1).
Phân tích: Tiền xử lý giai thừa đến r; hàm C trả 0 khi chỉ số ngoài miền, giúp công thức xử lý cả biên.
Thuật toán: Cài đặt trực tiếp công thức hoặc quy hoạch nêu trên, tiền xử lý các đại lượng tổ hợp cần thiết và chuẩn hóa mọi phép toán theo modulo của đề. Các trường hợp không khả thi được loại trước khi thực hiện phép chia modulo.
Chứng minh: Mỗi hậu tố hợp lệ thỏa đúng số bước lên/xuống và không vượt biên. Với hậu tố xấu, phản xạ đoạn từ đầu hậu tố đến lần đầu độ cao toàn cục bằng -1; phép đảo biến đổi số bước lên từ o thành o-1 và là khả nghịch. Vì vậy số xấu đúng bằng số tổ hợp thứ hai, phép trừ là chính xác.