/*
*/

//#pragma comment(linker, "/STACK:16777216")
#define _CRT_SECURE_NO_WARNINGS

#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd

#define eps 1e-9
#define M_PI 3.141592653589793
#define bs 666013
#define bsize 256

using namespace std;

const int INF = 1e9;
const int N = 100031;

string st;
int n;
int bad[200][200];
int cnt[200];

set<long long > done;
map<long long, int> memo;

int dfs(int l, int r, int l_let)
{
	long long v = 0;
	v = v * 73 + l;
	v = v * 73 + r;
	v = v * 73 + l_let;

	for (int i = 0; i < 26; i++)
	{
		v = v * 73 + cnt[i];
//		v.push_back(cnt[i]);
	}

	if (done.find(v) != done.end())
		return memo[v];
	done.insert(v);
	if (l>r)
	{
		memo[v] = 1;
	}
	else
	{
		int res = 0;
		int need = 2;
		if (l == r)
			need = 1;

		for (int i = 0; i < 26; i++)
		{
			if (cnt[i] < need)
				continue;
			if (l + 1 == r&&bad[i][i] == 1)
				continue;
			if (l_let >= 0 && bad[l_let][i]>0)
				continue;
			//	cout << l << " " << r << " " << l_let << " " << i << endl;

			cnt[i] -= need;
			res += dfs(l + 1, r - 1, i);
			cnt[i] += need;
			if (res >= bs)
				res -= bs;
		}
		memo[v] = res;
	}
	//if (memo[v] > 0)
	//cout << l << " " << r << " " << l_let << " " << memo[v] << endl;
	return memo[v];
}

int main(){
	//freopen("fabro.in","r",stdin);
	//freopen("fabro.out","w",stdout);
	//freopen("F:/in.txt", "r", stdin);
	//freopen("F:/output.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
	//cin.tie(0);

	cin >> st;
	sort(st.begin(), st.end());
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		string a, b;
		cin >> a >> b;
		bad[a[0] - 'a'][b[0] - 'a'] = 1;
		bad[b[0] - 'a'][a[0] - 'a'] = 1;
	}

	for (int i = 0; i < st.size(); i++)
	{
		cnt[st[i] - 'a']++;
	}
	int ods = 0;
	for (int i = 0; i < 26; i++)
	{
		if (cnt[i] % 2)
			++ods;
	}

	n = st.size();

	if (ods>1)
		cout << 0 << endl;
	else
		cout << dfs(0, n - 1, -1) << endl;

	cin.get(); cin.get();
	return 0;
}