Matrix<Mint>a(36,36),b(1,36);
Mint z;
ll k,m,n,p,q,r;
{
	rd(k,m,n);
	rep(m){
		rd(p--,q--,r--);
		a[p*6+q][q*6+r]=1;
	}
	b[0][0..5]=1;
	b*=a**(n-2);
	z+=b[0][(0..5)*6];
	wt(z);
}