如题

#include<bits/stdc++.h>
using namespace std;
int f[26],A[26][26];
const int M=1e9+7;
void mul(){
    int c[26];
    memset(c,0,sizeof c);
    for(int i=0;i<26;i++)
        for(int j=0;j<26;j++){
            c[i]=(1ll*c[i]+1ll*f[j]*A[j][i]%M)%M;
        }
    memcpy(f,c,sizeof c);
}
void mulself(){
    int c[26][26];
    memset(c,0,sizeof c);
    for(int i=0;i<26;i++)
        for(int j=0;j<26;j++)
            for(int k=0;k<26;k++)
                c[i][j]=(1ll*c[i][j]+1ll*A[i][k]*A[k][j]%M)%M;
    memcpy(A,c,sizeof c);
}
void qmi(int n){
    while(n){
        if(n&1)mul();
        mulself();
        n>>=1;
    }
}
int n;
char s1[100010];
int main(){
    cin>>n>>s1;
    int m=strlen(s1);
    if(n==0){
        cout<<0;return 0;
    }
    for(int i=0;i<26;i++){
        f[i]=1;
        for(int j=0;j<26;j++)A[i][j]=1;
    }
    //for(int i=0;i<n;i++)cout<<s1[i]-'a'<<' ';
    
    for(int i=1;i<m;i++)A[(s1[i-1]-'a')][(s1[i]-'a')]=0;
    qmi(n-1);
    int ans=0;
    for(int i=0;i<26;i++)ans=(1ll*ans+f[i])%M;
    cout<<ans;
}