#include <iostream>
#include <string.h>
using namespace std;

string s;
const long long MOD=666013;
long long m, n,REST[30][30],impare,F[30],fact[30];
char x, y,c;
long long DP[1<<15][30],SOLVED[1<<15][30];
void factorial()
{
    fact[0]=1;
    for(int i=1;i<=n;i++)
        fact[i]=fact[i-1]*i;
}

void solve(int conf)
{
    for(long long i=0;i<n;i++)
    {
        if(conf & (1<<i))
        {
            char x=s[i];
            if(SOLVED[conf][i])
                continue;
            long long prev_conf=conf - (1<<i);
            for(long long j=0;j<n;j++) {
                char y=s[j];
                if((prev_conf & (1<<j)) && !REST[x-'a'][y-'a']){
                    solve(prev_conf);
                    DP[conf][i]+=DP[prev_conf][j];
                }
            }
            SOLVED[conf][i]=1;
        }
    }
}

int main()
{
    cin>>s;
    cin>>m;
    for(long long i=1;i<=m;i++)
    {
        cin>>x>>y;
        REST[x-'a'][y-'a']=1;
        REST[y-'a'][x-'a']=1;
    }


    for(char c:s)
        F[c-'a']++;
    c='z'+1;
    for(long long i='a';i<='z';i++)
        if(F[i-'a']%2==1)
        {
            impare++;
            c=i;
        }

    if(impare>1)
    {
        cout<<"0\n";
        return 0;
    }

    s.clear();
    for(long long i='a';i<='z';i++)
    {
        if(F[i-'a']%2==1)
            continue;
        for(long long j=1;2*j<=F[i-'a'];j++)
            s += i;
    }

    n=s.size();
    factorial();
    for(long long i=0; i<n; i++)
    {
        DP[1<<i][i] = 1;
        SOLVED[1<<i][i] = 1;
    }

    long long max_conf = (1<<n)-1;

    solve(max_conf);

    long long sol = 0;
    for(int i='a'; i<='z'; i++)
        if(!REST[i-'a'][c-'a'])
            sol+=DP[max_conf][i-'a'];
    for(int i='a'; i<='z';i++)
        sol=sol/fact[F[i-'a']/2];
    cout<<sol%MOD<<"\n";

    return 0;
}