#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; }