Dãy ngoặc hợp lệ

Trong một buổi làm việc tại siêu thị, FullHouse Dev được giao nhiệm vụ kiểm tra tính hợp lệ của các mã vạch sản phẩm. Các mã vạch này được biểu diễn dưới dạng chuỗi ngoặc đơn, và họ cần phải xác định tính hợp lệ của chúng sau khi dịch chuyển.

Bài toán

Một dãy ngoặc được gọi là hợp lệ khi có thể chèn các ký tự '1' và '+' vào giữa các ký tự ngoặc để tạo thành một biểu thức số học đúng. Ví dụ, dãy ngoặc '()()' và '(())' là hợp lệ vì có thể biến đổi thành '(1)+(1)' và '((1+1)+1)'. Ngược lại, '(', ')(', và '(' là các dãy ngoặc không hợp lệ.

Cho một dãy ngoặc \(S\), nhiệm vụ của FullHouse Dev là xác định số lượng cách dịch chuyển vòng của \(S\) để tạo thành một dãy ngoặc hợp lệ.

INPUT FORMAT:

• Một dòng duy nhất chứa dãy ngoặc \(S\).

OUTPUT FORMAT:

• In ra số lượng cách dịch chuyển vòng tạo thành dãy ngoặc hợp lệ.

Ràng buộc:

• Độ dài của \(S\) không vượt quá \(10^5\)

Ví dụ

INPUT

)()()(

OUTPUT

3

Giải thích

Với mọi cách dịch chuyển vòng 3 lần, chuỗi sẽ trở thành "()()()". Đây là một dãy ngoặc hợp lệ, vì vậy đáp án là 3.