#include <stdio.h>#include <string.h>#include <stdlib.h>#define MIN 210#define MAX 1100#define MOD 1000000007struct node {int cnt;node *next[26];}*root;int n,dp[MAX];char dir[MAX][MIN],str[MAX];node *CreateNode() {node *p;p = (node *) malloc (sizeof(node));p->cnt = 0;for (int i = 0; i < 26; ++i)p->next[i] = NULL;return p;}void Release(node *p) {for (int i = 0; i < 26; ++i)if (p->next[i] != NULL) Release(p->next[i]);free(p);}void Insert(char *str) {int i = 0,k;node *p = root;while (str[i]) {k = str[i++] - 'A';if (p->next[k] == NULL)p->next[k] = CreateNode();p = p->next[k];}p->cnt++;}void Query(char *str){int i = 0,k;node *p = root;while (str[i]) {k = str[i] - 'A';if (p->next[k] == NULL)break;p = p->next[k];dp[i] = p->cnt;i++;}}void UpdateDP(char *str,int index) {int i = 0,k,j;long long tp[MAX],tot = 0;node *p = root;memset(tp,0,sizeof(tp));while (str[i]) {k = str[i] - 'A';if (p->next[k] == NULL)break;p = p->next[k];if (p->cnt)tp[i+index] = ((long long)(tot * p->cnt)) % MOD;tot = (dp[index+i] + tot) % MOD;i++;}for (j = 0; j <= i + index; ++j)dp[j] = (tp[j] + dp[j]) % MOD;}int main(){int i,j,k,t;scanf("%d",&t);while (t--) {scanf("%s",str);scanf("%d",&n);root = CreateNode();for (i = 0; i < n; ++i){scanf("%s",dir[i]);if (strlen(dir[i]) == 1)continue;Insert(dir[i]);}memset(dp,0,sizeof(dp));Query(str);for (i = 1; str[i]; ++i)UpdateDP(str+i,i);printf("%dn",dp[i-1]%MOD);Release(root);}}
