码丁实验室，一站式儿童编程学习产品，寻地方代理合作共赢，微信联系：leon121393608。
【题目描述】
给出序列长度$n$，和$m$个不可以包含的子串。问长度为$n$的合法序列有多少个？序列中只可能包含$ACTG$四个字符。
【输入】
第一行两个整数$m,n$，接下来$m$行每行一个字符串表示不可以包含的子串。
【输出】
输出一行一个整数表示答案，对$100000$取模。
【输入样例】
4 3 AT AC AG AA
【输出样例】
36
【提示】
【数据规模】
对于100%的数据，$n≤2 × 10^9，m≤10$，每个不可以包含的子串长度不超过$10$。