#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=-1;
int notpossible[300][300];
long long dp[1<<17][30], fact[20];

long long lgpow(long long a, long long b) {
    long long x=1,y=a;
    y%=MOD;
    while(b > 0) {
        if(b%2 == 1) {
            x=(x*y);
            if(x>MOD) x%=MOD;
        }
        y = (y*y);
        if(y>MOD) y%=MOD;
        b >>= 1;
    }
    return x;
}
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;
	}

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

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

	cout<<res;

	return 0;
}

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

	if(ret != -1) return ret;

	ret=0;
	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;
}