Công ty Just Odd Inventions, gọi tắt là công ty JOI, chuyên tạo ra những phát minh kỳ lạ. Để ngăn thông tin mật bị rò rỉ, công ty lắp một cổng an ninh tại cửa ra vào. Mọi người đều phải đi qua cổng khi vào hoặc ra khỏi công ty, và không thể có từ hai người trở lên đi qua cổng cùng một lúc.

Mỗi khi một người đi qua, cổng ghi lại người đó đang vào hay ra. IOI-kun, một nhân viên của JOI, có bản ghi của cổng trong một ngày, được biểu diễn bằng xâu \(S\). Nếu ký tự thứ \(i\) của \(S\) là (, người thứ \(i\) đi qua cổng đã vào công ty; nếu ký tự đó là ), người ấy đã ra khỏi công ty. IOI-kun biết rằng lúc bắt đầu và kết thúc ngày hôm đó, trong công ty đều không có ai.

Không phải mọi xâu chỉ gồm ( và ) đều có thể là bản ghi hợp lệ. Chẳng hạn, ())( không hợp lệ vì có lúc số người trong công ty sẽ âm; (() không hợp lệ vì cuối ngày vẫn còn người trong công ty.

Ngay sau khi IOI-kun kiểm tra bản ghi, một vi-rút máy tính trong công ty đã sửa đổi xâu \(S\)! Sau khi điều tra, anh cho rằng vi-rút đã thực hiện hai bước sau:

1. Chọn một đoạn liên tiếp trong \(S\) và đảo từng ký tự trong đoạn: ( thành ), còn ) thành (. Gọi xâu thu được là \(S'\). Đoạn được chọn có thể có độ dài \(0\), tức là có thể có \(S'=S\).
2. Thay không hoặc nhiều ký tự trong \(S'\) thành x. Gọi xâu thu được là \(S''\).

IOI-kun không nhớ \(S\) và muốn khôi phục nó từ \(S''\). Trước hết, anh muốn đếm số xâu có thể là \(S'\), không phải \(S\).

Cho \(S''\), hãy tính số xâu khác nhau có thể là \(S'\), lấy phần dư khi chia cho \(1\,000\,000\,007\).

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\), là độ dài của xâu \(S''\).
• Dòng thứ hai chứa xâu \(S''\) có độ dài \(N\), chỉ gồm các ký tự (, ) và x.

Dữ liệu ra

In một dòng chứa số xâu có thể là \(S'\), lấy phần dư khi chia cho \(1\,000\,000\,007\). Nếu không có xâu nào thỏa mãn, in \(0\).

Ràng buộc

• \(1 \le N \le 300\).

Phân nhóm

1. \(4\) điểm: \(N \le 100\); số ký tự x trong \(S''\) không quá \(4\).
2. \(8\) điểm: \(N \le 100\); số ký tự x trong \(S''\) không quá \(12\).
3. \(18\) điểm: \(N \le 100\); số ký tự x trong \(S''\) không quá \(20\).
4. \(43\) điểm: \(N \le 100\).
5. \(27\) điểm: Không có ràng buộc bổ sung.

Ví dụ

4
x))x

3

10
xx(xx()x(x

45

5
x))x(

0

10
xxxxxxxxxx

684

Nguồn

JOI 2018, trại huấn luyện mùa xuân, ngày thi 3: Security Gate.