#include <bits/stdc++.h>
using namespace std;
const int md=666013;
int n,m,k,i,j,e,r,b,c,a[44],fa[44],t[44],f[(1<<20)][20];
bool g[44][44];
char s[44];
long long pw(int a, int b) {
  if (b==0) return 1LL;
  if (b&1) return (pw(a,b-1)*a)%md;
  long long x=pw(a,b/2);
  return (x*x)%md;
}
int main() {
  scanf("%s",s);
  n=strlen(s);
  for (fa[0]=i=1; i<=n; i++) fa[i]=(fa[i-1]*i)%md;
  for (i=0; i<n; i++) a[s[i]-'a']++;
  for (i=0; i<26; i++) {
    if (a[i]%2) { b=i; c++; }
    a[i]/=2;
    for (j=0; j<a[i]; j++, k++) t[k]=i;
  }
  if (c!=n%2) { puts("0"); return 0; }
  scanf("%d",&m);
  while (m--) {
    scanf("%s",s); i=s[0]-'a';
    scanf("%s",s); j=s[0]-'a';
    g[i][j]=g[j][i]=true;
  }
  if (c) {
    f[(1<<k)][k]=1;
    t[k++]=b;
  } else for (i=0; i<k; i++) if (g[t[i]][t[i]]==false) f[(1<<i)][i]=1;
  for (i=0; i<(1<<k); i++) for (j=0; j<k; j++) if (f[i][j])
    for (e=0; e<k; e++) if ((i&(1<<e))==0 && g[t[j]][t[e]]==false) f[i|(1<<e)][e]=(f[i|(1<<e)][e]+f[i][j])%md;
  i=(1<<k)-1;
  for (j=0; j<k; j++) if (f[i][j]) r=(r+f[i][j])%md;
  for (j=0; j<26; j++) if (a[j]) r=(r*pw(fa[a[j]],md-2))%md;
  printf("%d\n",r);
  return 0;
}