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 an 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 consists 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 ≤ 2 × 109). Here, m is the number of genetic disease segment, and n is the length of sequences.
Each of the next m lines contains a DNA genetic disease segment, and lengths of these segments are not larger than 10.
An integer, the number of DNA sequences, mod 100000.