题目描述

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

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

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

输入格式

从文件 bracket.in 中读入数据。

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

输出格式

将答案输出到文件 bracket.out 中。

由于答案可能很大，输出

即可，其中 $ans_i$ 表示第 $i$ 个位置的答案。注意这里我们要先取模，再相加。

样例

(()())

49

样例 2 输入输出

见下发文件。

样例解释

样例 1 中，$ans$ 分别为 $1,3,3,3,3,1$。

数据范围

共十组数据。

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

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

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