"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.*;

public class C {

	final static int MOD = 1000 * 1000 * 1000 + 9;
	static char[] chars = "ACGT".toCharArray();

	static String[] s;
	static int m;
	static HashSet<String> hs;

	public int goodCount(String s, int start) {
		for (int i = start; i < s.length(); i++) {
			boolean ok = false;
			forl: for (int l = 0; l <= i; l++) {
				for (int r = i + 1; r <= s.length(); r++) {
					String s1 = s.substring(l, r);
					if (hs.contains(s1)) {
						ok = true;
						break forl;
					}
				}
			}
			if (!ok) {
				return i;
			}
		}
		return s.length();
	}

	private void solve() throws IOException {
		int n = nextInt();
		m = nextInt();
		hs = new HashSet<String>();
		for (int i = 0; i < m; i++) {
			hs.add(nextToken());
		}
		int len = 0;
		s = (String[]) hs.toArray(new String[hs.size()]);
		for (String s1 : s) {
			len = Math.max(len, s1.length());
		}
		m = s.length;
		int[][][] dp = new int[m][][];
		int[][][] next = new int[m][][];
		for (int i = 0; i < m; i++) {
			dp[i] = new int[s[i].length() + 1][];
			next[i] = new int[s[i].length() + 1][];
			for (int j = 0; j < dp[i].length; j++) {
				dp[i][j] = new int[dp[i].length + 1];
				next[i][j] = new int[dp[i].length + 1];
			}
		}
		dp[0][0][0] = 1;
		Pair[][][][] go = new Pair[m][][][];
		for (int i = 0; i < m; i++) {
			go[i] = new Pair[s[i].length() + 1][s[i].length() + 1][4];
			for (int l = 0; l <= s[i].length(); l++) {
				for (int ok = 0; ok <= l; ok++) {
					for (int j = 0; j < 4; j++) {
						String s1 = s[i].substring(0, l) + chars[j];
						Pair p = get(s1, ok);
						go[i][l][ok][j] = p;
					}
				}
			}
		}
		for (int it = 0; it < n; it++) {
			// System.err.println((it));
			for (int i = 0; i < m; i++) {
				for (int[] next1 : next[i])
					Arrays.fill(next1, 0);
			}
			for (int i = 0; i < m; i++) {
				// System.err.println(Arrays.toString(dp[i]));
				for (int j = 0; j <= s[i].length(); j++) {
					for (int ok = 0; ok <= j; ok++) {
						if (dp[i][j][ok] == 0)
							continue;
						for (int ch = 0; ch < 4; ch++) {
							Pair p = go[i][j][ok][ch];
							if (p == null)
								continue;
							next[p.a][p.b][p.c] += dp[i][j][ok];
							if (next[p.a][p.b][p.c] >= MOD) {
								next[p.a][p.b][p.c] -= MOD;
							}
						}
					}
				}
			}
			int[][][] tmp = dp;
			dp = next;
			next = tmp;
		}
		int res = 0;
		for (int i = 0; i < m; i++) {
			// System.err.println(Arrays.toString(dp[i]));
			for (int j = 0; j <= s[i].length(); j++) {
				res += dp[i][j][j];
				if (res >= MOD) {
					res -= MOD;
				}
			}
		}
		out.println(res);
	}

	static class Pair {
		int a, b, c;

		public Pair(int a, int b, int c) {
			this.a = a;
			this.b = b;
			this.c = c;
		}
	}

	Pair get(String t, int ok) {
		for (int i = 0; i < t.length(); i++) {
			String t1 = t.substring(i);
			for (int j = 0; j < m; j++) {
				if (s[j].startsWith(t1)) {
					int len = t1.length();
					int goodcnt = goodCount(t, ok);
					goodcnt -= i;
					if (goodcnt < 0)
						return null;
					else
						return new Pair(j, len, goodcnt);
				}
			}
		}
		return null;
	}

	public static void main(String[] args) {
		new C().run();
	}

	BufferedReader br;
	StringTokenizer st;
	PrintWriter out;
	boolean eof = false;

	public void run() {
		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			st = new StringTokenizer("");
			solve();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			System.exit(239);
		}
	}

	String nextToken() throws IOException {
		while (!st.hasMoreTokens()) {
			String line = br.readLine();
			if (line == null) {
				eof = true;
				line = "0";
			}
			st = new StringTokenizer(line);
		}
		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());
	}
}