“与遗传学问题不同,多维空间如今已经完全过时了”——物理学家沃尔认为,并将他的研究主题改为生物信息学。在分析测序结果时,他遇到了以下有关 DNA 序列的问题。我们进一步将DNA序列视为任意一串大写字母“A”、“C”、“G”和“T”(当然,这是一种简化的解释)。
令 w 为长 DNA 序列,s1, s2, ..., sm — 短 DNA 序列的集合。假设集合过滤器 w iff w 可以被集合中的序列覆盖。当然,串的不同位置对应的子串可以相互交叉,甚至覆盖。更正式地说:用 |w| 表示w 的长度,令 w 的符号从 1 到 |w| 编号。然后,对于 w 中的每个位置 i,存在一对索引 l、r (1 ≤ l ≤ i ≤ r ≤ |w|),使得子串 w[l ... r] 等于集合中的元素 s1、s2、...、sm 之一。
Woll想要计算给定集合过滤出的给定长度的DNA序列的数量,但他不知道如何处理。帮助他!你的任务是找到由集合 {si} 过滤的长度为 n 的不同 DNA 序列的数量。
答案可能会显得很大,因此输出它对 1000000009 求模。
输入
第一行包含两个整数 n 和 m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10) — 对应字符串的长度和集合中序列的数量。
接下来的 m 行包含集合序列 si,每行一个。每个si是一个长度不大于10的非空字符串。所有字符串均由大写字母“A”、“C”、“G”、“T”组成。该集合可能包含相同的字符串。
输出
输出应包含一个整数 - 由集合过滤的字符串数量模 1000000009 (109 + 9)。
示例
输入 #1
2 1 A
输出 #1
1
输入 #2
6 2 CAT TACT
输出 #2
2
注意
在第一个示例中,必须使用“A”过滤字符串。显然,这样的字符串只有一个:“AA”。
在第二个样本中,恰好存在两个满足条件的不同字符串(见下图)。