题目描述

我们定义一个 DNA 序列为仅有 ATCG 四个字母的字符串。

给出 $m(1 \le m \le 10)$ 个 DNA 序列模式串 $s_i$，每个长度均不超过 $10$，我们定义一个 DNA 序列 $w$ 是好的，当且仅当对于 $w$ 的每一个位置 $i$，都存在至少一个模式串 $s_j$，使得 $w[l...r] = s_j$（ $w[l...r]$ 表示一个原字符串的一个子串），其中 $1 \le l \le i \le r \le |w|$（$|w|$ 为 DNA序列 $w$ 的长度）。

请你计算出所有长度为 $n(1 \le n \le 1000)$ 的好的 DNA 序列的个数。答案对 $1000000009\ (10^9+9)$ 取模。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行一个模式串 $s_i$。

输出格式

一个整数表示答案，对 $1000000009(10^9+9)$ 取模。

2 1
A

1

6 2
CAT
TACT

2