暴力对每个串建后缀自动机，然后暴力枚举每个自动机的子串。可以拿到部分分。
然鹅我们可以把每个后缀自动机连起来。
我们知道，后缀自动机是用最少的点（空间）表示出一个串的所有子串。
那么我们为啥不在后缀自动机上直接跑dp呢？于是我们把它们连起来。
复制一段ppt：
可以怎么拼呢？
我们考虑如何判断一个字符串是否是可能的输出文件
显然我们可以贪心地匹配，每次拿起一个输入串，一直匹配到不能再加字符了才放下，这样一定是正确的
于是我们可以告诉自动机如果失配了要往哪走
比如有一个节点没有C的转移边，那么就要向之后第一个包含字符C的字符串的后缀自动机接受字符串C的节点连一条C的转移边
当然如果这样的字符串不存在就不需要连边
把自动机建起来后
对于$k=1$的情况，直接dfs搞定
但是面对大数据，dfs显然是会TLE的鸭
但是仔细一看
对于 100% 的数据，保证输入文件大小不超过 1MB ，保证输出文件大小不超过 200MB 。
显然大数据的$k=0$，否则输出文件就超过限制了。
于是我们在新图上跑个$dp$就行辣
#include<cstdio>
#include<iostream>
using namespace std;
#define N 10000005
const int mod=1e9+;
char fr1[]={'A','C','G','T'},s[N];
int n,k,fr2[],now[N],st[N],tp,ans;
int nxt[N][],fa[N],len[N],ed,last,rt[N],f[N];
void dfs(int tp,int x){//k=1时用dfs找每个子串并输出
st[tp]=x; puts(s+); ++ans;
for(;now[tp]<;++now[tp]){
if(nxt[x][now[tp]]){
s[tp+]=fr1[now[tp]];
now[tp+]=;
dfs(tp+,nxt[x][now[tp]]);
s[tp+]=;
}
}
}
void dp(int tp,int x){//k=0时直接dp，应对大数据
if(f[x]>) return;
f[x]=;
for(;now[tp]<;++now[tp]){
if(nxt[x][now[tp]]){
dp(tp+,nxt[x][now[tp]]);
now[tp+]=;
f[x]=(f[x]+f[nxt[x][now[tp]]])%mod;
}
}
}
struct sam{//裸裸的后缀自动机
void init(int x){
last=rt[x]=++ed; char c=getchar();
while(c<'A'||'T'<c) c=getchar();
while(c!='\n') add(fr2[c],x),c=getchar();
}
void add(int c,int x){
int q,p=last; len[last=++ed]=len[p]+;
for(;p&&!nxt[p][c];p=fa[p]) nxt[p][c]=ed;
if(!p) fa[ed]=rt[x];
else{
q=nxt[p][c];
if(len[q]==len[p]+) fa[ed]=q;
else{
len[++ed]=len[p]+;
for(int k=;k<;++k) nxt[ed][k]=nxt[q][k];
fa[ed]=fa[q]; fa[q]=fa[ed-]=ed;
for(;nxt[p][c]==q;p=fa[p]) nxt[p][c]=ed;
}
}
}
}S; int main(){
freopen("copy.in","r",stdin);
freopen("copy.out","w",stdout);
fr2['A']=;fr2['C']=;fr2['G']=;fr2['T']=;
scanf("%d",&n);
for(int i=;i<=n;++i) S.init(i);
for(int i=n-;i;--i)
for(int j=rt[i];j!=rt[i+];++j)
for(int c=;c<;++c)
if(!nxt[j][c]) nxt[j][c]=nxt[rt[i+]][c];//贪心连边
scanf("%d",&k);
if(k) dfs(,rt[]),printf("%d",ans);
else dp(,rt[]),printf("%d",f[rt[]]);
return ;
}