Cho xâu S chỉ gồm các ký tự (, ) và số nguyên k. Đánh dấu một số vị trí trên xâu, rồi xóa các ký tự ở những vị trí đã đánh dấu. Đếm số cách đánh dấu sao cho xâu còn lại là dãy ngoặc đúng bậc đúng bằng k. Có thể không đánh dấu vị trí nào. Hai cách khác nhau nếu tập vị trí được đánh dấu khác nhau, kể cả khi chúng tạo ra cùng một xâu.

Dãy rỗng có bậc 0. Nếu A là dãy ngoặc đúng bậc h thì (A) có bậc h + 1. Nếu A, B là hai dãy ngoặc đúng bậc h₁, h₂ thì AB có bậc max(h₁, h₂). Tương đương, bậc là độ sâu lồng ngoặc lớn nhất.

Dữ liệu vào

Dòng đầu chứa k.

Dòng thứ hai chứa S (1 ≤ k ≤ |S| ≤ 5000).

Kết quả

Số cách đánh dấu, lấy dư cho 10⁹ + 7.

Ví dụ

Input

1
())

Output

2

Đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn. Mỗi test được chấm độc lập.