"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.*;
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.fill;
import static java.util.Arrays.binarySearch;
import static java.util.Arrays.sort;

public class Main {
	public static void main(String[] args) throws IOException {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					try {
						if (new File("input.txt").exists())
							System.setIn(new FileInputStream("input.txt"));
					} catch (SecurityException e) {}
					new Main().run();
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}, "1", 1L << 24).start(); 
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");
	
	long MOD = 1000000009L;
	
	int ALPHA = 4;
	int MAXNUM = 10;
	int MAXLEN = 10;
	int MAXV = MAXNUM * MAXLEN + 1;
	int ROOT = 0;
	
	int N;
	int M;
	
	char[][] dict;
	int[][] next = new int [MAXV][ALPHA];
	int[] link = new int [MAXV];
	int[] prvt = new int [MAXV];
	int[] term = new int [MAXV];
	int vNum = 1;

	int[] cover;
	int[][] move;
	
	long[][][] dp;
	
	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		
		N = nextInt();
		M = nextInt();
		
		dict = new char [M][];
		fill(term, -1);
		for (int i = 0; i < M; i++)
			addWord(dict[i] = nextToken().toCharArray(), i);
		
		int[] queue = new int [vNum];
		int qH = 0;
		int qT = 0;
		
		for (int c = 0; c < ALPHA; c++)
			if (next[ROOT][c] != ROOT)
				queue[qT++] = next[ROOT][c];
		
		cover = new int [vNum];
		move = new int [vNum][ALPHA];
		while (qH < qT) {
			int v = queue[qH++];
			
			int word = term[v] == -1 ? term[prvt[v]] : term[v];
			if (word != -1) cover[v] = dict[word].length;
			
			for (int c = 0; c < ALPHA; c++) {
				int nv = next[v][c];
				if (nv == ROOT) continue;
				queue[qT++] = nv;
				int lnk = link[v];
				while (lnk != ROOT && next[lnk][c] == ROOT) lnk = link[lnk]; lnk = next[lnk][c];
				link[nv] = lnk;
				prvt[nv] = term[lnk] != -1 ? lnk : prvt[lnk];
			}
		}
		
		for (int v = 0; v < vNum; v++) {
			for (int c = 0; c < ALPHA; c++) {
				int lnk = v;
				while (lnk != ROOT && next[lnk][c] == ROOT) lnk = link[lnk]; lnk = next[lnk][c];
				move[v][c] = lnk;
			}
		}
		
		dp = new long [N + 1][MAXLEN + 1][vNum];
		dp[0][0][ROOT] = 1L;
		
		for (int symb = 0; symb < N; symb++) {
			for (int uncov = 0; uncov < MAXLEN; uncov++) {
				for (int v = 0; v < vNum; v++) {
					long cval = dp[symb][uncov][v];
					if (cval == 0L) continue;
					for (int c = 0; c < ALPHA; c++) {
						int nv = move[v][c];
						int nu = cover[nv] <= uncov ? uncov + 1 : 0;
						long nval = dp[symb + 1][nu][nv] + cval;
						if (nval > MOD) nval -= MOD;
						dp[symb + 1][nu][nv] = nval;
					}
				}
			}
		}
		
		long ans = 0L;
		for (int v = 0; v < vNum; v++) {
			ans += dp[N][0][v];
			if (ans > MOD) ans -= MOD;
		}
		out.println(ans);
		
		out.close();
	}
	
	void addWord(char[] w, int index) {
		int v = ROOT;
		for (char ch : w) {
			int c = c(ch);
			if (next[v][c] == ROOT) next[v][c] = vNum++;
			int nv = next[v][c];
			v = nv;
		}
		term[v] = index;
	}

	int c(char c) {
		if (c == 'A') return 0; if (c == 'C') return 1;
		if (c == 'G') return 2; if (c == 'T') return 3;
		throw new RuntimeException("Bad arg!");
	}
	
	
	/*************************************************************** 
	 * Input 
	 **************************************************************/
	String nextToken() throws IOException {
		while (!st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}
	
	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 nextLine() throws IOException {
		st = new StringTokenizer("");
		return in.readLine();
	}
	
	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String s = in.readLine();
			if (s == null)
				return true;
			st = new StringTokenizer(s);
		}
		return false;
	}
}
