题号：NC253749
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
我们认为一个由')'和'('组成的字符串为匹配的，当且仅当可以通过添加'1'和'+'使得其变成一个合法的运算式。例如，"()()"是匹配的，因为可以变成"(1+1)+(1+1)"，而")("则不匹配。
小红定义一个匹配的括号字符串的权值为：
每次操作选择一对相邻的括号对（只能是"()"，但不能是")("），将其删除，该操作的代价为这个括号对右边的')'字符数量。
持续这个操作，将该字符串变成空串的最小代价之和，即为原字符串的权值。
例如"()()"是权值为0（先删除右边的那对括号，再删除左边的），而"(())"的权值为1。
对于非匹配的字符串，权值为0。
现在给定一个括号串，请你求出所有连续子串的权值之和。答案对
取模。
小红定义一个匹配的括号字符串的权值为：
每次操作选择一对相邻的括号对（只能是"()"，但不能是")("），将其删除，该操作的代价为这个括号对右边的')'字符数量。
持续这个操作，将该字符串变成空串的最小代价之和，即为原字符串的权值。
例如"()()"是权值为0（先删除右边的那对括号，再删除左边的），而"(())"的权值为1。
对于非匹配的字符串，权值为0。
现在给定一个括号串，请你求出所有连续子串的权值之和。答案对
输入描述:
一个由')'和'('组成的字符串，长度不超过
。
输出描述:
所有子串的权值之和。答案对取模。