Dãy ngoặc II

Đếm số dãy ngoặc hợp lệ có độ dài $n$ khi biết một tiền tố của dãy.

Một dãy ngoặc hợp lệ là dãy ký tự ( và ) sao cho các ngoặc đóng mở khớp nhau.

Dữ liệu vào

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

Dòng thứ hai chứa xâu ký tự $k$ ký tự — tiền tố của dãy, gồm các ký tự ( và ).

Dữ liệu ra

In số dãy hợp lệ có thể hoàn thành từ tiền tố đã cho, modulo ${10}^9+7$.

Ràng buộc

• $1\le k\le n\le {10}^6$

Ví dụ