| #include<cstdio> |
| #include<cstring> |
| #include<bitset> |
| #include<iostream> |
| |
| #define int long long |
| |
| const int S=32; |
| const int P=998244353; |
| |
| struct Mat{ |
| int **a; |
| int r,c; |
| Mat(const int &r,const int &c):r(r),c(c){ |
| a=new int * [r]; |
| for(int i=0;i<r;++i) |
| a[i]=new int [c](); |
| } |
| Mat(const int &r,const int &c,const int &x):Mat(r,c){ |
| for(int i=0;i<r;++i) |
| a[i][i]=x; |
| } |
| Mat(const Mat &b):Mat(b.r,b.c){ |
| for(int i=0;i<r;++i) |
| memcpy(a[i],b[i],sizeof(int)*c); |
| } |
| Mat operator * (const Mat &b)const{ |
| Mat res(r,b.c); |
| for(int i=0;i<r;++i) |
| for(int j=0;j<c;++j) |
| for(int k=0;k<b.c;++k) |
| (res[i][k]+=a[i][j]*b[j][k])%=P; |
| return res; |
| } |
| int* operator [] (const int &x){ |
| return a[x]; |
| } |
| const int* operator [] (const int &x)const{ |
| return a[x]; |
| } |
| friend Mat pow(Mat a,int b){ |
| Mat res(a.r,a.r,1); |
| for(;b;b>>=1,a=a*a) |
| if(b&1) res=a*res; |
| return res; |
| } |
| }; |
| |
| long long M,N; |
| char a[130],len[130]; |
| |
| Mat T(S,S),F(S,1),G(S,1); |
| |
| bool contain(int a,int lena,int b,int lenb){ |
| for(int i=0;i<=lena-lenb;++i,a>>=1) |
| if((a^(a>>lenb<<lenb))==b) |
| return true; |
| return false; |
| } |
| |
| bool check(int s,int lens){ |
| for(int i=1;i<=M;++i) |
| if(contain(s,lens,a[i],len[i])) |
| return false; |
| return true; |
| } |
| |
| signed main(){ |
| scanf("%lld%lld",&N,&M); |
| for(int i=1;i<=M;++i){ |
| char s[6],j; |
| scanf("%s",s); |
| for(j=0;s[j];++j) |
| a[i]=a[i]<<1|(s[j]=='b'); |
| len[i]=j; |
| } |
| if(N<=5){ |
| int ans=0; |
| for(int s=0;s<(1<<N);++s) |
| ans+=check(s,N); |
| printf("%d\n",ans); |
| return 0; |
| } |
| for(int s=0;s<32;++s){ |
| if(check(s<<1,6)) |
| T[(s<<1)&31][s]=1; |
| if(check(s<<1|1,6)) |
| T[(s<<1|1)&31][s]=1; |
| if(check(s,5)) |
| F[s][0]=1; |
| } |
| G=pow(T,N-5)*F; |
| int ans=0; |
| for(int i=0;i<S;++i) |
| (ans+=G[i][0])%=P; |
| printf("%lld\n",ans); |
| return 0; |
| } |
