#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#define NMAX 1030
#define MOD 666013
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std;

typedef pair<int, int> pii;

//ifstream fin("sushi.in");
//ofstream fout("sushi.out");

map<string, long long> mp;
vector<pii> lista;
string s;
int fr[26],n,m;
int notpossible[300][300];

int memo(int pos, int last);

int main() {
	int i;
	char x,y;

	cin>>s;
	n=s.size();
	for(i=0;i<n;++i)
		++fr[s[i]-'a'];

	int nrimp=0;
	for(i=0;i<26;++i) {
		if(fr[i]&1) ++nrimp;
	}

	if(nrimp>1) {
		cout<<0;
		return 0;
	}

	cin>>m;
	for(i=0;i<m;++i) {
		cin>>x>>y;
		notpossible[x-'a'][y-'a']=notpossible[y-'a'][x-'a']=1;
	}

	cout<<memo(0,-1);

	return 0;
}

int memo(int pos, int last) {
	if(pos == n/2) {
		for(char i=0;i<26;++i) {
			if(fr[i]==1) {
				if(notpossible[i][last]==0) return 1;
				else return 0;
			}
		}

		return 1;
	}

	string curent;
	for(char i=0;i<26;++i) curent.pb((char)fr[i]);
	curent.pb((char)last);

	if(mp.find(curent)!=mp.end()) return mp[curent];

	long long res=0;
	for(char i=0;i<26;++i) {
		if(notpossible[i][last]==0 && fr[i]>1) {
			if(!(n&1) && pos+1==n/2 && notpossible[i][i]) continue;

			fr[i]-=2;
			res+=memo(pos+1,i);
			if(res>=MOD) res%=MOD;
			fr[i]+=2;
		}
	}

	return mp[curent]=res;
}