下发文件

题目描述

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

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

• 空串是合法的。
• 如果 S 是合法的，那么(S) 也是合法的。
• 如果 U , V 是合法的，那么 UV 也是合法的。

输入格式

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

输出格式

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

样例1输入

(()())

样例1输出

49

样例1解释

这里的 $ans$ 分别为 $1,3,3,3,3,1$ 。

样例2输入

见下发文件。

样例2输出

见下发文件。

数据规模

共十组数据。

对于 $30\%$ 的数据，保证 $|S| ≤ 5000$ 。

对于 $70\%$ 的数据，保证 $|S| ≤ 10^6$ 。

对于 $100\%$ 的数据，保证 $|S| ≤ 10^7$ 。