package main

import (
	"bufio"
	"fmt"
	"os"
)

const MOD = 1000000009

type Node struct {
	next [4]int
	fail int
	own  int
	out  int
}

func newNode() Node {
	return Node{next: [4]int{-1, -1, -1, -1}}
}

func id(c byte) int {
	switch c {
	case 'A':
		return 0
	case 'C':
		return 1
	case 'G':
		return 2
	default:
		return 3
	}
}

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	var n, m int
	if _, err := fmt.Fscan(in, &n, &m); err != nil {
		return
	}

	seen := make(map[string]bool)
	patterns := make([]string, 0, m)
	L := 0
	for i := 0; i < m; i++ {
		var s string
		fmt.Fscan(in, &s)
		if !seen[s] {
			seen[s] = true
			patterns = append(patterns, s)
			if len(s) > L {
				L = len(s)
			}
		}
	}

	nodes := []Node{newNode()}
	for _, s := range patterns {
		v := 0
		for i := 0; i < len(s); i++ {
			c := id(s[i])
			if nodes[v].next[c] == -1 {
				nodes = append(nodes, newNode())
				nodes[v].next[c] = len(nodes) - 1
			}
			v = nodes[v].next[c]
		}
		if len(s) > nodes[v].own {
			nodes[v].own = len(s)
		}
	}

	q := make([]int, 0, len(nodes))
	for c := 0; c < 4; c++ {
		u := nodes[0].next[c]
		if u == -1 {
			nodes[0].next[c] = 0
		} else {
			nodes[u].fail = 0
			q = append(q, u)
		}
	}

	for head := 0; head < len(q); head++ {
		v := q[head]
		nodes[v].out = nodes[v].own
		if nodes[nodes[v].fail].out > nodes[v].out {
			nodes[v].out = nodes[nodes[v].fail].out
		}
		f := nodes[v].fail
		for c := 0; c < 4; c++ {
			u := nodes[v].next[c]
			if u == -1 {
				nodes[v].next[c] = nodes[f].next[c]
			} else {
				nodes[u].fail = nodes[f].next[c]
				q = append(q, u)
			}
		}
	}

	maskCount := 1 << (L - 1)
	totalStates := len(nodes) * maskCount

	suffixMask := make([]int, L+1)
	for l := 1; l <= L; l++ {
		suffixMask[l] = ((1 << l) - 1) << (L - l)
	}

	nextNoCheck := make([]int, totalStates*4)
	nextCheck := make([]int, totalStates*4)

	for node := 0; node < len(nodes); node++ {
		stateBase := node * maskCount
		for c := 0; c < 4; c++ {
			nn := nodes[node].next[c]
			add := 0
			if nodes[nn].out > 0 {
				add = suffixMask[nodes[nn].out]
			}
			destBase := nn * maskCount
			for mask := 0; mask < maskCount; mask++ {
				s := stateBase + mask
				p := s*4 + c
				temp := mask | add
				nm := temp >> 1
				ns := destBase + nm
				nextNoCheck[p] = ns
				if temp&1 != 0 {
					nextCheck[p] = ns
				} else {
					nextCheck[p] = -1
				}
			}
		}
	}

	cur := make([]int, totalStates)
	nxt := make([]int, totalStates)
	cur[0] = 1

	for i := 1; i <= n; i++ {
		for j := 0; j < totalStates; j++ {
			nxt[j] = 0
		}
		trans := nextNoCheck
		if i >= L {
			trans = nextCheck
		}
		for s, val := range cur {
			if val == 0 {
				continue
			}
			b := s * 4

			ns := trans[b]
			if ns >= 0 {
				x := nxt[ns] + val
				if x >= MOD {
					x -= MOD
				}
				nxt[ns] = x
			}

			ns = trans[b+1]
			if ns >= 0 {
				x := nxt[ns] + val
				if x >= MOD {
					x -= MOD
				}
				nxt[ns] = x
			}

			ns = trans[b+2]
			if ns >= 0 {
				x := nxt[ns] + val
				if x >= MOD {
					x -= MOD
				}
				nxt[ns] = x
			}

			ns = trans[b+3]
			if ns >= 0 {
				x := nxt[ns] + val
				if x >= MOD {
					x -= MOD
				}
				nxt[ns] = x
			}
		}
		cur, nxt = nxt, cur
	}

	needMask := 0
	start := n - L + 2
	for j := 0; j < L-1; j++ {
		if start+j > 0 {
			needMask |= 1 << j
		}
	}

	ans := 0
	for node := 0; node < len(nodes); node++ {
		base := node * maskCount
		for mask := 0; mask < maskCount; mask++ {
			if mask&needMask == needMask {
				ans += cur[base+mask]
				if ans >= MOD {
					ans -= MOD
				}
			}
		}
	}

	fmt.Fprintln(out, ans)
}