自动机+dp
dp[i][j][k]在i节点字符串长度为j最小的未匹配位置k

/f[u]=r,r������u�ĺ�׺��
/last[u]=r,r������u�ĺ�׺�У�������һ������
ÿ����һ����ĸ��״̬ת��һ��
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef __int64 LL;
const int mod=1e9+9;
const int MN=10*11+10;
const int SZ=4;
int ch[MN][SZ];int val[MN];
int sz,tot;
void init(){tot=1;sz=4;memset(ch[0],0,sizeof(ch[0]));val[0]=0;}
int idx(char c){if(c=='A')return 0;if(c=='G')return 1;if(c=='C')return 2;return 3;
}
void Ins(char *s,int v){int u=0,n=strlen(s);for(int i=0;i<n;i++){int c=idx(s[i]);if(!ch[u][c]){memset(ch[tot],0,sizeof(ch[tot]));val[tot]=0;ch[u][c]=tot++;}u=ch[u][c];}val[u]=n;
}
int f[MN],last[MN],dep[MN];
int getFail(){queue<int> qq;f[0]=0;last[0]=0;dep[0]=0;for(int c=0;c<sz;c++){int u=ch[0][c];if(u){dep[u]=1;f[u]=0;last[u]=0;qq.push(u);}}while(!qq.empty()){int r=qq.front();qq.pop();for(int c=0;c<sz;c++){int u=ch[r][c];if(!u){ch[r][c]=ch[f[r]][c];continue;}dep[u]=dep[r]+1;qq.push(u);int v=f[r];while(v&&!ch[v][c])v=f[v];f[u]=ch[v][c];last[u]=val[f[u]]?f[u]:last[f[u]];//val[u]|=val[f[u]];val[u]=max(val[u],val[f[u]]);}}
}int dp[1000+1][MN][12];
char ss[15];
int main(){#ifdef DouBifreopen("in.cpp","r",stdin);#endif // DouBiint n,m;while(scanf("%d%d",&n,&m)!=EOF){init();for(int i=0;i<m;i++){scanf("%s",ss);Ins(ss,1);}getFail();memset(dp,0,sizeof(dp));dp[0][0][0]=1;for(int i=0;i<n;i++){for(int j=0;j<tot;j++){for(int k=0;k<=dep[j];k++)if(dp[i][j][k]){for(int c=0;c<sz;c++){int v=ch[j][c];if(dep[v]<k+1)continue;if(val[v]>=k+1){dp[i+1][v][0]+=dp[i][j][k];dp[i+1][v][0]%=mod;}else {dp[i+1][v][k+1]+=dp[i][j][k];dp[i+1][v][k+1]%=mod;}}}}}LL ans=0;for(int i=0;i<tot;i++){ans+=dp[n][i][0];ans%=mod;}printf("%I64d\n",ans);}return 0;
}