Tô màu dãy ngoặc

Cho một dãy ngoặc đúng $s$ chỉ gồm các ký tự "(" và ")". Một dãy ngoặc được gọi là đúng nếu có thể chèn thêm số và toán tử để thu được một biểu thức toán học hợp lệ (ví dụ "(())()" và "()" là đúng, còn ")()" và "(()" là sai). Trong một dãy ngoặc đúng, mỗi dấu ngoặc mở tương ứng với đúng một dấu ngoặc đóng khớp với nó và ngược lại.

Bạn được phép tô màu một số dấu ngoặc sao cho thỏa mãn đồng thời cả ba điều kiện sau:

• Mỗi dấu ngoặc hoặc không được tô màu, hoặc được tô màu đỏ, hoặc được tô màu xanh.
• Với mỗi cặp ngoặc khớp nhau, đúng một trong hai dấu được tô màu (dấu còn lại không tô).
• Hai dấu ngoặc kề nhau (đứng liền nhau trong dãy) mà cùng được tô màu thì không được cùng màu.

Hãy đếm số cách tô màu khác nhau thỏa mãn các điều kiện trên. Hai cách tô được coi là khác nhau nếu có ít nhất một dấu ngoặc khác màu (kể cả trạng thái không tô). Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

Một dòng duy nhất chứa xâu $s$ là một dãy ngoặc đúng.

Dữ liệu ra

In ra một số nguyên duy nhất là số cách tô màu hợp lệ, lấy phần dư theo modulo ${10}^9+7$.

Ràng buộc

• $2\le |s|\le 700$
• $|s|$ là số chẵn và $s$ luôn là một dãy ngoặc đúng.

Ví dụ