#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int i,j,k,l,p,q,r;
int n,s,e;
int a[30];
string ss[30];
long long total;
bool b;
bool d[30];
int c[30][30];

long long cc(int x,int y)
{
	long double w;
	int i;
	w=1;
	for (i=x;i>y;i--)
		w=w*i;
	for (i=x-y;i>1;i--)
		w/=i;
	return long(w);
}

long long suan()
{
	long double w;
	int i,j;
	j=n;
	w=1;
	for (i=1;i<=s;i++)
	{
		if (a[i]>0)
		{
			w*=cc(j,a[i]);
			j-=a[i];
		}
	}
	return long(w);
}

void full(int x)
{
	if (x<0)
	{
		return;
	}
	else
	{
		if (x==0)
		{
			if (b)
				total+=suan();
			else
				total-=suan();
		}
		else
		{
		int i;
		for (i=1;i<=s;i++)
		{
			a[i]++;
			full(x-1);
			a[i]--;
		}
		}
	}
}

int Max(int x,int y)
{
	if (x>y)
		return x;
	else
		return y;
}

void go(int x,int y,int z)
{
	int i,j,k;
	if (x==y)
	{
		for (i=1;i<=s;i++)
			a[i]=0;
		for (j=1;j<=e;j++)
			if (d[j])
			{
				for (k=1;k<=s;k++)
				{
					if (c[j][k]!=0)
					{
						if (a[k]==0)
							a[k]=c[j][k];
						else
							a[k]=Max(a[k],c[j][k]);
					}
				}
			}
		j=0;
		for (i=1;i<=s;i++)
			j+=a[i];
		full(n-j);
	}
	else
	{
		for (i=z;i<=e-(x-y)+1;i++)
		{
			d[i]=1;
			go(x,y+1,i+1);
			d[i]=0;
		}
	}
}

int main()
{
	ifstream fin("cowyotz.in");
	ofstream fout("cowyotz.out");
	
	fin>>n>>s>>e;
	
	for (i=1;i<=e;i++)
		fin>>ss[i];
	
	total=0;
	
	for (i=1;i<=e;i++)
	{
		for (j=1;j<=s;j++)
			a[j]=0;
		j=0;
		p=0;
		while (j<(ss[i].length()))
		{
			a[int(ss[i][j+2])-int('0')]=int(ss[i][j])-int('0');
			p=p+a[int(ss[i][j+2])-int('0')];
			c[i][int(ss[i][j+2])-int('0')]=a[int(ss[i][j+2])-int('0')];
			j+=4;
		}
		b=1;
		full(n-p);
	}
	
	for (i=2;i<=n;i++)
	{
		if (b)
			b=0;
		else
			b=1;
		for (j=1;j<=e;j++)
			d[j]=0;
		go(i,0,1);
	}
	
	fout<<total;
	
	fin.close();
	fout.close();
	
	return 0;
}