#include <bits/stdc++.h>

using namespace std;

long long cnt['z' + 1];

bool bad['z' + 1]['z' + 1];

const long long MOD = 666013;

char s[17];
long long n;

long long DP[1 << 17]['z' + 1];

long long fact[18];
long long invFact[18];
long long inv[18];

int main() {
  string s;
  cin >> s;
  for(auto c: s)
    cnt[(long long)c]++;

  long long odd = 0;

  for(long long c = 'a' ; c <= 'z'; ++c) {
    odd += cnt[c] % 2;
    cnt[c] /= 2;
  }

  if(odd > 1 || (s.length() % 2 == 0 && odd > 0)) {
    cout << "0\n";
    return 0;
  }

  fact[1] = fact[0] = 1;

  for(long long i = 2; i <= 17; ++i)
    fact[i] = (i * fact[i - 1]) % MOD;

  inv[1] = 1;
  invFact[1] = 1;
  invFact[0] = inv[0] = 1;

  for(long long i = 2; i <= 17; ++i) {
    inv[i] = (1LL * MOD * MOD - 1LL * (MOD / i) * inv[MOD % i]) % MOD;
    invFact[i] = (1LL * invFact[i - 1] * inv[i]) % MOD;
  }

  for(long long c = 'a'; c <= 'z'; ++c) {
    long long aux = cnt[c];
    while(cnt[c] > 0) {
      s[n] = c;
      n++;
      cnt[c]--;
    }
    cnt[c] = aux;
  }



  long long m;
  cin >> m;
  for(long long i = 1; i <= m; ++i) {
    char x, y;
    cin >> x >> y;
    bad[(long long)x][(long long)y] = bad[(long long)y][(long long)x] = 1;
  }

  for(long long i = 0; i < n; ++i)
    DP[1 << i][(long long)s[i]]++;

  for(long long i = 0; i < (1 << n); ++i) {
    for(long long j = 0; j < n; ++j) {
      if(!((1 << j) & i))
        continue;
      long long c = s[j];
      for(long long k = 'a'; k <= 'z'; ++k) {
        DP[i][c] += DP[i ^ (1 << j)][k] * (1 - bad[c][k]);
        if(DP[i][c] >= MOD)
          DP[i][c] -= MOD;
      }
    }
  }

  const long long mask = (1 << n) - 1;
  long long ans = 0;


  for(long long i = 'a' ; i <= 'z'; ++i) {
    ans += DP[mask][i];
    if(ans >= MOD)
      ans -= MOD;
  }

  for(long long c = 'a' ; c <= 'z'; ++c)
    ans = (ans * invFact[cnt[c]]) % MOD;

  cout << ans << "\n";

  return 0;
}