题意：

给出m个模式串，要求构造一长度为n的文本串，至少包括k种模式串，求有多少种可能的模式串。

k<=10  然后可以想到状压

一个文本串，k种模式串，很容易想到AC自动机。

把所有的模式串放入AC自动机上面，然后跑状压DP

跟AC自动机有关的DP一般都要用的AC自动机上的节点。

dp状态定义为dp[ i ][ j ][status]走到长度为i 时，在AC自动机上 j 这个节点

状态为 status 的方案数。

然后统计答案即可。

由于状态只与上一步有关，所以我滚动了一维，多开一维并不会MLE，也可以写。

#include
#include

#define pi acos(-1.0)
#define eps 1e-9
#define fi first
#define se second
#define rtl rt<<1
#define rtr rt<<1|1
#define bug printf("******\n")
#define mem(a, b) memset(a,b,sizeof(a))
#define name2str(x) #x
#define fuck(x) cout<<#x" = "<<x<<endl
#define sf(n) scanf("%d", &n)
#define sff(a, b) scanf("%d %d", &a, &b)
#define sfff(a, b, c) scanf("%d %d %d", &a, &b, &c)
#define sffff(a, b, c, d) scanf("%d %d %d %d", &a, &b, &c, &d)
#define pf printf
#define FIN freopen("../date.txt","r",stdin)
#define gcd(a, b) __gcd(a,b)
#define lowbit(x) x&-x
#define IO iOS::sync_with_stdio(false)

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1e6 + ;
const int maxm = 8e6 + ;
const int INF = 0x3f3f3f3f;
const int mod = ;

char buf[];
int n, m, k;
LL dp[][][];

int cal(int num) {
int ans = ;
while (num) {
if (num % ) ans++;
num /= ;
}
return ans;
}

struct Aho_Corasick {
int next[][], fail[], End[];
int root, cnt;

 int newnode() {  
     for (int i = ; i < ; i++) next\[cnt\]\[i\] = -;  
     End\[cnt++\] = ;  
     return cnt - ;  
 }

 void init() {  
     cnt = ;  
     root = newnode();  
 }

 void insert(char buf\[\], int id) {  
     int len = strlen(buf);  
     int now = root;  
     for (int i = ; i < len; i++) {  
         if (next\[now\]\[buf\[i\] - 'a'\] == -) next\[now\]\[buf\[i\] - 'a'\] = newnode();  
         now = next\[now\]\[buf\[i\] - 'a'\];  
     }  
     End\[now\] |= ( << id);  
 }

 void build() {  
     queue<int> Q;  
     fail\[root\] = root;  
     for (int i = ; i < ; i++)  
         if (next\[root\]\[i\] == -) next\[root\]\[i\] = root;  
         else {  
             fail\[next\[root\]\[i\]\] = root;  
             Q.push(next\[root\]\[i\]);  
         }  
     while (!Q.empty()) {  
         int now = Q.front();  
         Q.pop();  
         End\[now\] |=End\[fail\[now\]\];  
         for (int i = ; i < ; i++)  
             if (next\[now\]\[i\] == -) next\[now\]\[i\] = next\[fail\[now\]\]\[i\];  
             else {  
                 fail\[next\[now\]\[i\]\] = next\[fail\[now\]\]\[i\];  
                 Q.push(next\[now\]\[i\]);  
             }  
     }  
 }

 void debug() {  
     for (int i = ; i < cnt; i++) {  
         printf("id = %3d,fail = %3d,end = %3d,chi = \[", i, fail\[i\], End\[i\]);  
         for (int j = ; j < ; j++) printf("%2d", next\[i\]\[j\]);  
         printf("\]\\n");  
     }  
 }  

} ac;

int main() {
// FIN;
while (~sfff(n, m, k)) {
if (n == && m == && k == ) break;
ac.init();
for (int i = ; i < m; ++i) {
scanf("%s", buf);
ac.insert(buf, i);
}
ac.build();
for (int i = ; i <; i++)
for (int j = ; j < ac.cnt; j++)
for (int p = ; p < ( << m); p++)
dp[i][j][p] = ;
int now = ;
dp[now][][] = ;
for (int i = ; i <= n; ++i) {
now = now ^ ;
for (int j = ; j < ac.cnt; j++)
for (int p = ; p < ( << m); p++)
dp[now][j][p] = ;
for (int j = ; j < ac.cnt; ++j) {
for (int status = ; status < ( << m); ++status) {
if (dp[now ^ ][j][status]) {
for (int l = ; l < ; ++l) {
int st = (status | ac.End[ac.next[j][l]]);
dp[now][ac.next[j][l]][st] = (dp[now][ac.next[j][l]][st] + dp[now ^ ][j][status]) % mod;
}
}
}
}
}
LL ans = ;
for (int status = ; status < ( << m); ++status) {
if (cal(status) < k) continue;
for (int i = ; i < ac.cnt; ++i)
ans = (ans + dp[now][i][status]) % mod;
}
printf("%lld\n", ans);
}
return ;
}