/* This Code is Submitted by wywcgs for Problem 2471 on 2007-04-16 at 11:09:33 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long llong;

const int N = 52;
const int MAGIC = 1000000;

void matPow(llong[][N], int);
void mul(llong[][N], llong[][N]);

int main()
{
	llong m[N][N];
	int T, L;
	
	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		memset(m, 0, sizeof(m));
		for(int i = 0; i < N/2; i++) m[i][i] = m[i][i+N/2] = 1;
		int n; scanf("%d", &n);
		for(int i = 0; i < n; i++) {
			char d[3]; scanf("%s", d);
			m[d[0]-'a'+N/2][d[1]-'a'+N/2] = 1;
		}
		scanf("%d", &L);
		matPow(m, L);
		llong res = 0;
		for(int i = 0; i < N/2; i++)
			for(int j = N/2; j < N; j++)
				res = (res+m[i][j])%MAGIC;
		printf("%lld\n", (res+MAGIC-26)%MAGIC);
	}
	
	return 0;
}

void matPow(llong m[][N], int n)
{
	llong u[N][N];
	memcpy(u, m, sizeof(u));
	int bit = 31;
	for(; (n&(1<<bit)) == 0; bit--);
	for(bit--; bit >= 0; bit--) {
		mul(m, m);
		if(n&(1<<bit)) mul(m, u);
	}
}
void mul(llong a[][N], llong b[][N])
{
	llong c[N][N]; memset(c, 0, sizeof(c));
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			for(int k = 0; k < N; k++)
				c[i][j] = (c[i][j]+a[i][k]*b[k][j])%MAGIC;
	memcpy(a, c, sizeof(c));
}