$描述$
众所周知，$DNA$序列是仅包含$A、C、T$和$G$的序列，分析一段$DNA$序列非常有用。例如，如果某动物的$DNA$序列中包含片段$ATC$，可能意味着该动物患有某种遗传疾病。目前科学家已发现若干这类片段，问题是：求某物种长度为$n$的$DNA$序列中，不包含任何这些片段的序列数量。

假设该物种的$DNA$序列由$A$、$C$、$T$和$G$组成，且序列长度为给定整数$n$。

$输入$
第一行包含两个整数$m$（$0 \leq m \leq 10$）和$n$（$1 \leq n \leq 2000000000$）。其中，$m$是遗传疾病片段的数量，$n$是序列长度。
接下来$m$行，每行包含一个$DNA$遗传疾病片段，且这些片段的长度不超过$10$。

$输出$
一个整数，表示满足条件的$DNA$序列数量，结果对$100000$取模。

输入数据

4 3
AT
AC
AG
AA

输出数据

36