include<bits/stdc++.h>

define rep(i,x,y) for (int i=(x);i<=(y);i++)

define ll long long

define inf 1000000001

define y1 y1___

using namespace std;
char gc(){
static char buf[100000],p1=buf,p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:p1++;
}
#define gc getchar
ll read(){
char ch=gc();ll x=0;int op=1;
for (;!isdigit(ch);ch=gc()) if (ch=='-') op=-1;
for (;isdigit(ch);ch=gc()) x=(x<<1)+(x<<3)+ch-'0';
return xop;
}
#define N 405
int m,mod,n,ans,vis[N];bool flag;
char str[N],s[30][N];
struct node{
int len,val,ans,l[35][35],r[35];
bool flag;
}num[10],f[30];
void upd(int &x,int y){x+=y;x-=x>=mod?mod:0;}
node merge(node a,node b){
node ret;
if (a.flag) return b;
ret.len=a.lenb.len%m;
ret.val=(a.valb.len+b.val)%m;
rep (i,0,m-1) rep (j,0,m-1) ret.l[i][j]=a.l[i][j];
rep (i,0,m-1) rep (j,0,m-1) upd(ret.l[a.leni%m][(a.vali+j)%m],b.l[i][j]);
rep (i,0,m-1) ret.r[i]=b.r[i];
rep (i,0,m-1) upd(ret.r[(ib.len+b.val)%m],a.r[i]);
ret.ans=(a.ans+b.ans)%mod;
rep (i,0,m-1) rep (j,0,m-1) rep (k,0,m-1)
if ((ij+k)%m==0) upd(ret.ans,(ll)a.r[i]*b.l[j][k]%mod);
return ret;
}
void dfs(int u){
if (vis[u]) return;
vis[u]=1;
int len=strlen(s[u]+1);
f[u].flag=1;
rep (i,1,len) if ('A'<=s[u][i]&&s[u][i]<='Z'){
int v=s[u][i]-'A'+1;
dfs(v);
f[u]=merge(f[u],f[v]);
} else f[u]=merge(f[u],num[s[u][i]-'0']);
}
int main(){
m=read(),mod=read(),n=read();
rep (i,1,n){
scanf("%s",str+1);
int len=strlen(str+1);
int x=str[1]-'A'+1;
int len_=0;
rep (j,4,len) s[x][++len_]=str[j];s[x][len_+1]='\0';
}
rep (i,0,9){
num[i].len=10%m;
num[i].val=i%m;
num[i].ans=i%m==0;
num[i].l[10%m][i%m]=1;
num[i].r[i%m]=i!=0;
}
dfs(1);
printf("%d\n",f[1].ans);
return 0;
}