【题目链接】:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1030

【题意】

【题解】

/*

    先把AC自动机搞出来;

    然后利用AC自动机,把所有的不可读文本处理出来;

    实现方式:

        设f[i][j]表示走完i步之后(文本有了i个字母)到达j节点的方案数;

        对于节点j,如果它包含了某个单词.就忽略它;

        利用AC自动机能够轻易地搞出f数组;

    最后累加f[m][0..tot];

    用总数减去它就好;

    在搞自动机的失配函数的时候,可以把一个单词是另外一个单词的子串的情况弄出来;

    就是说不一定都是

    s[1..x]为可读单词;

    这里x<=m

    可能是s[i..j]为可读单词;

    这里i>1,j<=m

    这种情况可以在搞失配函数的时候顺便弄出来;

    需要对KMP熟练一点才能体会吧

    具体一点

    如果

    a[1..k]是一个单词

    则

    如果

    s[j-k+1..j]=这个单词的话.

    就在s[j]所在的节点打个标记;

    标记它不能再继续组成不可读串

    之后在进行DP的时候,遇到这个s[j]所代表的节点就会跳过.

    之后就不会用那个节点更新不可读节点了.

*/

【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

#define ref(x) scanf("%lf",&x)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 110;

const int MAXS = 110;

const int MOD = 1e4 + 7;

int n, m, a[N * 65][27],tot = 1,f[N*65],cnt[N*65],dp[N][N*65];

char s[MAXS];

queue <int> dl;

void in()

{

    rei(n), rei(m);

    rep1(i, 1, n)

    {

        scanf("%s", s);

        int len = strlen(s), now = 1;

        rep1(j, 0, len - 1)

        {

            int k = s[j] - 'A' + 1;

            if (!a[now][k])

                now = a[now][k] = ++tot;

            else

                now = a[now][k];

        }

        cnt[now] = 1;

    }

}

void aczidongji()

{

    rep1(i, 1, 26)

        a[0][i] = 1;

    dl.push(1), f[1] = 0;

    while (!dl.empty())

    {

        int x = dl.front();

        dl.pop();

        rep1(j, 1, 26)

        {

            if (!a[x][j])

                continue;

            int k = f[x];

            while (!a[k][j]) k = f[k];

            f[a[x][j]] = a[k][j];

            dl.push(a[x][j]);

            if (cnt[a[k][j]])

                cnt[a[x][j]] = 1;

        }

    }

}

void do_dp_ando()

{

    dp[0][1] = 1;

    rep1(i, 1, m)

    {

        rep1(j, 1, tot)

        {

            if (cnt[j] || dp[i - 1][j] == 0) continue;

            rep1(k, 1, 26)

            {

                int y = j;

                while (!a[y][k]) y = f[y];

                dp[i][a[y][k]] = (dp[i][a[y][k]] + dp[i - 1][j]) % MOD;

            }

        }

    }

    int ans1 = 0,ans2=1;

    rep1(i, 1, tot)

        if (!cnt[i])

            ans1 = (ans1 + dp[m][i]) % MOD;

    rep1(i, 1, m)

        ans2 = (ans2 * 26) % MOD;

    printf("%d\n", (ans2 - ans1 + MOD) % MOD);

}

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    in();

    aczidongji();

    do_dp_ando();

    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);

    return 0;

}