"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.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class GeneticEngineering {
    static class Node {
        int id;
        Node fail;
        Node[] child;
        ArrayList<Integer> indices;
        boolean[] chars;

        public Node() {
            child = new Node[256];
            indices = new ArrayList<Integer>();
            chars = new boolean[256];
            id = -1;
        }

        void insert(String str, int index, int charIndex) {
            if (charIndex == str.length())
                indices.add(index);
            else {
                if (child[str.charAt(charIndex)] == null) {
                    child[str.charAt(charIndex)] = new Node();
                    chars[str.charAt(charIndex)] = true;
                }
                child[str.charAt(charIndex)].insert(str, index, charIndex + 1);
            }
        }
    }

    static Node build(ArrayList<String> words) {
        Node root = new Node();
        for (int i = 0; i < words.size(); i++)
            root.insert(words.get(i), i, 0);
        Queue<Node> q = new LinkedList<Node>();
        for (int i = 45; i < 125; i++) {
            if (root.child[i] == null)
                root.child[i] = root;
            else {
                q.add(root.child[i]);
                root.child[i].fail = root;
            }
        }
        while (!q.isEmpty()) {
            Node front = q.remove();
            for (int i = 45; i < 125; i++) {
                if (!front.chars[i])
                    continue;
                q.add(front.child[i]);
                Node temp = front.fail;
                while (temp.child[i] == null)
                    temp = temp.fail;
                temp = temp.child[i];
                front.child[i].fail = temp;
                front.child[i].indices.addAll(temp.indices);
            }
        }
        return root;
    }

    public static void dfs(Node n) {
        if (n.id != -1)
            return;
        n.id = id;
        nodes[id++] = n;
        for (int i = 45; i < 125; i++)
            if (n.chars[i]) {
                dfs(n.child[i]);
            }
    }

    static int id, n;
    static Node[] nodes = new Node[110];
    static char[] valid = { 'A', 'C', 'G', 'T' };
    static ArrayList<String> arr;
    static Integer[][][] dp = new Integer[1001][101][11];
    static int mod = 1000000009;

    public static int go(int index, int nodeId, int back) {
        if (back > 10)
            return 0;
        if (index == n) {
            if (back == 0)
                return 1;
            return 0;
        }
        if (dp[index][nodeId][back] != null)
            return dp[index][nodeId][back];
        int res = 0;
        for (char c : valid) {
            Node n = nodes[nodeId];
            while (n.child[c] == null)
                n = n.fail;
            n = n.child[c];
            int nB = back + 1;
            for (int ind : n.indices) {
                if (arr.get(ind).length() >= back + 1) {
                    nB = 0;
                }
            }
            res += go(index + 1, n.id, nB);
            res %= mod;
        }
        return dp[index][nodeId][back] = res;
    }

    public static void main(String[] args) {
        InputReader r = new InputReader(System.in);
        n = r.nextInt();
        int m = r.nextInt();
        arr = new ArrayList<String>();
        for (int i = 0; i < m; i++) {
            arr.add(r.next());
        }
        Node root = build(arr);
        dfs(root);
        System.out.println(go(0, 0, 0));
    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
                return null;
            }
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}
