#include<cstdio>
const long long mod = 1e9+7;
long long a[50][50], res[50][50], c[50][50];
long long org[50], ans[50];

void mul(long long u[50][50],long long v[50][50],int n){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            c[i][j] = 0;
            for(int k = 1; k <= n; k++){
                c[i][j] += u[i][k]*v[k][j]%mod;
                if(c[i][j]>=mod) c[i][j] -= mod; 
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) u[i][j] = c[i][j];
    }
}

void power(long long u[50][50],long long b,int n){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) res[i][j] = i==j;
    }
    while(b){
        if(b&1) mul(res,u,n);
        mul(u,u,n);
        b /= 2;
    }
}

int main(){
    int k,m; long long n;
    scanf("%d%d%lld",&k,&m,&n);
    for(int i = 0; i < m; i++){
        int p,q,r;
        scanf("%d%d%d",&p,&q,&r);
        int from = p*k+q, to = q*k+r;
        a[to][from] = 1;
        if(p==1){ 
            //printf("to = %d\n",to);
            org[to] = 1;
        }
    }
    n -= 3;
    int total = (k+1)*k;
    power(a,n,total);
    /*for(int i = 1; i <= total; i++){
        for(int j = 1; j <= total; j++) printf("%lld ",res[i][j]);
        printf("\n");
    }*/
    for(int i = 1; i <= total; i++){
        long long cur = 0;
        for(int j = 1; j <= total; j++){
            cur += org[j]*res[i][j]%mod;
            if(cur>=mod) cur -= mod;
        }
        ans[i] = cur;
    }
    long long sum = 0;
    for(int i = 1; i <= k; i++){
        int id = i*k+1;
        sum += ans[id];
        if(sum>=mod) sum -= mod;
    }
    printf("%lld\n",sum);
    return 0;
}