#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define fi first
#define se second
#define _UN using namespace
using namespace std;
const int PR[] {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173};
constexpr int MAXN=5e5+10;
int n; long tot;
struct Mat{
    long A[50][50]; int m;
    Mat mul(const Mat& o,int mod)const{
        assert(o.m==m);
        Mat r {}; r.m=m;
        RNG(k,0,m){
            RNG(i,0,m){
                RNG(j,0,m) r.A[i][j]=(r.A[i][j]+A[i][k]*o.A[k][j])%mod;
            }
        }
        return r;
    }
    static Mat I(int m){
        Mat r{}; r.m=m;
        RNG(i,0,m) r.A[i][i]=1;
        return r;
    }
};
struct AC{
    int to[50][26],fail[50],len[50]; int id[50]; int nnd;
    void init(){ memset(this,0,sizeof(*this)); }
    void ins(const char* s,int k){
        int u=0;
        for(; *s; s++){
            int c=*s-'A';
            if(!to[u][c]) to[u][c]=++nnd,len[nnd]=len[u]+1;
            u=to[u][c];
        }
        id[u]=k;
    }
    pair<Mat,function<Mat(int)>> build(){
        queue<int> q;
        RNG(c,0,25){
            if(to[0][c]) q.push(to[0][c]);
        }
        while(q.size()){
            int u=q.front(); q.pop();
            RNG(c,0,25){
                if(to[u][c]) fail[to[u][c]]=to[fail[u]][c],q.push(to[u][c]);
                else to[u][c]=to[fail[u]][c];
            }
        }
        Mat A; A.m=nnd;
        RNG(i,0,nnd){
            RNG(c,0,25) A.A[i][to[i][c]]++;
        }
        auto f=[this](int l){
            Mat B {}; B.m=nnd;
            RNG(i,0,nnd){
                if(id[i]) B.A[i][i]=PR[id[i]]*(len[i]+l);
                else B.A[i][i]=1;
            }
            return B;
        };
        return {A,f};
    }
} ac;
Mat qpow(Mat x,long p,int mod){
    Mat ret=Mat::I(x.m);
    for(; p; p>>=1,x=x.mul(x,mod)){
        if(p&1) ret=ret.mul(x,mod);
    }
    return ret;
}
long solve(int mod,Mat B,function<Mat(int)>& f){
    auto A=Mat::I(ac.nnd);
    RNG(i,1,mod) A=A.mul(B,mod),A=A.mul(f(i),mod);
    A=qpow(A,tot/mod,mod);
    RNG(i,1,int(tot%mod)) A=A.mul(B,mod),A=A.mul(f(i),mod);
    long ret=0;
    RNG(i,0,ac.nnd) ret=ret+A.A[0][i];
    return ret;
}
void case_main(){
    cin>>tot;
    ac.init();
    RNG(i,1,n){ char S[41]; cin>>S; ac.ins(S,i); }
    auto [A,f]=ac.build();
    auto a=solve(179,A,f);
    auto b=solve(173,A,f);
    auto c=solve(163,A,f);
    auto ans=(a*1945731+b*1429673+c*1672218)%5047621;
    cout<<ans<<"\n";
}
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
//  freopen("out","w",stdout);
//  freopen("/dev/null","w",stderr);
#else
//  freopen("desert.in","r",stdin);
//  freopen("desert.out","w",stdout);
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    while(n=0,cin>>n,n) case_main();
}