"Multidimensional spaces are completely out of style these days, unlike genetics problems" — thought physicist Woll and changed his subject of study to bioinformatics. Analysing results of sequencing he faced the following problem concerning DNA sequences. We will further think of a DNA sequence as an arbitrary string of uppercase letters "A", "C", "G" and "T" (of course, this is a simplified interpretation).

Let w be a long DNA sequence and s1, s2, ..., sm — collection of short DNA sequences. Let us say that the collection filters w iff w can be covered with the sequences from the collection. Certainly, substrings corresponding to the different positions of the string may intersect or even cover each other. More formally: denote by |w| the length of w, let symbols of w be numbered from 1 to |w|. Then for each position i in w there exist pair of indices l, r (1 ≤ l ≤ i ≤ r ≤ |w|) such that the substring w[l ... r] equals one of the elements s1, s2, ..., sm of the collection.

Woll wants to calculate the number of DNA sequences of a given length filtered by a given collection, but he doesn't know how to deal with it. Help him! Your task is to find the number of different DNA sequences of length n filtered by the collection {si}.

Answer may appear very large, so output it modulo 1000000009.

Input

First line contains two integer numbers n and m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10) — the length of the string and the number of sequences in the collection correspondently. 

Next m lines contain the collection sequences si, one per line. Each si is a nonempty string of length not greater than 10. All the strings consist of uppercase letters "A", "C", "G", "T". The collection may contain identical strings.

Output

Output should contain a single integer — the number of strings filtered by the collection modulo 1000000009 (109 + 9).

Examples

Input

2 1
A


Output

1


Input

6 2
CAT
TACT


Output

2

Note

In the first sample, a string has to be filtered by "A". Clearly, there is only one such string: "AA".

In the second sample, there exist exactly two different strings satisfying the condition (see the pictures below).

<image> <image>

import java.util.*;
import java.math.*;
import static java.lang.Character.isDigit;
import static java.lang.Character.isLowerCase;
import static java.lang.Character.isUpperCase;
import static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Character.isDigit;

public class Main{
    static void debug(Object...os){
        System.err.println(deepToString(os));
    }
    int M = 1000000009;
    class P{
        Object fst,snd;

        public P(Object fst,Object snd){
            this.fst=fst;
            this.snd=snd;
        }
        
    }
    void run(){
        int n=nextInt(),m=nextInt();
        String[] ss = new String[m];
        for(int i=0;i<m;i++)ss[i]=next();
        TreeSet<String> preset=new TreeSet<String>();
        preset.add("");
        for(int i=0;i<m;i++)for(int j=0;j<ss[i].length();j++)preset.add(ss[i].substring(0,j+1));
        String[] pres=preset.toArray(new String[0]);// 100
        int len=pres.length;
        P[][][] es=new P[len][11][4];
        for(int i=0;i<len;i++)for(int j=0;j<=pres[i].length();j++)for(int k=0;k<4;k++) {
            String s = pres[i] + "AGCT".charAt(k);
            boolean colvered=false;
            for(int l=0;l<m;l++)if(s.endsWith(ss[l]) && ss[l].length()>=j+1)colvered=true;
            for(int l=0;l<s.length();l++) {
                int p = binarySearch(pres,s.substring(l));
                if(p>=0) {
                    if(s.length()-l-1>=j) {
                        es[i][j][k] = new P(p,colvered ? 0 : j+1);
                    }
                    break;
                }
            }
        }
        long[][][] dp=new long[n+1][len][11];
        dp[0][0][0] = 1;
        for(int i=0;i<n;i++)for(int j=0;j<len;j++)for(int k=0;k<11;k++)if(dp[i][j][k]>0) {
            for(int d=0;d<4;d++)if(es[j][k][d]!=null) { 
                P p = es[j][k][d];
                int nj = (Integer)p.fst;
                int nk = (Integer)p.snd;
                dp[i+1][nj][nk] += dp[i][j][k];
                if(dp[i+1][nj][nk]>=M)dp[i+1][nj][nk]-=M;
            }
        }
        long res=0; 
        for(int i=0;i<len;i++) {
            res += dp[n][i][0];
            if(res>=M)res-=M;
        }
        System.out.println(res);
    }
    
    int nextInt(){
        try{
            int c=System.in.read();
            if(c==-1) return c;
            while(c!='-'&&(c<'0'||'9'<c)){
                c=System.in.read();
                if(c==-1) return c;
            }
            if(c=='-') return -nextInt();
            int res=0;
            do{
                res*=10;
                res+=c-'0';
                c=System.in.read();
            }while('0'<=c&&c<='9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }
    
    long nextLong(){
        try{
            int c=System.in.read();
            if(c==-1) return -1;
            while(c!='-'&&(c<'0'||'9'<c)){
                c=System.in.read();
                if(c==-1) return -1;
            }
            if(c=='-') return -nextLong();
            long res=0;
            do{
                res*=10;
                res+=c-'0';
                c=System.in.read();
            }while('0'<=c&&c<='9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }
    
    double nextDouble(){
        return Double.parseDouble(next());
    }
    
    String next(){
        try{
            StringBuilder res=new StringBuilder("");
            int c=System.in.read();
            while(Character.isWhitespace(c))
                c=System.in.read();
            do{
                res.append((char)c);
            }while(!Character.isWhitespace(c=System.in.read()));
            return res.toString();
        }catch(Exception e){
            return null;
        }
    }
    
    String nextLine(){
        try{
            StringBuilder res=new StringBuilder("");
            int c=System.in.read();
            while(c=='\r'||c=='\n')
                c=System.in.read();
            do{
                res.append((char)c);
                c=System.in.read();
            }while(c!='\r'&&c!='\n');
            return res.toString();
        }catch(Exception e){
            return null;
        }
    }
    public static void main(String[] args){
        new Main().run();
    }
}
