K,n,L=map(int,input().split())
M=10**9+7
l=K*K
A=[[0]*l for i in range(l)]
for i in range(n):
  p1,p2,p3=map(int,input().split())
  p1-=1
  p2-=1
  p3-=1
  A[p3*K+p2][p2*K+p1]+=1

def seki(a,b):
  c=[[0]*l for i in range(l)]
  for i in range(l):
    for j in range(l):
      for k in range(l):
        c[i][j]+=a[i][k]*b[k][j]
        c[i][j]%=M
  return c

B=[[0]*l for i in range(l)]
for i in range(l):
  B[i][i]=1

L-=2
for i in range(60):
  if (L>>i)&1:
    B=seki(A,B)
  A=seki(A,A)

a=0
for i in range(K):
  for j in range(K):
    a+=B[0*K+i][j*K+0]
    a%=M
print(a)