^^# Background

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

Format

Input

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

Output

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

Samples

(()())

49

样例解释

这里的ans分别为1，3，3，3，3，1.

样例输入输出2

见下发文件

Limitation

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