It’s well known that DNA Sequence is a sequence only contains A, C, T and G, and it’s very useful to analyze a segment of DNA Sequence,For example, if a animal’s DNA sequence contains segment ATC then it may mean that the animal may have a genetic disease. Until now scientists have found several those segments, the problem is how many kinds of DNA sequences of a species don’t contain those segments.

Suppose that DNA sequences of a species is a sequence that consist of A, C, T and G,and the length of sequences is a given integer n.


First line contains two integer m (0 <= m <= 10), n (1 <= n <=2000000000). Here, m is the number of genetic disease segment, and n is the length of sequences.

Next m lines each line contain a DNA genetic disease segment, and length of these segments is not larger than 10.


An integer, the number of DNA sequences, mod 100000.

Sample Input

Sample Output


和上午做的一题完全相同 只不过这次改成了求不会出现的个数 而且这个n这么大 然后字符串的长度这么小可以想象到用矩阵快速幂优化下dp转移即可ac 另外意识到取模真的很慢..



退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下