LP4052.cpp

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
const int P = 1e4+7, N = 6010, K = 110;
int dp[N][K], tr[N][26], fail[N], idx;
bool mark[N];
int n, m;
vector<int> g[N];

void insert(const string& s) {
    int u = 0;
    for (char c: s) {
        int p = c - 'A';
        if (!tr[u][p]) tr[u][p] = ++idx;
        u = tr[u][p];
    }
    mark[u] = true;
}

void build() {
    queue<int> q;
    for (int i = 0; i < 26; i++) if (tr[0][i]) q.push(tr[0][i]);
    while (q.size()) {
        int fa = q.front(); q.pop();
        for (int i = 0; i < 26; i++) {
            int& u = tr[fa][i];
            if (u) fail[u] = tr[fail[fa]][i], q.push(u);
            else u = tr[fail[fa]][i];
        }
    }
    for (int i = 1; i <= idx; i++) g[fail[i]].pb(i);
}

void dfs(int u, bool m) {
    if (mark[u]) m = true;
    if (m) mark[u] = true;
    for (int to: g[u]) {
        dfs(to, m);
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        insert(s);
    }
    build();

    dfs(0, false);
    for (int i = 0; i <= idx; i++) dp[i][0] = !mark[i];
    for (int k = 1; k <= m; k++) {
        for (int u = 0; u <= idx; u++) {
            if (mark[u]) continue;
            for (int i = 0; i < 26; i++) {
                int to = tr[u][i];
                dp[u][k] = (dp[u][k] + dp[to][k-1]) % P;
            }
        }
    }

    int tot = 1;
    for (int i = 1; i <= m; i++) tot = tot * 26 % P;
    cout << (tot - dp[0][m] + P) % P << '\n';
    return 0;
}