# P5337 [TJOI2019]甲苯先生的字符串

```#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define IOS std::ios::sync_with_stdio(0)
using namespace std;
const int N =1e5+5,mod=1e9+7;
#define int long long
bool ch[30][30];
int n,m;
char s[N] ;
struct matrix {
int a[30+2][30+2];
};
matrix m1;

void init_(matrix &x){
int i,j;
for(i=1;i<=26;i++)
for(j=1;j<=26;j++) {
x.a[i][j]=0;
if(i==j) x.a[i][j]=1;
}
}
matrix mul(matrix &x,matrix &y){
int i,j,k;
matrix z;

for(i=1;i<=26;i++)
for(j=1;j<=26;j++){
z.a[i][j]=0;
for(k=1;k<=26;k++)
z.a[i][j]+=x.a[i][k]*y.a[k][j]%mod, z.a[i][j]%=mod;
}

return z;
}
matrix ksm(matrix &x,int k){
matrix tmp=x, ans;
init_(ans);

while(k){
if(k&1) ans=mul(ans,tmp);

tmp=mul(tmp,tmp);
k/=2;
}
return ans;
}

signed main(){
cin>>n;
matrix Z;
int i,j;
for(i=1;i<=26;i++)
for(j=1;j<=26;j++) Z.a[i][j]=1;
cin>>s+1; m=strlen(s+1);

for(i=2;i<=m;i++){
char c1=s[i]-"a"+1,c2=s[i-1]-"a"+1 ;
Z.a[c2][c1]=0;
}
matrix F;
for(j=1;j<=26;j++) F.a[1][j] =1;

matrix tmp =ksm(Z,n-1) ;
F=mul(F,tmp);

int ans=0;
for(i=1;i<=26;i++)
ans+= F.a[1][i],ans%=mod;
cout<<ans<<endl;
}

```