poj 2778 DNA Sequence AC自动机

DNA Sequence

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 11860   Accepted: 4527

Description

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 a 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 consist of A, C, T and G,and the length of sequences is a given integer n.

Input

First line contains two integer m (0 <= m <= 10), n (1 <= n <=2000000000). Here, m is the number of genetic disease segment, and n is the length of sequences.

Next m lines each line contain a DNA genetic disease segment, and length of these segments is not larger than 10.

Output

An integer, the number of DNA sequences, mod 100000.

Sample Input

4 3
AT
AC
AG
AA

Sample Output

36
上一篇:poj 2778 DNA Sequence AC自动机DP 矩阵优化


下一篇:浅析 阿里 OceanBase 双十一 淘宝天猫 天量交易 承载能力 原理