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

6
(()

2