#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25;
const int M = 1005;
const int S = 26;
const int mod = 1000003;

int ch[M][S] = {{0}}, fail[M] = {0}, f[M] = {0};
int tot = 0;

void insrt(string &s) {
	int cur = 0;
	for (auto i: s) {
		if (!ch[cur][i - 'a'])	
			ch[cur][i - 'a'] = ++tot;
		cur = ch[cur][i - 'a'];
	}
	f[cur] = 1;
}

int q[M] = {0}, fr, ba;
void build() {
	fr = 1, ba = 0;
	for (int i = 0; i < S; i++)
		if (ch[0][i])
			q[++ba] = ch[0][i];
	while (fr <= ba) {
		int x = q[fr++];
		for (int i = 0; i < S; i++)
			if (!ch[x][i])
				ch[x][i] = ch[fail[x]][i];
			else {
				fail[ch[x][i]] = ch[fail[x]][i];
				q[++ba] = ch[x][i];
			}
	}
	for (int i = 1; i <= ba; i++)
		f[q[i]] |= f[fail[q[i]]];
}

int dp[N][M][2][2][2] = {{{{{0}}}}};
void add(int &x, int y) {
	x = (x + y) % mod;
}

int A, B, m;

/*
0 1 3 5 7
o i e s t
*/

vector<int> res;

int main() {
	cin >> A >> B >> m;
	for (int i = 1; i <= m; i++) {
		string s;
		cin >> s;
		insrt(s);
	}
	build();
	res.push_back('o' - 'a');
	res.push_back('i' - 'a');
	res.push_back('e' - 'a');
	res.push_back('s' - 'a');
	res.push_back('t' - 'a');
	dp[0][0][0][0][0] = 1;
	for (int i = 0; i < B; i++) {
		for (int j = 0; j <= tot; j++) {
			for (int k = 0; k < S; k++)
				if (!f[ch[j][k]]) {
					for (int x = 0; x < 2; x++)
						for (int y = 0; y < 2; y++)
							for (int z = 0; z < 2; z++) 
								add(dp[i + 1][ch[j][k]][1][y][z], dp[i][j][x][y][z]);
					for (int x = 0; x < 2; x++)
						for (int y = 0; y < 2; y++)
							for (int z = 0; z < 2; z++)
								add(dp[i + 1][ch[j][k]][x][y][1], dp[i][j][x][y][z]);
				}
			for (auto k: res) 
				if (!f[ch[j][k]]) {
					for (int x = 0; x < 2; x++)
						for (int y = 0; y < 2; y++)
							for (int z = 0; z < 2; z++)
								add(dp[i + 1][ch[j][k]][x][1][z], dp[i][j][x][y][z]);		
				}
			for (int k = 0; k < 10; k++)
				if (k != 0 && k != 1 && k != 3 && k != 5 && k != 7) {
					for (int x = 0; x < 2; x++)
						for (int y = 0; y < 2; y++)
							for (int z = 0; z < 2; z++)
								add(dp[i + 1][0][x][1][z], dp[i][j][x][y][z]);
				}
		}
	}
	int ans = 0;
	for (int i = A; i <= B; i++)
		for (int j = 0; j <= tot; j++)
			add(ans, dp[i][j][1][1][1]);
	cout << ans << endl;
	return 0;
}