{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n It\u0027s well known that DNA Sequence is a sequence only contains A, C, T and G, and it\u0027s very useful to analyze a segment of DNA Sequence,For example, if a animal\u0027s 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\u0027t contain those segments. \n \u003cbr\u003e \n \u003cbr\u003eSuppose 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. \n \u003cbr\u003e\n \u003cbr\u003e有m种DNA序列是致病的,问长为n且不包含致病序列的DNA有多少种\n \u003cbr\u003e\n \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n First line contains two integer m (0 \u0026lt;\u003d m \u0026lt;\u003d 10), n (1 \u0026lt;\u003d n \u0026lt;\u003d2000000000). Here, m is the number of genetic disease segment, and n is the length of sequences. \n \u003cbr\u003e \n \u003cbr\u003eNext m lines each line contain a DNA genetic disease segment, and length of these segments is not larger than 10. \n \u003cbr\u003e\n \u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n An integer, the number of DNA sequences, mod 100000.\n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e4 3\nAT\nAC\nAG\nAA\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e36\u003c/pre\u003e"}}]}