#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");

vector<pii> lista;
string s,fin;
int fr[300],n,m,mid;
int notpossible[300][300];
long long dp[1<<16][30], fact[20];

int lgpow(int x, int pow) {
	if (pow==0) return 1;
	if(pow&1) return (1LL*x*lgpow(x,pow-1))%MOD;
	return (1LL*lgpow(x,pow>>1)*lgpow(x,pow>>1))%MOD;
}
long long memo(int mask, 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) {
			mid=i;
			++nrimp;
		}
		fr[i]/=2;
	}

	for(i=0;i<26;++i) {
		int x=fr[i];
		while(x) {
			fin.pb(i);
			--x;
		}
	}
	n=fin.size();

	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;
	}

	for(i=0;i<n;++i) dp[1<<i][i]=1;
	long long res=0;
	for(i=0;i<n;++i) {
		if((mid==0 && notpossible[fin[i]][fin[i]]==0) || (mid && notpossible[mid][fin[i]]==0))
			res+=memo((1<<n)-1,i);
	}

	fact[0]=1;
	for(i=1;i<=15;++i) fact[i]=i*fact[i-1];
	for(i=0;i<26;++i)
		if(fr[i])
			res=(res*lgpow(fact[fr[i]], MOD-2))%MOD;
			//res/=fact[fr[i]];

	cout<<res%MOD;

	return 0;
}

long long memo(int mask, int last) {
	long long &ret=dp[mask][last];

	if(ret != 0) return ret;

	for(char i=0;i<n;++i) {
		if((mask&(1<<i)) && notpossible[fin[last]][fin[i]]==0 && i!=last)
			ret+=memo(mask^(1<<last),i);
			//if(ret>=MOD) ret-=MOD;
	}

	return ret;
}