括号序列

题目描述 给一个由左右括号构成的字符串�，对于每一个位置�，输出有多少个子串，满足这 个子串是一个合法的括号序列，并且�这个位置在子串中。

其中合法的括号序列定义如下：

• 空串是合法的。

• 如果�是合法的，那么(�)也是合法的。

• 如果�, �是合法的，那么��也是合法的。

输入格式 一行，一个由左右括号构成的字符串�。

输出格式

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

样例输入 1 (()())

样例输出 1 49

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

样例输入输出 2 见下发文件。

数据规模 共十组数据。

对于 30%的数据，保证|�| ≤ 5000。

对于 70%的数据，保证|�| ≤ 106 。

对于 100%的数据，保证|�| ≤ 107 。