#include <iostream>
#include <cstdio>
#include <unordered_map>
#define LL long long
#define MD 666013
using namespace std;

string s;
int m,fb[270][270],fr[270],nri;
LL rz;
char cm='z'+1;
unordered_map<string,LL> nr;

string itos(int n) {
  string r;
  for(;n;n/=10) r+=char(n%10+'0');
  return r;
}

int clc(int p, int lst) {
  if(p==s.size()/2) return 1;
  string sc;
  for(int i=0; i<26; ++i) {
    sc+=itos(fr[i]);
    sc+='|';
  }
  sc+=itos(lst);
  
  if(nr.find(sc)!=nr.end()) return nr[sc];
  nr[sc]=0;
  for(int i=0; i<26; ++i) if(fr[i] && !fb[lst][i]) {
    --fr[i];
    nr[sc]+=clc(p+1,i);
    ++fr[i];
  }
  nr[sc]%=MD;
  //cout<<p<<' '<<lst<<' '<<sc<<' '<<fb[lst][0]<<' '<<nr[sc]<<'\n';
  return nr[sc];
}

int main() {
  //freopen("input.txt","r",stdin);
  cin>>s;
  for(int i=0; i<s.size(); ++i) ++fr[s[i]-'a'];
  for(int i=0; i<26; ++i)
    if(fr[i]&1) {
      if(nri) {
        cout<<0;
        return 0;
      }
      ++nri;
      cm=i;
      fr[i]/=2;
    }else fr[i]/=2;

  for(cin>>m;m--;) {
    char a,b; cin>>a>>b;
    fb[a-'a'][b-'a']=fb[b-'a'][a-'a']=1;
  }
  for(int i=0; i<26; ++i) if(!fb[cm][i] && fr[i] && (nri==1 || (nri==0 && !fb[i][i]))) {
    --fr[i];
    rz+=clc(1,i);
    ++fr[i];
  }
  cout<<rz%MD;
}