Một xâu ngoặc đúng được định nghĩa như sau:

• () và [] là các xâu ngoặc đúng.
• Nếu A là một xâu ngoặc đúng thì (A) và [A] cũng là các xâu ngoặc đúng.
• Nếu A và B là các xâu ngoặc đúng thì xâu nối AB cũng là một xâu ngoặc đúng.

Từ một xâu ngoặc đúng chứa ít nhất một cặp ngoặc vuông, người ta thay mọi dấu ngoặc vuông, cả dấu mở [ lẫn dấu đóng ], bằng dấu ngoặc tròn mở (. Xâu thu được gọi là xâu ngoặc hỏng.

Chẳng hạn, (( và ((((())) đều là các xâu ngoặc hỏng. Xâu thứ nhất được tạo từ []. Xâu thứ hai chỉ có thể được tạo từ bốn xâu ngoặc đúng: []((())), ([](())), (([]())) hoặc ((([]))).

Cho một xâu ngoặc hỏng, hãy đếm số xâu ngoặc đúng có thể tạo ra nó bằng phép thay thế trên.

Dữ liệu vào

Dòng đầu chứa số nguyên chẵn \(N\), độ dài của xâu ngoặc hỏng. Dòng thứ hai chứa \(N\) ký tự ( và ), mô tả xâu đó.

Dữ liệu ra

In ra một số nguyên: số xâu ngoặc đúng có thể có, lấy phần dư khi chia cho \(1\,000\,000\,009\).

Ràng buộc

• \(2 \le N \le 30\,000\) và \(N\) chẵn.
• Xâu đã cho là một xâu ngoặc hỏng theo định nghĩa trên.

Phân nhóm

• Các bộ test có \(N \le 50\) chiếm tổng cộng \(20\) điểm.
• Các bộ test có \(N \le 1000\) chiếm tổng cộng \(45\) điểm, bao gồm các bộ test ở mục trên.
• Toàn bộ các bộ test chiếm \(100\) điểm.

Ví dụ

4
((()

2

8
((((((((

14