MOD = 10**9 + 7

K, M, N = map(int, input().split())

allowed = set()
for _ in range(M):
    p, q, r = map(int, input().split())
    allowed.add((p, q, r))

# Generate all possible states (a, b)
states = []
index = {}
for a in range(1, K + 1):
    for b in range(1, K + 1):
        states.append((a, b))
        index[(a, b)] = len(states) - 1

size = len(states)

# Initialize transition matrix
matrix = [[0] * size for _ in range(size)]
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            if (a, b, c) in allowed:
                if (a, b) in index and (b, c) in index:
                    i = index[(a, b)]
                    j = index[(b, c)]
                    matrix[i][j] += 1

# Matrix exponentiation functions
def multiply(a, b):
    res = [[0] * size for _ in range(size)]
    for i in range(size):
        for k in range(size):
            if a[i][k] == 0:
                continue
            for j in range(size):
                res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % MOD
    return res

def matrix_power(mat, power):
    result = [[0] * size for _ in range(size)]
    for i in range(size):
        result[i][i] = 1
    while power > 0:
        if power % 2 == 1:
            result = multiply(result, mat)
        mat = multiply(mat, mat)
        power //= 2
    return result

if N == 1 or N == 2:
    print(1 if N == 1 and K >= 1 else 0)
    exit()

pow_count = N - 2
mat = matrix_power(matrix, pow_count)

# Initial vector: starts with (1, b) for all b
initial = [0] * size
for b in range(1, K + 1):
    key = (1, b)
    if key in index:
        initial[index[key]] = 1

# Multiply initial vector with the exponentiated matrix
result = [0] * size
for i in range(size):
    if initial[i]:
        for j in range(size):
            result[j] = (result[j] + initial[i] * mat[i][j]) % MOD

# Sum all states ending with 1
answer = 0
for (a, b), idx in index.items():
    if b == 1:
        answer = (answer + result[idx]) % MOD

print(answer)