Bob最近迷上了一个博彩游戏……

这个游戏的规则是这样的：
每花一块钱可以得到一个随机数R，花上N块钱就可以得到一个随机序列；
有M个序列，如果某个序列是产生的随机序列的子串，那么就中奖了，否则不中。
Bob会告诉你这M个序列，和身上有的钱的总数N，当然还有R的范围。
请你告诉Bob中奖的概率有多少？

第一行三个用空格隔开的数N、M和R的范围R。
其中1<=R<=9，0<N<=60，0<M<=20000。
下面M行每行一个字符串（长度小于等于20），字符串的每一位范围在1-r之间
保证必要运算都在64位整型范围内。

一行一个实数，表示中奖的概率（保留小数点后5位小数）。

输入

5 1 3 
1

输出

0.86831

数据分布：
第1个点~第10个点，每个点5分；
第11个点~第15个点，每个点10分。

对于样例的解释：
随机序列一共有3^5=243个，其中包含"1"的个数为211个，则概率为211/243=0.86831Bob HAN

/*

    AC自动机+DP

    f[i][j]表示将字符串扩展到i，在自动机上匹配到j的概率。

    因为合法概率较难统计，所以最后答案为 1-不合法的概率。

    要滚动一下数组。

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#include<queue>

#define N 400010

#define eps 0.000000001

using namespace std;

int a[N][],danger[N],point[N],n,m,r,size=;

double f[][N];char s[N];

queue<int> q;

void insert(){

    int len=strlen(s),now=;

    for(int i=;i<len;i++){

        int t=s[i]-'';

        if(!a[now][t]) a[now][t]=++size;

        now=a[now][t];

    }

    danger[now]=;

}

void build(){

    q.push();point[]=;

    while(!q.empty()){

        int now=q.front();q.pop();

        for(int i=;i<=r;i++){

            if(!a[now][i]){

                a[now][i]=a[point[now]][i];

                continue;

            }

            int k=point[now];

            while(!a[k][i]) k=point[k];

            point[a[now][i]]=a[k][i];

            danger[a[now][i]]|=danger[point[a[now][i]]];

            q.push(a[now][i]);

        }

    }

}

void dp(){

    f[][]=;

    for(int i=;i<=n;i++){

        for(int j=;j<=size;j++){

            if(danger[j]||f[i+&][j]<eps) continue;

            for(int t=;t<=r;t++){

                int k=j;

                while(!a[k][t]) k=point[k];

                f[i&][a[k][t]]+=f[i+&][j]/(double)r;

            }

        }

        for(int j=;j<=size;j++)

            f[i+&][j]=;

    }

}

int main(){

    scanf("%d%d%d",&n,&m,&r);

    for(int i=;i<=r;i++) a[][i]=;

    for(int i=;i<=m;i++){

        scanf("%s",s);

        insert();

    }

    build();dp();

    double ans=;

    for(int i=;i<=size;i++)

        if(!danger[i]) ans+=f[n&][i];

    printf("%.5f",1.0-ans);

    return ;

}