Nhiệm vụ của bạn là tính toán số lượng dãy ngoặc hợp lệ có độ dài \(n\) khi một tiền tố của dãy được cho.

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\).
• Dòng thứ hai có một xâu gồm \(k\) kí tự: tiền tố của chuỗi.

Output

• In số lượng dãy chia lấy dư cho \(10 ^ 9 + 7\).

Constraints

• \(1 \leq k \leq n \leq 10 ^ 6\)

Example

Sample input

6  
(()

Sample output

2

Note

Có hai dãy có thể: (())() và (()()).