{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"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.\r\u003cbr\u003e\r\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.\r\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"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.\r\u003cbr\u003e\r\u003cbr\u003eNext m lines each line contain a DNA genetic disease segment, and length of these segments is not larger than 10.\r\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"An integer, the number of DNA sequences, mod 100000."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 3\r\nAT\r\nAC\r\nAG\r\nAA\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e36\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}