"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.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.Set;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Solution {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }
}

class Task
{
    public void solve(int testNumber, InputReader in, PrintWriter out)
    {
        int n = in.nextInt();
        int m = in.nextInt();
        String[] Viruses = new String[m];
        for (int i = 0; i < m; i++)
        {
            Viruses[i] = in.nextToken();
        }
        HashMap<String, Integer> Index = new HashMap<String, Integer>();
        int lastIndex = 1;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < Viruses[i].length(); j++)
            {
                Index.put(Viruses[i].substring(0, j + 1), lastIndex++);
            }
        }
        Index.put("",0);
        int[][] replaceMent = new int[lastIndex][26];
        int[] longestSuffix = new int[lastIndex];
        //Найдем строку, которая заканчиывает каждый префикс и является наибольшей:
        for (String s : Index.keySet())
            for (String t : Viruses)
                if (s.endsWith(t))
                    longestSuffix[Index.get(s)] = Math.max(longestSuffix[Index.get(s)], t.length());

        //Допустим мы в позиции I, и пишем букву CH. Найдем максимальный префикс который в итоге получитcя:

        for (String s : Index.keySet()) {
            int start = Index.get(s);
            for (char ch = 'A'; ch <= 'Z'; ch++) {
                String candidate=s.concat(Character.toString(ch));//берем по максимуму
                while (!Index.containsKey(candidate))
                    candidate = candidate.substring(1);//отрезаем первый символ
                replaceMent[start][ch-'A'] = Index.get(candidate);
            }
        }

        int[][] dp = new int[lastIndex][20]; //За состояние в индексе I примем последний
                                                //префикс И удаленность первого ненакрытого символа
        int modulo=1000000009;
        dp[Index.get("")][0] = 1;//Существует ровно одна пустая строка
        for (int idx = 0; idx < n; ++idx) {
            int[][] newDp = new int[lastIndex][20];
            for (int oldprefix = 0; oldprefix < lastIndex; oldprefix++)
                for (int oldCover = 0; oldCover < 20; oldCover++) {
                    for (char ch='A'; ch <='Z'; ch++) {
                        int newPrefix = replaceMent[oldprefix][ch-'A'];
                        int newCover = oldCover + 1; //теперь нам надо на 1 больше,так как мы продвинулись на 1
                        if (newCover <= longestSuffix[newPrefix])
                            newCover = 0;//если мы накрыли то что было ненакрыто, то we are happy!
                        if (newCover >=20)//тяжелый случай
                            continue;
                        newDp[newPrefix][newCover] = (newDp[newPrefix][newCover]+dp[oldprefix][oldCover])%modulo;

                    }
                }
            dp=newDp;
            //cnt = oneStep(cnt, maxLength, last, isFinish, next);
        }
        int answer = 0;
        for (int i = 0; i < lastIndex; i++) {
            answer = (answer+dp[i][0])%modulo;

        }
        out.println(answer);
    }
}

class InputReader {
    StringTokenizer st;
    BufferedReader in;
    public InputReader(InputStream ins)
    {
        in = new BufferedReader(new InputStreamReader(ins));
    }

    public String nextToken()
    {
        while(st==null || !st.hasMoreTokens())
        {
            try {
                st=new StringTokenizer(in.readLine());
            } catch (IOException e) {
                e.printStackTrace();  //To change body of catch statement use File | Settings | File Templates.
            }
        }
        return st.nextToken();
    }
    public int nextInt()
    {

        return Integer.parseInt(nextToken());
    }

    }

