CF86C Genetic engineering

“多维空间现在已经不流行了，反倒是遗传学问题成了潮流。”——物理学家 Woll 如此想着，于是将研究方向转向了生物信息学。在分析测序结果时，他遇到了以下有关 DNA 序列的问题。我们将 DNA 序列简化为只由大写字母 “A”、“C”、“G” 和 “T” 组成的任意字符串（当然，这只是一个简化的解释）。 设 $w$ 为一个较长的 DNA 序列，$s_1, s_2, ..., s_m$ 为若干较短 DNA 序列组成的集合。我们说集合能够过滤 $w$，当且仅当 $w$ 可以被集合中的这些序列完全覆盖。显然，字符串不同位置对应的子串可以重叠，甚至可以相互覆盖。更正式地说：令 $|w|$ 表示 $w$ 的长度，$w$ 的字符从 $1$ 编号到 $|w|$。那么对于 $w$ 的每一个位置 $i$，都存在一对下标 $l, r$（$1 \leq l \leq i \leq r \leq |w|$），使得子串 $w[l...r]$ 恰好等于集合中的某一个 $s_1, s_2, ..., s_m$。 Woll 想计算：长度为 $n$，且能被给定集合过滤的不同 DNA 序列的数量。但他不会解决这个问题。请你帮他！你的任务是：求出被集合 ${s_i}$ 过滤的长度为 $n$ 的不同 DNA 序列的数量。 由于答案可能很大，请将其模 $1000000009$ 输出。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 1000, 1 \leq m \leq 10$），分别表示字符串的长度和集合中序列的数量。 接下来的 $m$ 行，每行一个序列 $s_i$，表示集合中的 DNA 短序列。每个 $s_i$ 是长度不超过 $10$ 的非空字符串，仅包含 “A”、“C”、“G”、“T” 四个大写字母。集合中可能存在相同的字符串。

输出一个整数，表示被集合过滤的 DNA 序列的数量，对 $1000000009$ 取模。

在第一个样例中，字符串必须被 "A" 过滤。显然，只有一种字符串满足要求，即 "AA"。 在第二个样例中，正好有两种不同的字符串满足条件（见下图）。   由 ChatGPT 5 翻译