已经没有什么好害怕的了

先观察一下性质，会发现如果一个右括号在原序列中匹配到的是某一个左括号，那么他怎么匹配都是那个左括号。如果原序列中他匹配不到，那在所有子串中他都匹配不到。

还有一个难发现的。我们通过括号的嵌套情况分层，那么在所有子串中，嵌套情况不会变。

我们不妨分治地做。首先用一个栈求出一个右括号所匹配的左括号，一个左括号所匹配的右括号。然后分治每一个区间 \([l,r]\)，每次把区间 \([l,r]\) 最外层的那一些括号进行处理后，再进入到下一层处理。

具体而言，我们统计答案是肯定要用差分的。对于一个左括号，我们需要知道有多少个括号序列从这里开始。那么在分治的某一层中，也就是问在这个左括号的后面，下一个不合法括号的前面，有多少个同一层合法的右括号。我们可以通过不停地跳括号的方式来实现。右括号同理。

那么最后求差分数组前缀和就行了。

#include<bits/stdc++.h>
const int N=1e6+5,P=1e9+7;
int t,n,st[N],tp,lst[N],nxt[N];
long long ans,f[N];
char s[N];
void solve(int l,int r)
{
	if(l>=r)
		return;
	int k(0);
	for(int i=r;i>=l;i--)
	{
		if(lst[i])
		{
			solve(lst[i]+1,i-1);
			++k;
			f[lst[i]]+=k;
			i=lst[i];
		}
		else
			k=0;
	 } 
}
void calc(int l,int r)
{
	if(l>r)
		return;
	int k(0);
	for(int i=l;i<=r;i++)
	{
		if(nxt[i])
		{
			calc(i+1,nxt[i]-1);
			++k;
			f[nxt[i]+1]-=k;
			i=nxt[i];
		}
		else
			k=0;
	}
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",s+1),tp=ans=0;
		n=strlen(s+1);
		memset(f,0,sizeof(f));
		memset(lst,0,sizeof(lst));
		memset(nxt,0,sizeof(nxt));
		for(int i=1;i<=n;i++)
		{
			if(s[i]=='(')
				st[++tp]=i;
			else if(tp)
				lst[i]=st[tp],nxt[st[tp]]=i,--tp;
		}
		solve(1,n);
		calc(1,n);
		for(int i=1;i<=n;i++)
		{
			f[i]+=f[i-1];
			ans+=(1LL*f[i]%P*i)%P;
		}
		printf("%lld\n",ans);
	}
}