Số Lượng Dãy Đẹp

Nam đang theo học môn Cấu trúc Dữ liệu. Trong các giờ học, sinh viên thường nghiên cứu các loại chuỗi khác nhau bao gồm dấu ngoặc tròn (ký tự ( và )).

Trong tiết học trước, Nam đã học về Dãy Ngoặc Cấu Trúc (DNCT). Một chuỗi ngoặc $s$ có độ dài $n$ được gọi là DNCT nếu thỏa mãn các điều kiện sau:

• Không rỗng (nghĩa là $n ≠q 0$).
• Độ dài của chuỗi là một số chẵn.
• $\frac{n}{2}$ ký tự đầu tiên của chuỗi đều bằng (.
• $\frac{n}{2}$ ký tự cuối cùng của chuỗi đều bằng ).

Ví dụ, chuỗi ((())) là một DNCT nhưng các chuỗi ((()) và (()()) không phải là DNCT.

Cô giáo Lan giao cho Nam một bài tập về nhà. Cho một chuỗi ngoặc $s$, hãy tìm số lượng các chuỗi con phân biệt của nó sao cho mỗi chuỗi con đó đều là một DNCT. Lưu ý rằng chuỗi con của $s$ là một chuỗi có thể thu được từ $s$ bằng cách xóa đi một số phần tử. Hai chuỗi con được coi là phân biệt nếu các tập hợp vị trí bị xóa là khác nhau.

Vì kết quả có thể rất lớn và cô Lan không thích những con số quá lớn, cô yêu cầu Nam tìm phần dư của kết quả khi chia cho $10^9+7$.

Nam đã suy nghĩ rất lâu nhưng vẫn chưa biết cách giải. Hãy giúp Nam giải quyết bài toán này và viết một chương trình tìm ra kết quả!

Dữ liệu vào

Dòng duy nhất của dữ liệu vào chứa một chuỗi $s$ là dãy ngoặc được cho trong bài tập của Nam ($1 ≤ |s| ≤ 200\,000$). Chuỗi này chỉ bao gồm các ký tự ( và ). Đảm bảo rằng chuỗi không rỗng.

Kết quả

In ra một số nguyên duy nhất là kết quả của bài toán theo mô-đun $10^9+7$.

Chấm điểm

Subtask 1 (20 points). erts ert $≤ 50$

Subtask 2 (30 points). erts ert $≤ 2000$

Subtask 3 (50 points). 1 $≤$|s| $≤ 200$\,000

Ví dụ

Input

(())

Output

5

Ghi chú

Trong ví dụ, các chuỗi con sau đây có thể được tạo ra:

• Nếu chúng ta xóa các ký tự ở vị trí 1 và 4 (vị trí bắt đầu đếm từ 1), chúng ta sẽ có chuỗi con ().
• Nếu chúng ta xóa các ký tự ở vị trí 1 và 3, chúng ta sẽ có chuỗi con ().
• Nếu chúng ta xóa các ký tự ở vị trí 2 và 4, chúng ta sẽ có chuỗi con ().
• Nếu chúng ta xóa các ký tự ở vị trí 2 và 3, chúng ta sẽ có chuỗi con ().
• Nếu chúng ta không xóa ký tự nào, chúng ta sẽ có chuỗi con (()).

Tất cả 5 chuỗi con thu được đều là DNCT, vì vậy kết quả là 5.