{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"众所周知,DNA序列是仅包含A、C、T和G的序列,对于分析DNA序列的一个片段非常有用。例如,如果一个动物的DNA序列包含片段ATC,那么这可能意味着这个动物可能患有遗传疾病。到目前为止,科学家已经发现了几个这样的片段,问题是一个物种的DNA序列中有多少种不包含这些片段的序列。\r\u003cbr\u003e\r\u003cbr\u003e假设一个物种的DNA序列是由A、C、T和G组成的序列,序列的长度是给定的整数n。"}},{"title":"输入","value":{"format":"HTML","content":"第一行包含两个整数m(0 \u003c\u003d m \u003c\u003d 10)、n(1 \u003c\u003d n \u003c\u003d 2000000000)。这里,m是遗传疾病片段的数量,n是序列的长度。\r\u003cbr\u003e\r\u003cbr\u003e接下来的m行,每行包含一个DNA遗传疾病片段,这些片段的长度不超过10。"}},{"title":"输出","value":{"format":"HTML","content":"一个整数,表示DNA序列的数量,取模100000后的结果。"}},{"title":"示例","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"}}]}