"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.PrintStream;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;

/**
 * Created by andywu on 12/19/14.
 */
public class Main {
    public static void main(String[] args){
        new Main().solve(new Scanner(System.in), System.out);
    }

    static char[] dna = new char[]{'A','C','G','T'};

    private void solve(Scanner scanner, PrintStream out) {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        HashSet<String> completes = new HashSet<String>();
        HashSet<String> prefixes = new HashSet<String>();
        prefixes.add("");
        int ml = 0;
        for(int i = 0; i < m; i++){
            String s = scanner.next();
            completes.add(s);
            ml = Math.max(ml, s.length());
            for(int j = 0; j < s.length(); j++){
                prefixes.add(s.substring(0, j+1));
            }
        }
        int last = 0;
        Map<String, Integer> index = new HashMap<String, Integer>();
        for(String s : prefixes){
            index.put(s, last++);
        }
        int[][] next = new int[last][4];
        for(String s : prefixes){
            int idx = index.get(s);
            for(int i = 0; i < 4; i++){
                String x = s + dna[i];
                int start = 0;
                while (!prefixes.contains(x.substring(start))) start++;
                next[idx][i] = index.get(x.substring(start));
            }
        }
        int[] isFinish = new int[last];
        for(String s : prefixes)
            for(String t : completes){
                if(s.endsWith(t))
                    isFinish[index.get(s)] = Math.max(isFinish[index.get(s)], t.length());
            }

        int[][] dp = new int[last][ml];
        dp[index.get("")][0] = 1;
        for(int i = 0; i < n; i++){
            dp = newDp(dp, ml, last, isFinish, next);
        }
        int ans = 0;
        for(int state = 0; state < last; state++){
            ans += dp[state][0];
            if(ans >= MOD)
                ans -= MOD;
        }
        out.println(ans);
    }

    private int[][] newDp(int[][] dp, int maxToCover, int last, int[] isFinish, int[][] next) {
        int[][] newdp = new int[last][maxToCover];
        for(int oldState = 0; oldState < last; oldState++){
            for(int oldToCover = 0; oldToCover < maxToCover; oldToCover++){
                if(dp[oldState][oldToCover] == 0) continue;
                for(int i = 0; i < 4; i++){
                    int newState = next[oldState][i];
                    int newToCover = oldToCover + 1;
                    if(newToCover <= isFinish[newState]) newToCover = 0;
                    if(newToCover >= maxToCover) continue;
                    newdp[newState][newToCover] += dp[oldState][oldToCover];
                    if(newdp[newState][newToCover] > MOD) newdp[newState][newToCover] -= MOD;
                }
            }
        }
        return newdp;
    }

    static final int MOD = 1000000009;
}
  	   	  			 							 			  	 			