DNA序列 - ROJ

给出序列长度 $n$ ，和 $m$ 个不可以包含的子串。问长度为 $n$ 的合法序列有多少个？序列中只可能包含 $ACTG$ 四个字符。

第一行两个整数 $m,n$ ，接下来 $m$ 行每行一个字符串表示不可以包含的子串。

输出一行一个整数表示答案，对 $100000$ 取模。

4 3
AT
AC
AG
AA

【数据规模】对于100%的数据， $n≤2 × 10^9，m≤10$ ，每个不可以包含的子串长度不超过 $10$ 。