#include <bits/stdc++.h>
using namespace std;

const int MXS = 1005;
const string FULC = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
const char CHS[] = "abcdefghijklmnopqrstuvwxyz24689";
const int CHST = 31;
const int MXN = 21;
const int DVS= 1e6 + 3;
int A, B, N, nxt[MXS][CHST], fail[MXS], ndsz(1), cnt[MXN][MXS][8], ans;
bool beend[MXS];
vector<int> son[MXS];
char str[MXS];

inline int id(char c) {
  if (c >= 'A' && c <= 'Z') return id('a' + (c - 'A'));
  if (c == '0') return id('o');
  if (c == '1') return id('i');
  if (c == '3') return id('e');
  if (c == '5') return id('s');
  if (c == '7') return id('t');
  return find(CHS, CHS + CHST, c) - CHS;
}
void mark(int p, bool m) {
  beend[p] = m = (m || beend[p]);
  for (int q : son[p]) mark(q, m);
}
void build() {
  static int que[MXS];
  int qh(0), qt(0);
  for (int i(0); i != CHST; ++i)
    if (nxt[0][i]) que[qt++] = nxt[0][i], son[0].push_back(nxt[0][i]);
  while (qh != qt) {
    int c(que[qh++]);
    for (int i(0); i != CHST; ++i) {
      int &n = nxt[c][i];
      if (n) {
        fail[n] = nxt[fail[c]][i];
        que[qt++] = n;
        son[fail[n]].push_back(n);
      } else {
        n = nxt[fail[c]][i];
      }
    }
  }
  mark(0, beend[0]);
}

int main() {
  cin >> A >> B >> N;
  while (N--) {
    cin >> str;
    int p(0), len(strlen(str));
    for (int i(0); i != len; ++i) {
      int &q(nxt[p][id(str[i])]);
      if (!q) q = ndsz++;
      p = q;
    }
    beend[p] = true;
  }
  build();
  cnt[0][0][0] = 1;
  for (int i(0); i != B; ++i) {
    for (int j(0); j != ndsz; ++j) {
      for (int k(0); k != 8; ++k) {
        for (char c : FULC) {
          int nj(nxt[j][id(c)]);
          if (beend[nj]) continue;
          int nk(k);
          if (c >= 'A' && c <= 'Z') nk |= 4;
          if (c >= 'a' && c <= 'z') nk |= 2;
          if (c >= '0' && c <= '9') nk |= 1;
          cnt[i + 1][nj][nk] = (cnt[i + 1][nj][nk] + cnt[i][j][k]) % DVS;
        }
      }
    }
  }
  for (int i(0); i != ndsz; ++i) {
    for (int j(A); j <= B; ++j) ans = (ans + cnt[j][i][7]) % DVS;
  }
  cout << ans << endl;
  return 0;
}