Dãy ngoặc đúng là một dãy chỉ gồm các kí tự mở ngoặc ( và kí tự đóng ngoặc ). Dãy ngoặc đúng là dãy có thể được xây dựng dựa trên nguyên tắc sau:

• Một dãy ngoặc rỗng là dãy ngoặc đúng.
• Nếu \(A\) là dãy ngoặc đúng thì \((A)\) cũng là một dãy ngoặc đúng.
• Nếu \(A\) và \(B\) là dãy ngoặc đúng thì \(AB\) cũng là một dãy ngoặc đúng.

Ví dụ: (())() và () là dãy ngoặc đúng còn ()) không phải là một dãy ngoặc đúng.

Cho một dãy kí tự \(T\) độ dài \(n\). Dãy \(T\) chỉ bao gồm các loại kí tự (, ) và x, kí tự thứ \(i\) \((1 \leq i \leq n)\) của dãy là \(T_{i}\).

Bạn cần thực hiện các thao tác dưới đây để biến \(T\) thành một dãy ngoặc đúng.

• Đầu tiên, với mỗi vị trí \(i ~ (1 \leq i \leq n)\) mà \(T_{i} =\) x, bạn phải lựa chọn biến đổi \(T_{i}\) thành một trong hai kí tự là ( hoặc ) tuỳ ý.
• Sau đó bạn chọn một đoạn liên tiếp \(\left[ L, R \right]\) \((1 \leq L \leq R \leq n)\) và biến đổi các kí tự của dãy \(T\) trong đoạn. Với mỗi vị trí \(i\) \((L \leq i \leq R)\), nếu \(T_{i} =\) ( thì được biến đổi thành ), nếu \(T_{i} =\) ( thì được biến đổi thành ).

Hỏi có bao nhiêu cách thực hiện các thao tác trên sao cho sau khi thực hiện xong thì dãy \(T\) là một dãy ngoặc đúng. Biết rằng hai cách được xem là khác nhau khi trong hai cách tồn tại một kí tự x được biến đổi thành hai kí tự khác nhau hoặc đoạn \(\left[ L, R \right]\) được chọn trong hai cách là khác nhau.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq 4000)\).
• Dòng thứ hai gồm xâu kí tự \(T ~ (T_i \in \{\) (, ), x \(\})\).

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán. Vì kết quả có thể rất lớn nên chỉ cần đưa ra số dư khi chia kết quả cho \(({10}^9 + 7)\).

Scoring

• Subtask \(1\) (\(31\%\) số điểm): \(n \leq 18\).
• Subtask \(2\) (\(29\%\) số điểm): \(n \leq 100\).
• Subtask \(3\) (\(23\%\) số điểm): Xâu \(T\) chỉ gồm hai loại kí tự là ( và ).
• Subtask \(4\) (\(17\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
(())

1

2
xx

3

20
(xxxxxxxx(xxxxxxxxxx

1595620