#include <bits/stdc++.h>
#define ll long long int

using namespace std;

const int nax=1e5+5;
int n,m,k;
const int mod=1e9+7;

int dp[2][37][19];

int gg[nax][2];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k>>m;
    for(int i=0;i<nax;i++)
    {
        for(int j=0;j<2;j++)
        {
            gg[i][j]=-1;
        }
    }
    for(int i=0;i<m;i++)
    {
        int x,y,z; cin>>x>>y>>z;
        gg[x+1][y]=z;
    }
    //cout<<"JD"<<gg[2][0]<<endl;
    for(int a=0;a<=9;a++)
    {
        for(int b=0;b<=9;b++)
        {
            for(int c=0;c<=9;c++)
            {
                for(int d=0;d<=9;d++)
                {
                    if(gg[1][0]!=-1)
                    {
                        if(gg[1][0]!=a) continue;
                    }
                    if(gg[1][1]!=-1)
                    {
                        if(gg[1][1]!=b) continue;
                    }
                    if(gg[2][0]!=-1)
                    {
                        if(gg[2][0]!=c) continue;
                    }
                    if(gg[2][1]!=-1)
                    {
                        if(gg[2][1]!=d) continue;
                    }
                    if(a+b+c+d>k) continue;
                    //if(a+b+c+d==15 && c+d==7) //cout<<"XD"<< c<<" "<<d<<endl;
                    dp[0][a+b+c+d][c+d]++;
                }
            }
        }
    }
    //cout << dp[0][15][7];
    for(int i=3;i<=n;i++)
    {
        for(int j=0;j<=36;j++)
        {
            for(int xd=0;xd<=18;xd++) dp[i&1][j][xd]=0;
        }
        for(int a=0;a<=9;a++)
        {
            for(int b=0;b<=9;b++)
            {
                if(gg[i][0]!=-1 && gg[i][0]!=a) continue;
                if(gg[i][1]!=-1 && gg[i][1]!=b) continue;
                if(k-a-b>36) continue;
                if(a+b>k) continue;
                for(int suma=0;suma<=18;suma++)
                {
                    if(suma+a+b>k) break;
                    dp[i&1][suma+a+b][a+b]+=dp[(i-1)&1][k-a-b][suma];
                    if(dp[i&1][suma+a+b][a+b]>=mod) dp[i&1][suma+a+b][a+b]-=mod;
                }
            }
        }
    }
    ll wynik=0;
    //cout<<dp[1][16][3]<<endl;
    for(int i=0;i<=36;i++)
    {
        for(int j=0;j<=18;j++)
        {
            wynik+=dp[n&1][i][j];
            wynik%=mod;
        }
    }
    cout<<wynik;
    return 0;
}