{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"众所周知,DNA Sequence 是一个只包含 A、C、T 和 G 的序列,分析一段 DNA Sequence 非常有用,例如,如果一个动物的 DNA 序列包含 ATC 段,则可能意味着该动物可能有遗传病。到目前为止,科学家们已经发现了几个这样的片段,问题是一个物种有多少种 DNA 序列不包含这些片段。\n\n假设一个物种的DNA序列是一个由A、C、T、G组成的序列,序列的长度是一个给定的整数n。"}},{"title":"Input","value":{"format":"HTML","content":"第一行包含两个整数 m (0 \u003c\u003d m \u003c\u003d 10), n (1 \u003c\u003d n \u003c\u003d2000000000)。其中,m 为遗传病片段数,n 为序列长度。\n\n接下来m行每行包含一个DNA遗传疾病片段,这些片段的长度不大于10。"}},{"title":"Output","value":{"format":"HTML","content":"一个整数,DNA 序列的数量,mod 100000。"}},{"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"}}]}