很简单的板子题，本来想放个思维难度高一点的黄，结果这把是板子局。
部分分：
第一个部分分就是暴力枚举。
第二个部分分对 \(\texttt{b}\) 的位置进行枚举，然后做一下前缀和，统计一下。
第三个部分分就接近正解了，是留给会正解但不会快速幂求组合数的。
第四个部分分是给没有优化枚举 \(\texttt{c}\) 的位置的大常数做法。
正解：
显然，我们对于这种三段式子序列，通常都会根据中间那一段计算，本题恰好是中间有 \(1\) 个字母。
因此，我们可以枚举 \(\texttt{b}\) 的位置，对于 \(\texttt{a}\) 的值，我们选一个和 \(\texttt{b}\) 的值不同的字母，并记前面有 \(x\) 个这样的字母，计算 \(C(x,n)\) 即为 \(\texttt{a}\) 的取法。这里要对所有字母的数量进行前缀和，记为 \(f\) 。
然后对于 \(\texttt{c}\) 的取法，我们对字母的数量进行后缀和，记为 \(h\) 。那么既然前面两个字母已经被占用了，那么 \(\texttt{c}\) 就只能取剩下 \(24\) 个字母，于是将后面总字母数减去 \(h[ \texttt{a} ]\) 与 \(h[ \texttt{b} ]\) ，就是 \(\texttt{c}\) 的取法。这样就省掉了枚举 \(\texttt{c}\) 的一重循环。
然后每一位算一下贡献即可。
注意要用快速幂算组合数，如果用递推会 MLE 。
时间为 \(O(26m)\) 。
代码：
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int f[1000005],g[1000005],l[1000005][30],r[1000005][30],n;
long long ans=0;
string s;
long long qpow(long long a,long long b)
{
long long res=1;
while(b)
{
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res%mod;
}
void init()
{
f[0]=g[0]=1;
for(int i=1;i<=1000000;i++)
{
f[i]=1ll*f[i-1]*i%mod;
g[i]=1ll*g[i-1]*qpow(i,mod-2)%mod;
}
}
long long getc(long long n,long long m)
{
return 1ll*f[n]*g[n-m]%mod*g[m]%mod;
}
int main()
{
freopen("prove.in","r",stdin);
freopen("prove.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
init();
cin>>n;
cin>>s;
for(int i=1;i<s.length();i++)
{
for(int j=0;j<26;j++)
{
l[i][j]=l[i-1][j];
}
l[i][s[i-1]-'a']++;
}
for(int i=s.length()-2;i>=0;i--)
{
for(int j=0;j<26;j++)
{
r[i][j]=r[i+1][j];
}
r[i][s[i+1]-'a']++;
}
char a,b;
for(int i=1;i<s.length()-1;i++)
{
b=s[i];
for(int j=0;j<26;j++)
{
a=j+'a';
if(a!=b&&l[i][j]>=n)ans+=1ll*getc(l[i][j],n)%mod*(1ll*(s.length()-i-1-r[i][j]-r[i][b-'a']))%mod;
ans%=mod;
}
}
cout<<ans%mod;
return 0;
}