/*
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#define For(i,l,r) for(register int i=(l);i<=(r);i++)
#define Rof(i,l,r) for(register int i=(l);i>=(r);i--)
#define bug cout<<"Ln:"<<__LINE__<<'\n'
bool MS;
struct ACAM{
	int cnt,tr[1005][26];bool ed[1005];
	void insert(char str[]){
		int len=strlen(str+1),p=0;
		For(i,1,len){
			int t=str[i]-'a';
			if(!tr[p][t]) tr[p][t]=++cnt;
			p=tr[p][t];
		}
		ed[p]=1;
	}
	int fail[1005];
	queue<int>q;
	void build(){
		fail[0]=0;
		For(i,0,25) if(tr[0][i]) fail[tr[0][i]]=0,q.push(tr[0][i]);
		while(!q.empty()){
			int u=q.front();q.pop();
			ed[u]|=ed[fail[u]];
			For(i,0,25){
				if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
				else tr[u][i]=tr[fail[u]][i];
			}
		}
	}
}acam;
const int mod=1000003;
int nl,nr,m,f[25][1005][2][2][2];
char s[25];
void upd(int &x,int y){
	x=(x+y)%mod;
}
bool MT;
signed main(){
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	// cerr<<"Memory: "<<1.0*(&MS-&MT)/1048576<<"MiB\n";
	cin>>nl>>nr;
	cin>>m;
	For(i,1,m){
		cin>>(s+1);
		acam.insert(s);
	}
	acam.build();
	assert(acam.cnt<1005);
	f[0][0][0][0][0]=1;
	For(i,0,nr-1){
		For(j,0,acam.cnt) if(!acam.ed[j]){
			For(a,0,1){
				For(b,0,1){
					For(c,0,1){
						For(k,0,25){
							upd(f[i+1][acam.tr[j][k]][1][b][c],f[i][j][a][b][c]);
							upd(f[i+1][acam.tr[j][k]][a][1][c],f[i][j][a][b][c]);
						}
						For(k,0,9){
							if(k==0) upd(f[i+1][acam.tr[j]['o'-'a']][a][b][1],f[i][j][a][b][c]);
							else if(k==1) upd(f[i+1][acam.tr[j]['i'-'a']][a][b][1],f[i][j][a][b][c]);
							else if(k==3) upd(f[i+1][acam.tr[j]['e'-'a']][a][b][1],f[i][j][a][b][c]);
							else if(k==5) upd(f[i+1][acam.tr[j]['s'-'a']][a][b][1],f[i][j][a][b][c]);
							else if(k==7) upd(f[i+1][acam.tr[j]['t'-'a']][a][b][1],f[i][j][a][b][c]);
							else upd(f[i+1][0][a][b][1],f[i][j][a][b][c]);
						}
					}
				}
			}
		}
	}
	int ans=0;
	For(i,nl,nr){
		For(j,0,acam.cnt) if(!acam.ed[j]){
			upd(ans,f[i][j][1][1][1]);
		}
	}
	cout<<ans<<'\n';
	return 0;
}
/*
3 5
9
swerc
icpc
fbi
cia
bio
z
hi
no
yes
*/