首先定义状态f[i][j]表示长度为i的串以j为结尾有多少符合条件的串，发现$f[i][j]=\sum f[i-1][k]$(j和k可以相邻)，这个用矩阵乘法优化一下即可。

1 #include
2 using namespace std;
3 #define ll long long
4 #define mod 1000000007
5 struct ji{
6 ll a[31][31];
7 }a,b,c;
8 ll n,ans;
9 char s[100001];
10 ji cheng(ji a,ji b){
11 memset(c.a,0,sizeof(c.a));
12 for(int i=0;i<26;i++) 13 for(int j=0;j<26;j++) 14 if (a.a[i][j]) 15 for(int k=0;k<26;k++)c.a[i][k]=(c.a[i][k]+a.a[i][j]*b.a[j][k])%mod; 16 return c; 17 } 18 int main(){ 19 scanf("%lld%s",&n,s); 20 for(int i=0;i<26;i++) 21 for(int j=0;j<26;j++)a.a[i][j]=1; 22 for(int i=0;s[i+1];i++)a.a[s[i]-'a'][s[i+1]-'a']=0; 23 for(int i=0;i<26;i++)b.a[i][i]=1; 24 for(n--;n;n>>=1){
25 if (n&1)b=cheng(b,a);
26 a=cheng(a,a);
27 }
28 for(int i=0;i<26;i++)
29 for(int j=0;j<26;j++)ans=(ans+b.a[i][j])%mod;
30 printf("%lld",ans);
31 }