Migrated from Lutece 1709 DNA序列

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

众所周知，DNA序列是仅含有$A，C，T$和$G$的序列，分析DNA序列的一段非常有用，例如，如果动物的DNA序列含有片段$ATC$，则可能意味着可能有 一种遗传性疾病。

到目前为止，科学家已经发现了几个片段，问题是一个物种的DNA序列有多少种不包含这些片段。

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

Input

第一行包含两个整数$m(0 \leq m \leq 10)$，$n(1\leq n \leq 2000000000)$。 这里，$m$是遗传疾病段的数量，$n$是序列的长度。

接下来$m$行每行表示一个DNA遗传疾病段，并且这些段长度不为零且不大于$10$。

Output

一个整数，DNA序列数，$mod$ $100000$。

Samples

4 3
AT
AC
AG
AA

36

Resources

2017 UESTC Training for Search Algorithm & String