#include<cstdio>

#include<cstring>

#include<vector>

using namespace std;

const int N=10010,M=500010,P=1000000;

int n,i,j,k,x,t,f[2][M],ans,len[N],tot,son[N][26],id[N],fail[N],q[N];char s[M];vector<int>v[N];

inline void up(int&x,int y){x+=y;if(x>=P)x-=P;}

void ins(int p){

  scanf("%s",s);

  for(int l=len[p]=strlen(s),x=0,i=0,w;i<l;i++){

    if(!son[x][w=s[i]-'a'])son[x][w]=++tot;x=son[x][w];

    if(i==l-1)id[x]=p;

  }

}

void make(){

  int h=1,t=0,i,j,x;fail[0]=-1;

  for(i=0;i<26;i++)if(son[0][i])q[++t]=son[0][i];

  while(h<=t)for(x=q[h++],i=0;i<26;i++)if(son[x][i]){

    fail[q[++t]=son[x][i]]=son[fail[x]][i];

    id[son[x][i]]+=id[son[fail[x]][i]];

  }else son[x][i]=son[fail[x]][i];

}

int main(){

  scanf("%d",&n);

  for(i=1;i<=n;i++)ins(i);

  make();

  scanf("%s",s);

  for(i=0;s[i];i++)if(id[x=son[x][s[i]-'a']])v[id[x]].push_back(i);

  for(i=0,x=1;i<v[1].size();i++)f[1][i]=1;

  for(i=2;i<=n;i++)for(x^=1,j=k=t=0;j<v[i].size();j++){

    while(k<v[i-1].size()&&v[i-1][k]+len[i]<=v[i][j])up(t,f[x^1][k++]);

    f[x][j]=t;

  }

  for(i=0;i<v[n].size();i++)up(ans,f[x][i]);

  return printf("%d",ans),0;

}