Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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:

  1. Tổng số dầu mở ngoặc bằng tổng số dấu mở ngoặc.
  2. 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
1
Giải thích

Ở ví dụ 1, có 4 cặp p, q thỏa mãn:

  1. p = “(”, q = “))”.
  2. p = “()”, q = “)”.
  3. p = “”, q = “())”.
  4. 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 PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.