Các dấu ngoặc xuất hiện rất nhiều trong các biểu thức toán học để thể hiện thứ tự tính toán. Giờ đây ta bỏ hết các hạng tử toán tử đi, chỉ giữ lại các dấu ngoặc, biểu thức mà ta thu được gọi là một dãy ngoặc đúng. Cụ thể hơn:

• Xâu rỗng là biểu thức ngoặc đúng bậc 0.
• Nếu ~A~ là biểu thức ngoặc đúng bậc ~k~ thì ~(A)~ là dãy ngoặc đúng bậc ~k + 1~.
• Nếu ~A~ là biểu thức ngoặc đúng bậc ~a~ và ~B~ là biểu thức ngoặc đúng bậc ~b~ thì ~AB~ là biểu thức ngoặc đúng bậc ~max(a, b)~.

Cho một xâu ~S~ chỉ chứa các ký tự '(' và ')' và một số ~k~. Nam muốn đánh dấu một số vị trí trên xâu này sao cho khi xóa các vị trí bị đánh dấu đó đi, Nam thu được dãy ngoặc đúng bậc ~k~. Hai cách đánh dấu được coi là khác nhau nếu tồn tại một vị trí được đánh dấu trong cách này nhưng không được đánh dấu trong cách kia.

Yêu cầu: Tính số cách xóa các vị trí để thu được dãy ngoặc đúng bậc ~k~, kết quả lấy dư cho ~10^9 + 7~.

Input

• Dòng đầu tiên chứa số tự nhiên ~k~.
• Dòng tiếp theo chứa xâu ~S~.

Output

• Ghi số cách xóa tìm được, chỉ cần in ra phần dư khi chia cho ~10^9 + 7~.

Sample Input 1

1
)((()(((((

Sample Output 1

3