#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define ll long long int
#define vi vector<int>
const int mod=1000000007;
using namespace std;
int n,k,m;
int T[100005][3],A[19][19][19],B[19][19][19],P[4][19];
int S[19];
struct triple
{
    int a,b,c;
};
vector<triple> M;
vi W;
bool operator<(triple a,triple b)
{
    if(a.a!=b.a)
        return a.a<b.a;
    if(a.b!=b.b)
        return a.b<b.b;
    return a.c<b.c;
}
bool operator==(triple a, triple b){
    return !(a<b || b<a);
}
void funkcja(int i,int s)
{
    if(i==4)
    {

        if(s==k)
        {
            int a=W[0],b=W[1],c=W[2];
            M.pb({a,b,c});
            M.pb({b,c,a});
            M.pb({c,a,b});

            // cout<<s<<" "<<k<<" "<<W[0]<<" "<<W[1]<<" "<<W[2]<<endl;
            A[a][b][c]=P[1][a]*P[2][b]*P[3][c];
        }
        return;
    }
    if(T[i][1]!=-1&&T[i][2]!=-1)
    {
        W.pb(T[i][1]+T[i][2]);
        P[i][T[i][1]+T[i][2]]=1;
        funkcja(i+1,s+T[i][1]+T[i][2]);
        W.pop_back();
    }
    else if(T[i][1]!=-1||T[i][2]!=-1)
    {
        int x=max(T[i][1],T[i][2]);
        for(int j=0; j<=9; j++)
        {
            W.pb(x+j);
            P[i][x+j]=1;
            funkcja(i+1,s+x+j);
            W.pop_back();
        }
    }
    else
    {
        for(int j=0; j<=18; j++)
        {
            W.pb(j);
            P[i][j]=S[j];
            funkcja(i+1,s+j);
            W.pop_back();

        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cout.tie();
    cin>>n>>k>>m;
    for(int i=1; i<=n; i++)
    {
        T[i][1]=-1;
        T[i][2]=-1;
    }

    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        a++;
        b++;
        T[a][b]=c;
    }
    for(int i=0; i<=9; i++)
        for(int j=0; j<=9; j++)
            S[i+j]++;
    funkcja(1,0);
    sort(M.begin(),M.end());
    M.resize(unique(M.begin(),M.end())-M.begin());
    for(int i=4; i<=n; i++)
    {
        for(auto v:M)
        {
            int a=v.a,b=v.b,c=v.c;
            int ile=0;
            if(T[i][1]!=-1&&T[i][2]!=-1)
            {
                if(T[i][1]+T[i][2]==c)
                    ile=1;
            }
            else if(T[i][1]!=-1||T[i][2]!=-1)
            {
                int x=max(T[i][1],T[i][2]);
                if(c-x>=0&&c-x<=9)
                    ile=1;
            }
            else
                ile=S[c];
            B[a][b][c]=((ll)A[c][a][b]*ile)%mod;
        }
        for(auto v:M)
        {
            int a=v.a,b=v.b,c=v.c;
            A[a][b][c]=B[a][b][c];
            B[a][b][c]=0;
        }
    }
    ll wynik=0;
    for(auto v:M)
    {
        int a=v.a,b=v.b,c=v.c;
        wynik+=A[a][b][c];
        wynik%=mod;

    }
    cout<<wynik;
    return 0;
}