#include <iostream> #include <cstdio> #include <map> #define LL long long #define MD 666013 using namespace std; string s; int m,fb[27][27],fr[27],nri; LL rz; char cm='z'+1; 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<<-1; 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; }