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

Dữ liệu vào

Dòng đầu tiên chứa số nguyên ~n~.

Dòng thứ hai chứa một xâu gồm ~k~ ký tự: tiền tố của dãy.

Kết quả

In ra số lượng dãy modulo ~10^9+7~.

Giới hạn

• ~1 \le k \le n \le 10^6~

Ví dụ

Dữ liệu vào:

6
(()

Kết quả:

2

Giải thích: Có hai dãy khả dĩ: (())() và (()()).