#include <bits/stdc++.h>

using namespace std;

char s[50];
int g[50][50];
int f[50];
int x[50];

const int kMod = 666013;

int D[18][1 << 18];

int fact[50];

int fastPow(int A, int B) {
    if (B == 0)
        return 1;
    int res = fastPow(A, B / 2);
    res = (long long) res * res % kMod;
    if (B % 2)
        res = (long long) res * A % kMod;
    return res;
}

int main() {
    int m;
    cin >> (s + 1);
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        char a, b;
        cin >> a >> b;
        g[a - 'a'][b - 'a'] = 1;
        g[b - 'a'][a - 'a'] = 1;
    }
    int n = strlen(s + 1);
    if (n == 1) {
        assert(0);
        return 0;
    }
    for (int i = 1; i <= n; ++i)
        ++f[s[i] - 'a'];
    int odd = 0;
    for (int i = 0; i < 26; ++i)
        if (f[i] % 2)
            ++odd;
    if (odd > 1) {
        printf("0");
        return 0;
    }
    int new_n = 0;
    for (int i = 0; i < 26; ++i)
        for (int j = 1; j <= f[i] / 2; ++j)
            x[new_n++] = i;
    n = new_n;
    for (int mask = 1; mask < (1 << n); ++mask)
        for (int last = 0; last < n; ++last)
            if (mask & (1 << last)) {
                for (int prev = 0; prev < n; ++prev)
                    if (prev != last)
                        if (g[x[prev]][x[last]] == 0) {
                            D[last][mask] += D[prev][mask ^ (1 << last)];
                            if (D[last][mask] >= kMod)
                                D[last][mask] -= kMod;
                        }
                    if ((mask & (mask - 1)) == 0)
                        D[last][mask] = 1;
            }
    int last = -1;
    for (int i = 0; i < 26; ++i)
        if (f[i] % 2)
            last = i;
    int muie = 0;
    for (int i = 0; i < n; ++i)
        if (last == -1 || g[i][last] == 0)
            if (odd || g[i][i] == 0)
                muie = (muie + D[i][(1 << n) - 1]) % kMod;
    fact[0] = 1;
    for (int i = 1; i < 50; ++i)
        fact[i] = (long long) i * fact[i - 1] % kMod;
    for (int i = 0; i < 26; ++i)
        if (f[i] / 2)
            muie = (long long) muie * fastPow(fact[f[i] / 2], kMod - 2) % kMod;
    printf("%d", muie);
    return 0;
}