//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cmath>
#include <queue>
#include <bitset>
#include <numeric>
#include <array>
#include <cstring>
#include <random>
#include <chrono>
#include <cassert>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

mt19937 rng(4242);

const int max_n = -1, inf = 1000111222;

class AhoCorasick {
public:
    static const int min_c = 'a', max_c = 'z' + 1;
    struct Node {
        friend class AhoCorasick;
        int parent, parent_c;
        bool is_terminal;

        Node(int parent, int parent_c): suffix_link(-1), parent(parent), parent_c(parent_c), closest_terminal(-1), is_terminal(false) {
            memset(nxt, -1, sizeof(nxt));
        };
    private:
        int nxt[max_c - min_c + 1], suffix_link;
        int closest_terminal;
    };
    vector<Node> nodes;

    AhoCorasick(): nodes({{0, 0}}) {}

    AhoCorasick(int max_nodes) : nodes({{0, 0}}) {
        nodes.reserve(max_nodes);
    }

    void clear() {
        nodes.clear();
        nodes.pb({0, 0});
    }

    int add(const string &s) {
        int v = 0;
        for (char cur_c : s) {
            assert(min_c <= cur_c && cur_c <= max_c);
            const int c = cur_c - min_c;
            if(nodes[v].nxt[c] == -1) {
                nodes[v].nxt[c] = nodes.size();
                nodes.pb({v, c});
            }
            v = nodes[v].nxt[c];
        }
        nodes[v].is_terminal = true;
        return v;
    }
    int get_nxt(int v, int c) {
        assert(min_c <= c && c <= max_c);
        c -= min_c;
        return get_nxt_private(v, c);
    }
    int get_suffix_link(int v) {
        if(nodes[v].suffix_link == -1) {
            if(nodes[v].parent == 0) {
                nodes[v].suffix_link = 0;
            } else {
                nodes[v].suffix_link = get_nxt_private(get_suffix_link(nodes[v].parent), nodes[v].parent_c);
            }
        }
        return nodes[v].suffix_link;
    }
    int get_closest_terminal(int v) {
        if(nodes[v].closest_terminal == -1) {
            if(v == 0) {
                nodes[v].closest_terminal = 0;
            } else if(nodes[v].is_terminal) {
                nodes[v].closest_terminal = v;
            } else {
                nodes[v].closest_terminal = get_closest_terminal(get_suffix_link(v));
            }
        }
        return nodes[v].closest_terminal;
    }
    vector<vector<int> > get_suffix_link_tree() {
        vector<vector<int> > g(nodes.size());
        for(int i = 1; i < nodes.size(); i++) {
            g[get_suffix_link(i)].pb(i);
        }
        return g;
    }
    vector<int> get_bfs_order() {
        queue<int> q;
        vector<int> res;
        vector<char> used(nodes.size());
        q.push(0);
        used[0] = 1;
        while(!q.empty()) {
            int v = q.front();
            q.pop();
            res.pb(v);
            for(int c = 0; c <= max_c - min_c; c++) {
                if(!used[get_nxt_private(v, c)]) {
                    q.push(get_nxt_private(v, c));
                    used[get_nxt_private(v, c)] = 1;
                }
            }
        }
        return res;
    }
private:
    int get_nxt_private(int v, int c) {
        if(nodes[v].nxt[c] == -1) {
            if(v == 0) {
                nodes[v].nxt[c] = 0;
            } else {
                nodes[v].nxt[c] = get_nxt_private(get_suffix_link(v), c);
            }
        }
        return nodes[v].nxt[c];
    }
};

const int mod = 1000003;

int add(int a, int b) {
    return (a + b) % mod;
}

void solve() {
    int a, b;
    cin >> a >> b;
    int n;
    cin >> n;
    vector<string> bad(n);
    AhoCorasick aho = AhoCorasick(222);
    for(auto& x : bad) {
        cin >> x;
        aho.add(x);
    }
    int amv = len(aho.nodes);
    vector<bool> bad_v(amv);
    for(int i = 0; i < amv; i++) {
        int cur_v = i;
        bool have_terminal = false;
        while(cur_v != 0) {
            have_terminal |= aho.nodes[cur_v].is_terminal;
            cur_v = aho.get_suffix_link(cur_v);
        }
        bad_v[i] = have_terminal;
    }
    vector<pair<int, int> > transitions; //mask, char
    for(int i = 'a'; i <= 'z'; i++) transitions.pb({(1 << 0), i}); //lowercase
    for(int i = 'a'; i <= 'z'; i++) transitions.pb({(1 << 1), i}); //uppercase
    //digits
    {
        transitions.pb({(1 << 2), 'o'}); //0
        transitions.pb({(1 << 2), 'i'}); //1
        transitions.pb({(1 << 2), 'z' + 1}); //2
        transitions.pb({(1 << 2), 'e'}); //3
        transitions.pb({(1 << 2), 'z' + 1}); //4
        transitions.pb({(1 << 2), 's'}); //5
        transitions.pb({(1 << 2), 'z' + 1}); //6
        transitions.pb({(1 << 2), 't'}); //7
        transitions.pb({(1 << 2), 'z' + 1}); //8
        transitions.pb({(1 << 2), 'z' + 1}); //9
    }
    vector<vector<int> > dp(amv, vector<int>((1 << 3))), ndp(amv, vector<int>((1 << 3)));
    dp[0][0] = 1;
    int ans = 0;
    for(int lenS = 1; lenS <= b; lenS++) {
        for(int state = 0; state < amv; state++) {
            for(int mask = 0; mask < 8; mask++) {
                for(auto& x : transitions) {
                    int nstate = aho.get_nxt(state, x.se);
                    if(bad_v[nstate]) continue;
                    int nmask = (mask | (x.fi));
                    ndp[nstate][nmask] = add(ndp[nstate][nmask], dp[state][mask]);
                }
            }
        }
        for(int state = 0; state < amv; state++) {
            for (int mask = 0; mask < 8; mask++) {
                dp[state][mask] = ndp[state][mask];
                ndp[state][mask] = 0;
            }
        }
        if(lenS >= a) {
            for(int v = 0; v < amv; v++) ans = add(ans, dp[v][7]);
        }
    }
    cout << ans << '\n';
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;

//    cin >> t;

    while (t--) solve();

}

/*
KIVI
*/