首先暴力的思路肯定是枚举每一个子串，然后暴力判断一下是否合法。鉴于字符只有 $k$ 个，$k\leq 52$，使用前缀和优化判断过程以后复杂度是 $O(n^2k)$。

然后我们把前缀和的判断部分拿出来看一下，这个前缀和的形式形如 $sum_{i,st}-sum_{j-1,st}$，只要判断这些是否全部等价。

注意到一个部分分叫做 $k=2$，我们可以把这个部分分拿出来看看有什么性质。

这样无非就是说明了项只有两个。令两个字符为 $st_1$ 与 $st_2$，也就是说，我们只要判断 $sum_{i,st1}-sum_{j-1,st1}$ 与 $sum_{i,st2}-sum_{j-1,st2}$ 是否相等。我们可以移项，然后就变成了判断 $sum_{i,st1}-sum_{i,st2}$ 与 $sum_{j-1,st2}-sum_{j-1,st2}$ 的大小关系。

后者我们可以在枚举 $i$ 的过程时使用哈希表或者 map 存储，然后每次枚举到后面的 $i$ 的时候直接调用此时答案即可。

然后我们发现这个东西推广到 $k\leq 52$ 的时候依然是成立的。我们统计所有字符的个数减去字符 $1$ 的个数，然后放到 map 里找找有没有这个元素就可以直接解决这个问题了。如果写哈希的话复杂度甚至能达到 $O(nk)$。

但是我们其实有更进一步的方法优化复杂度（其实有人提到过但是讲的不是很清楚）。这个我没试过，但是理论上是可行的：

我们考虑到，每次往后枚举一个 $i$ 只会多产生一个字符对吧。假如这个字符是字符 $1$，则除了 $1$ 以外的所有字符的总量减去它都会减少 $1$。如果不是 $1$，那么那个字符减去 $1$ 的个数会加一。

然后这个东西就转化为了区间修改和单点修改的操作，可以在线段树上解决。线段树维护这个数的哈希值，然后这样复杂度可以达到惊人的 $O(n\log k)$。但是我没写过，只能说理论可行。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int mod=1e9+7;
int ans,n,tot,cnt,sum[maxn][55],a[maxn],ct[maxn][55],tong[maxn];
char s[maxn];
struct node{
	int p[55],k;
	bool friend operator < (node x,node y){
		for(int i=1;i<=x.k;i++){
			if(x.p[i]<y.p[i])return 1;
			if(x.p[i]>y.p[i])return 0;
		}
		return 0;
	}
};
map<char,int> G;
map<node,int> M;
int main(){
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
		if(!G[s[i]])a[i]=G[s[i]]=++tot;
		else a[i]=G[s[i]];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=tot;j++)sum[i][j]=sum[i-1][j]+(a[i]==j);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=tot;j++)
			ct[i][j]=sum[i][j]-sum[i][1];
	node p;
	p.k=0;
	for(int j=1;j<=tot;j++)p.p[++p.k]=0;
	M[p]=++cnt,tong[M[p]]++;
	for(int i=1;i<=n;i++){
		p.k=0;
		for(int j=1;j<=tot;j++)p.p[++p.k]=ct[i][j];
		if(!M[p])M[p]=++cnt;
		ans+=(tong[M[p]]++),ans%=mod;
	}
	printf("%d\n",ans);
	return 0;
}