| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P193PROG - Problem G - Món quà ý nghĩa |
Sắp tới là sinh nhật của Kirito, Bích Ngọc quyết định sẽ tặng cho anh ta một mọn quà đặc biệt. Cô ấy biết rặng Kirito rất thích các chuỗi ngoặc tròn có độ dài n và sẽ càng thích thú nếu chuỗi ngoặc đó là hoàn hảo.
Một chuỗi ngoặc được gọi là hoàn hảo khi và chỉ khi:
- Tổng số dầu mở ngoặc bằng tổng số dấu mở ngoặc.
- Với bất kỳ tiền tố nào của chuỗi, số lượng dầu mở ngoặc luôn lớn hơn hoặc bằng số lượng dấu đóng ngoặc.
Bích Ngọc đã mua được một chuỗi ngoặc s có độ dài m (m <= n). Cô ấy sẽ tạo ra một chuỗi ngoặc hoàn hảo độ dài n bằng cách chọn chuỗi p và q chỉ gồm các dầu ngoặc tròn và hợp nhất chúng lại thành chuỗi p + s + q, hay nói cách khác là thêm chuỗi p vào đầu và chuỗi q vào cuối chuỗi s.
Bây giờ, do sự tò mò của mình, cô ấy tự hỏi có bao nhiêu cặp chuỗi p và q tồn tại sao cho chuỗi p + s + q là một chuỗi ngoặc hoàn hảo độ dài n. Vì kết quả có thể sẽ rất lớn nên cô ấy mong muốn mọi người sẽ tính giúp cô và kết quả lấy dư theo modulo 109 + 7.
Input
Dòng đầu tiên và duy nhất là hai số nguyên n và m (1 ≤ m ≤ n ≤ 105, n - m ≤ 2000).
Dòng thứ hai là chuỗi s có độ dài m chỉ gồm các ký tự ‘(‘ và ‘)’.
Output
In ra số cặp p, q sao cho p + s + q là một chuỗi ngoặc tròn hoàn hảo theo modulo 109 + 7.
Example
Input 4 1 ( Output 4
Input 4 4 (()) Output 1Giải thích
Ở ví dụ 1, có 4 cặp p, q thỏa mãn:
- p = “(”, q = “))”.
- p = “()”, q = “)”.
- p = “”, q = “())”.
- p = “”, q = “)()”.
Ở ví dụ 2, chỉ có cách duy nhất là chọn p, q rỗng.
| Được gửi lên bởi: | adm |
| Ngày: | 2019-03-02 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
