给一个由左右括号构成的字符串 s ，对于每一个位置 i ，输出有多少个子串，满足这个子串是一个合法的括号序列，并且 i 这个位置在子串中。其中合法的括号序列定义如下：
• 空串是合法的。
• 如果 S 是合法的，那么 (S) 也是合法的。
• 如果 U, V 是合法的，那么 UV 也是合法的。

一行，一个由左右括号构成的字符串 S 。

由于答案可能很大，输出 ∑(i⋅ ans[i] mod (10^9 + 7)) 即可，其中 ans[i] 表示第 i 个位置的答案。注意这里我们要先取模，再相加。

(()())

49

样例解释
这里的 ans 分别为 1,3,3,3,3,1。

数据规模
共十组数据。
对于 30%的数据，保证 |S| ≤ 5000。
对于 70%的数据，保证 |S| ≤ 10^6。
对于 100%的数据，保证 |S| ≤ 10^7。