#pragma GCC target("avx2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int p[216], q[216], r[216]; int main() { long long mod = 1000000007; int m_size, m; cin >> m_size >> m; m_size = m; long long mat[216][216]; long long y; cin >> y; y -= 3; long long ans[216][216]; int co = 0; for (int i = 0; i < m; i++) { cin >> p[i] >> q[i] >> r[i]; if (y == 0 && p[i] == 1 && r[i] == 1) { co++; } } if (y == 0) { cout << co << endl; return 0; } for (int i = 0; i < m_size; i++) { for (int j = 0; j < m_size; j++) { mat[i][j]=0; } } for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { if (q[i] == p[j] && r[i] == q[j]) { mat[j][i]++; } } } for (int i = 0; i < m_size; i++) { for (int j = 0; j < m_size; j++) { ans[i][j]=mat[i][j]; } } y--; long long ans_mem[216][216]; for (int i = 0; i < m_size; i++) { for (int j = 0; j < m_size; j++) { ans_mem[i][j]=0; } } long long mat_mem[216][216]; for (int i = 0; i < m_size; i++) { for (int j = 0; j < m_size; j++) { mat_mem[i][j]=0; } } while (y > 0) { if ((y & 1) == 1) { for (int i = 0; i < m_size; i++) { for (int j = 0; j < m_size; j++) { ans_mem[i][j] = 0; } } for (int i = 0; i < m_size; i++) { for (int k = 0; k < m_size; k++) { for (int j = 0; j < m_size; j++) { ans_mem[i][j] += ans[i][k] * mat[k][j] % mod; if(ans_mem[i][j]>mod) ans_mem[i][j]-=mod; } } } for (int i = 0; i < m_size; i++) { for (int j = 0; j < m_size; j++) { ans[i][j] = ans_mem[i][j]; } } } for (int i = 0; i < m_size; i++) { for (int j = 0; j < m_size; j++) { mat_mem[i][j] = 0; } } for (int i = 0; i < m_size; i++) { for (int k = 0; k < m_size; k++) { for (int j = 0; j < m_size; j++) { mat_mem[i][j] += mat[i][k] * mat[k][j] % mod; if(mat_mem[i][j]>mod)mat_mem[i][j]-=mod; } } } for (int i = 0; i < m_size; i++) { for (int j = 0; j < m_size; j++) { mat[i][j] = mat_mem[i][j]; } } y >>= 1; } long long ans1 = 0; for (int i = 0; i < m; i++) {; for (int j = 0; j < m; j++) { if (r[i] == 1 && p[j] == 1) { ans1 += ans[i][j]; if(ans1>mod)ans1-=mod; } } } cout << ans1 << endl; }