题目描述

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

输入

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

输出

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

输入样例

4 3
AT
AC
AG
AA

输出样例

36

提示

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

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。