自动机上状压dp，把单词是否存在压成二进制位
注意这里面某些单词会包含其他单词，所以某些自动机上有些状态点对应多个二进制位
方案只要再顺着有方案的状态搜一遍即可
var trie,go:array[..,'a'..'z'] of longint;
f,q,v:array[..] of longint;
ans:array[..] of string;
dp:array[..,..,..] of int64;
t,k,i,j,n,m,l:longint;
c:char;
s:string; function calc(n:longint):int64;
var i:longint;
begin
calc:=;
for i:= to n do
calc:=calc*;
end; procedure ac;
var h,r,x,y,j,i:longint;
c:char;
begin
h:=;
r:=;
for c:='a' to 'z' do
if trie[,c]> then
begin
inc(r);
q[r]:=trie[,c];
end; while h<=r do
begin
x:=q[h];
for c:='a' to 'z' do
if trie[x,c]> then
begin
y:=trie[x,c];
inc(r);
q[r]:=y;
j:=f[x];
while (j>) and (trie[j,c]=) do j:=f[j];
f[y]:=trie[j,c];
v[y]:=v[y] or v[trie[j,c]];
end;
inc(h);
end;
end; function dfs(i,p,q:longint):int64;
var c:char;
begin
if i=m then
begin
if q= shl n- then dp[i,p,q]:=
else dp[i,p,q]:=;
end;
if dp[i,p,q]<>- then exit(dp[i,p,q]);
if (q= shl n-) and (m-i<) then exit(calc(m-i));
dp[i,p,q]:=;
for c:='a' to 'z' do
dp[i,p,q]:=dp[i,p,q]+dfs(i+,go[p,c],q or v[go[p,c]]);
exit(dp[i,p,q]);
end; procedure get(i,p,q:longint);
var c:char;
j:longint;
begin
if i=m then
begin
inc(t);
ans[t]:=s;
end
else begin
for c:='a' to 'z' do
if dp[i+,go[p,c],q or v[go[p,c]]]> then
begin
s[i+]:=c;
get(i+,go[p,c],q or v[go[p,c]]);
end;
end;
end; begin
readln(m,n);
for i:= to n do
begin
j:=;
readln(s);
l:=length(s);
for k:= to l do
begin
if trie[j,s[k]]= then
begin
inc(t);
trie[j,s[k]]:=t;
end;
j:=trie[j,s[k]];
end;
v[j]:= shl (i-);
end;
ac;
for i:= to t do
for c:='a' to 'z' do
begin
j:=i;
while (j>) and (trie[j,c]=) do j:=f[j];
go[i,c]:=trie[j,c];
end; fillchar(dp,sizeof(dp),);
writeln(dfs(,,));
if dp[,,]<= then
begin
t:=;
s:='';
for i:= to m do
s:=s+' ';
get(,,);
for i:= to t do
writeln(ans[i]);
end;
end.