RT

code:

#include <bits/stdc++.h>
#define for1(i,a,b) for( int (i)=(a); (i)<=(b); ++(i))
#define for2(i,a,b) for( int (i)=(a); (i)>=(b); --(i))
#define pedl cout<<"\n";
#define fi first
#define se second
#define p_f push_front
#define p_b push_back
#define o_f pop_front
#define o_b pop_back
#define ls p<<1
#define rs p<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
using namespace std;
mt19937 rnd(time(0));//uint
mt19937_64 rnd_64(time(0));//ull
template<typename T> void cmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void cmax(T& x, T y) {if(x < y) x = y;}
template<typename T> T qpow(T x,auto y) {T res=x; y--; for(;y;y>>=1,x=x*x) if(y&1) res=res*x; return res;}
void madd(auto& x, auto y, auto Mod) {x=(x+y+1ull*Mod)%Mod;}
typedef double db;
typedef long double ld;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;
const double eps = 1e-7;
const int base = 13331;
const int mod = 10007;
const int N = 1e2+5;
const int M = 1e2+5;
const int IINF = 0x3f3f3f3f;
const long long LINF = 1e18;
int n,len,alpha;
int a[N];
string s;
struct MAT{
	int row,col;
	ld t[105][105];
}G; 
MAT operator *(const MAT &A,const MAT &B){
	MAT ANS;
	assert(A.col==B.row);//断言，若为false报错 
	ANS.row=A.row,ANS.col=B.col;
	for1(i,0,ANS.row)
		for1(j,0,ANS.col)
			ANS.t[i][j]=(ld)0.0; 
	for1(i,0,ANS.row)
		for1(j,0,ANS.col)
			for1(k,0,A.col)
				ANS.t[i][j]+=(ld)1.0*A.t[i][k]*1.0*B.t[k][j];
	return ANS;
}
int tot_tr;
struct node{
	int fail;
	int son[30];
	bool end;
	node(){
		fail=end=0;
		memset(son,0,sizeof son);
	}
}tr[N];
void insert(string s){
	int u=0,c;
	for1(i,0,s.size()-1){
		c=s[i]-'a';
		if(!tr[u].son[c]) tr[u].son[c]=++tot_tr;
		u=tr[u].son[c];
	}
	tr[u].end=1;
}
void get_fail(){
	queue<int> q;
	q.push(0); tr[0].fail=0;
	while(!q.empty()){
		int u=q.front(),FL=tr[u].fail; q.pop();
		for1(i,0,alpha-1){
			int v=tr[u].son[i];
			if(v){
				tr[v].fail=u?tr[FL].son[i]:u;
				tr[v].end|=tr[tr[v].fail].end;
				q.push(v);
			}else tr[u].son[i]=u?tr[FL].son[i]:u;
		}
	}
}
void solve(){
	cin>>n>>len>>alpha;
	for1(i,1,n){
		cin>>s;
		insert(s);
	}
	get_fail();
	G.col=G.row=tot_tr+1;
	for1(i,0,G.row)
		for1(j,0,G.col)
			G.t[i][j]=(ld)0.0;
	for1(u,0,tot_tr){
		for1(c,0,alpha-1){
			if(tr[tr[u].son[c]].end){
				G.t[u][0]+=(ld)1.0;
				G.t[u][tot_tr+1]+=(ld)1.0;
			}else G.t[u][tr[u].son[c]]+=(ld)1.0;
		}
	}
	
	for1(i,0,G.row)
		for1(j,0,G.col)
			G.t[i][j]/=(ld)alpha;
	G.t[G.row][G.col]=(ld)1.0;
	G=qpow(G,len);
	cout<<G.t[0][tot_tr+1]; 
	return ;
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	time_t start=clock();
//	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T=1;
//cin>>T;
while(T--){
	solve();
}
	time_t duration=clock()-start;
	cerr<<"\ntime="<<duration;
    return 0;
}