#include <bits/stdc++.h>
using namespace std;
const int md=666013;
int n,m,k,i,j,e,r,c,a[44],fa[44],t[77],f[(1<<20)][20];
bool g[44][44];
char s[44];
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) if (++c==1) {
      f[(1<<k)][k]=1;
      t[k++]=i;
    }
    a[i]/=2;
    for (j=0; j<a[i]; j++, k++) t[k]=i;
  }
  if (c!=n%2) { puts("0"); return 0; }
  if (c==0) for (i=0; i<k; i++) if (i==0 || t[i]!=t[i-1]) f[(1<<i)][i]=1;
  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;
  }
  for (i=0; i<(1<<k); i++) for (j=0; j<k; j++) if (f[i][j])
    for (e=0; e<k; e++) if (g[t[j]][t[e]]==false && (i&(1<<e))==0 && (e==0 || t[e]!=t[e-1] || (i&(1<<(e-1)))))
      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;
  printf("%d\n",r);
  return 0;
}