【题目描述】

DNA由A、C、T、G四种碱基构成。现在，科学家们已经知道m种患病基因段，问有多少种不同的长为n的DNA序列是健康的。

【输入描述】

第一行包含两个整数m(0 <= m <= 10)和n(1 <= n <= 2000000000)，意义见题目描述；

接下来m行每行1个患病基因片段，长度不超过10。

【输出描述】

输出一个整数，表示有多少长为n的健康DNA序列，若该数字大于100000，则输出其除以100000的余数即可。

【输入样例】

4 3

AT

AC

AG

AA

【输出样例】

36

DNA