#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define maxn 32
#define sigma 27
#define mod 666013

int n, m;
int d[1<<(maxn/2)][sigma];
char s[maxn];
int f[sigma], conf[maxn];
int rest[sigma][sigma];
int s2[maxn];

int main()
{
    scanf("%s", s);
    n=strlen(s);

    for(int i=0; i<n; ++i)
        ++f[s[i]-'a'];

    int imp=0, k=0, lastimp=sigma-1;

    for(int i=0; i<sigma; ++i)
    {
        if(f[i]%2==1)
        {
            lastimp=i;
            ++imp;
        }
        for(int j=1; j<f[i]; j+=2)
            s2[k++]=i;
    }

    if(imp>1)
    {
        printf("0\n");
        return 0;
    }

    scanf("%d", &m);
    for(int i=1; i<=m; ++i)
    {
        char a, b;
        scanf("\n");
        scanf("%c %c", &a, &b);
        a-='a';
        b-='a';
        rest[a][b]=rest[b][a]=1;
    }

    d[0][lastimp]=1;

    for(int i=0; i<(1<<k); ++i)
    {
        for(int j=0; j<k; ++j)
            conf[j]=((i>>j)&1);

        for(int j=0; j<sigma; ++j)
        {
            if(d[i][j]==0)
                continue;

            for(int l=0; l<k; ++l)
                if(conf[l]==0)
                {
                    if(l==0 && rest[j][s2[l]]==0)
                    {
                    //    printf("*");
                        d[i+(1<<l)][s2[l]]+=d[i][j];
                    }
                    else
                    if((conf[l-1]==1 || s2[l]!=s2[l-1]) && rest[j][s2[l]]==0)
                    {
                    //    printf("!");
                        d[i+(1<<l)][s2[l]]+=d[i][j];
                    }

                    if(d[i+(1<<l)][s2[l]]>=mod)
                        d[i+(1<<l)][s2[l]]-=mod;

                  //  printf("%d %d %d %d %d %d %d\n", i+(1<<l), s2[l], d[i+(1<<l)][s2[l]], d[i][j], j, s2[l], rest[j][s2[l]]);

                }
        }
    //    printf(" %d\n", i);
    }
    int sol=0;

    for(int j=0; j<sigma; ++j)
        sol=(sol+d[(1<<k)-1][j])%mod;

    printf("%d\n", sol);

    return 0;
}