/*
*/

//#pragma comment(linker, "/STACK:16777216")
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash

#define eps 1e-11
//#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 256

using namespace std;

long n,n1,m,a,b,dp[105][78777];
long tmask;
vector<long> g[2000];

void add(long&a,long&b)
{
 a+=b;
 if (a>=bs)a-=bs;
}

 long ar[200];

long gett1(long msk,long p)
{
 for (int i=1;i<=n;i++)
 {ar[i]=msk%3;msk/=3;}
 for (int j=0;j<g[p].size();j++)
 {
  long q=g[p][j];
  if (ar[q]==0)ar[q]=1;
 }
 long r=0;
 for (int i=n;i;--i)
 r=r*3+ar[i];
 return r;
}

long answ;

long gett2(long msk, long v)
{
 for (int i=1;i<=n;i++)
 {ar[i]=msk%3;msk/=3;}
 if (ar[v]==2)return -1;
 ar[v]=2;

 long r=0;
 for (int i=n;i;--i)
 r=r*3+ar[i];
 return r;
}

bool nice(long msk)
{
 for (int i=1;i<=n;i++)
 {ar[i]=msk%3;msk/=3;}
 for (int i=1;i<=n;i++)
  if( ar[i]==1)return false;
 return true;
}


void show(long msk)
{
 for (int i=1;i<=n;i++)
 {ar[i]=msk%3;msk/=3;}
 for (int i=1;i<=n;i++)
  cout<<ar[i];
  cout<<endl;
}

int main(){
//freopen("rush.in","r",stdin);
//freopen("rush.out","w",stdout);
//freopen("C:/input.txt","r",stdin);
//freopen("C:/output.txt","w",stdout);
ios_base::sync_with_stdio(0);
//cin.tie(0);

cin>>n>>n1>>m;

for (int i=1;i<=m;i++)
{
 cin>>a>>b;
 g[b].push_back(a);
}

dp[0][0]=1;

long bb=0;

for (int i=1;i<=n1;i++)
{
 for (int old=0;old<60000;old++)
 {
  if (dp[i-1][old]==0)continue;
  // don't use
  tmask=gett1(old,i);
  bb=max(bb,tmask);
  add(dp[i][tmask],dp[i-1][old]);
  for (int j=0;j<g[i].size();j++)
  {
   tmask=gett2(old,g[i][j]);
   bb=max(bb,tmask);
   if (tmask!=-1)
    add(dp[i][tmask],dp[i-1][old]);
  }
 }
}

answ=0;
for (int i=0;i<60000;i++)
if (nice(i))
if (dp[n1][i]>0){
/* show(i);
 cout<<i<<endl;
 cout<<dp[n1][i]<<endl;
 cout<<endl;
*/ add(answ,dp[n1][i]);}

cout<<answ<<endl;

cin.get();cin.get();
return 0;}