#include <iostream>
#include <string.h>
using namespace std;

#define MAXN 100
#define FAIL 0

int trans[MAXN][26];
bool terminal[MAXN];
int S[MAXN];
int vex;

const int mod = 10007;

void init() {
    fill(trans[1], trans[vex + 1], FAIL);
    fill(terminal, terminal + vex + 1, false);
    vex = 1;
}

void trie(char *p) {
    int cur = 1, ch;    
    while (*p != '\0') {
        ch = *(p++) - 'A';
        if (trans[cur][ch] == FAIL) trans[cur][ch] = ++vex;
        cur = trans[cur][ch];
    }
    terminal[cur] = true;
}

void build_ac() {
    int Q[MAXN], f, r;
    f = r = 0;
    S[1] = FAIL;
    Q[r++] = 1;
    
    while (f < r) {
        int cur = Q[f++];        
        for (int i = 0; i < 26; i++) {
            int next = trans[cur][i];            
            if (next != FAIL) {
                if (cur == 1) S[next] = cur;
                else S[next] = trans[S[cur]][i];                
                if (terminal[S[next]]) terminal[next] = true;
                
                Q[r++] = next;
            } else {
                if (cur == 1) trans[cur][i] = 1;
                else trans[cur][i] = trans[S[cur]][i];
            }
        }
    }
}

typedef int MATR[MAXN][MAXN];
MATR omat;
int n;

int conv[MAXN];
int getid(int cur) {
    if (conv[cur] == -1) conv[cur] = n++;
    return conv[cur];
}


void calmat() {
    int i, j, ch, cur, next;
    memset(omat, 0, sizeof(omat));
    
    fill(conv, conv + vex + 1, -1);
    n = 0;
    for (cur = 1; cur <= vex; cur++) {
        if (terminal[cur]) continue;
        i = getid(cur);
        
        for (ch = 0; ch < 26; ch++) {                
            next = trans[cur][ch];
            if (terminal[next]) continue;            
            j = getid(next);            
            if (next != FAIL) omat[i][j]++;        
        }
    }    
}




void matmul(MATR a, MATR b, MATR c, int n) {
    int i, j, k;
    
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            c[i][j] = 0;
            for (k = 0; k < n; k++)
                c[i][j] += a[i][k] * b[k][j];
            c[i][j] %= mod;
        }                    
    }
}

void matpow(MATR a, MATR c, int m) { //a^m
    if (m == 1) {
        memcpy(c, omat,sizeof(MATR));
        return;
    }
    
    matpow(c, a, m/2);
    matmul(a, a, c, n);
    
    if (m & 1) {
        matmul(c, omat, a, n);
        memcpy(c, a, sizeof(MATR));
    }    
}

int modpow(int a, int m) {    
    if (m == 1) return a % mod;
    
    int tmp = modpow(a, m/2);
    tmp = tmp * tmp % mod;
    
    if (m & 1) tmp = tmp * a % mod;
    return tmp;
}

int main() {
#ifdef _DEBUG
    freopen("in.txt", "r", stdin);
#endif
    
    int m, len, i;
    char buf[100];
    
    while (scanf("%d%d", &m, &len) != EOF) {
        init();
        for (i = 0; i < m; i++) {
            scanf("%s", buf);
            trie(buf);
        }
        build_ac();
        calmat();
        MATR tmp, res;
        matpow(tmp, res, len);

        int bad = 0;
        for (i = 0; i < n; i++) bad -= res[0][i];
        
        bad = (bad % mod + mod) % mod;        
        int total = modpow(26, len);
        
        printf("%d\n", (total + bad) % mod);
    }
    
    return 0;
}


版本2

#include <stdio.h>
#include <string.h>
#define R 27
#define N 100
#define M 10007
typedef int LL;

int tree[N][R], flag[N], fail[N], state;

void init(){
    memset(tree, -1, sizeof(tree));
    memset(flag, 0, sizeof(flag));
    memset(fail, -1, sizeof(fail));
    flag[0] = 0;
    state = 1;
}
void insert(char ch[]) {
    int p = 0, i = 0, t;
    while(ch[i]) {
        t = ch[i] - 'A' + 1;
        if(tree[p][t] < 0) tree[p][t] = state++;
        p = tree[p][t], i ++;
    }
    flag[p] = 1;
}

int que[N];

void get_fail() {
    int close = -1, open = 0, next;
    que[0] = 0;
    fail[0] = -1;
    while(close < open) {
        int p = que[++close];
        for(int i = 0; i < R; i ++) {
   next = tree[p][i];
            if(next == -1){
                if(p == 0)  tree[p][i] = 0;
                else        tree[p][i] = tree[fail[p]][i];
            } else {
                if(p == 0)  fail[next] = 0;
                else        fail[next] = tree[fail[p]][i];
                if(flag[fail[next]]) flag[next] = true;
                que[++open] = next;
            }
        }
    }
}
int n, L;
LL f[N][N], sum = 0;

void mod_multi(LL a[N][N], LL b[N][N], int r){
    int i, j, k;
    LL c[N][N] = {};
    for (k = 0; k < r; k++)
        for (i = 0; i < r; i++)
            if(a[i][k])
            for (j = 0; j < r; j++){
                c[i][j] += a[i][k] * b[k][j];
                c[i][j] %= M;
            }
    for (i = 0; i < r; i++)
        for (j = 0; j < r; j++)
            a[i][j] = c[i][j];
}

void mod_exp(LL a[N][N], LL n, int r){
    int i, j, k;
    LL ans[N][N] = {};
    for (i = 0; i < r; i++)ans[i][i] = 1;
    for (; n; n >>= 1){
        if (n & 1)
            mod_multi(ans, a, r);
        mod_multi(a, a, r);
    }
    for (i = 0; i < r; i++)
        for (j = 0; j < r; j++)
            a[i][j] = ans[i][j];
}

LL fast(LL sum, int L) {
    LL temp = 1ll;
    for(;L;L >>= 1) {
        if(L&1) {
            temp *= sum;
            temp %= M;
        }
        sum *= sum;
        sum %= M;
    }
    return temp;
}

int main() {
    while(scanf("%d %d\n", &n ,&L) != EOF) {
        char str[7];
        init();
        for(int i = 0; i < n; i ++) {
            gets(str);
            insert(str);
        }
        get_fail();
        int map[N], cnt = 0, next;
        memset(map,-1,sizeof(map));
        memset(f, 0, sizeof(f));
        for(int i = 0; i < state; i ++) {
            if(flag[i]) continue;
            for(int j = 1; j < R; j ++) {
    next = tree[i][j];
                if(flag[next]) 
     continue;
                if(map[i] == -1) map[i] = cnt ++;
                if(map[next] == -1) map[next]  = cnt ++;
                f[map[i]][map[next]] ++; 
            }
        }
        mod_exp(f, L, cnt);
        LL ans = 0;
        for(int i = 0; i < cnt; i ++) ans += f[0][i];
  ans %= M;
        sum = fast(26, L);
        printf("%d\n", (sum + M - ans) % M);
    }
}