"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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class BaiC implements Runnable {
    
	//6 2
	//CAT
	//TACT	
	final int MOD = 1000000009;
	int n, m;	
	Set<String> all, end;
	int[][] next;
	int f[][][];
	
	private void solve() throws IOException {
		n = nextInt();
		m = nextInt();
		
		all = new HashSet<String>();
		end = new HashSet<String>();
		for (int i=0; i<m; i++) {
			String s = nextToken();
			end.add(s);
			for (int j=0; j<s.length(); j++)
				all.add(s.substring(0, j+1));
		}
		TreeMap<String, Integer> index = new TreeMap<String, Integer>();
		int total=0;
		index.put("", total++);
		for (String s: all) index.put(s, total++);
		all.add("");
		
		next = new int[total][4];
		//for (int[] a: next) Arrays.fill(a, -1);
		for (String s: all)
		{
			int i = index.get(s);
			//System.err.println(s + " " + i);
			for (int ch=0; ch<4; ch++) {
				String ns = s + "ACGT".charAt(ch);
				while (!all.contains(ns))
					ns = ns.substring(1);
				next[i][ch] = index.get(ns);
			}
		}
		int[] finish = new int[total];
		Arrays.fill(finish, 0);
		for (String s: all) {
			int i = index.get(s);
			for (String t: end)
				if (s.endsWith(t))
					finish[i] = Math.max(finish[i], t.length());
		}
		
		f = new int[2][total][11];
		int cur=0;
		f[cur][0][0] = 1;		
		for (int len=1; len<=n; len++) {
			cur=1-cur;			
			for (int j=0;j<total;j++) Arrays.fill(f[cur][j], 0);
			
			for (int state=0; state<total; state++)
				for (int i=0; i<10; i++) if (f[1-cur][state][i]>0) {
					
					for (int ch=0;ch<4;ch++) {
						int nState = next[state][ch];
						//System.err.println(state + " " + ch + " " + nState);
						int ni = i+1;
						if (ni<=finish[nState]) ni = 0;
						f[cur][nState][ni] += f[1-cur][state][i];
						if (f[cur][nState][ni]>=MOD) f[cur][nState][ni]-=MOD;
					}					
				}
			
			for (int i=0; i<total; i++) {
				//System.err.print(i + " " + f[cur][i][0] + "\t");
			}
			//System.err.print("\n");
		}
		
		int res = 0;
		for (int i=0; i<total; i++) {
			res = (res + f[cur][i][0]) % MOD;
		}
		writer.println(res);
	}
	
	
    public static void main(String[] args) {
        new BaiC().run();
    }

    BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter writer;

    public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            writer = new PrintWriter(System.out);
            solve();
            reader.close();
            writer.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
}