#include using namespace std; using ll = long long; const ll mod = 1e9 + 7; int main() { int n, m, k; cin >> n >> m >> k; vector>> a(n); for(int i = 0; i < m; i++) { int p, q, c; cin >> p >> q >> c; p--, q--; a[p].push_back({q, c}); } vector>> dp(n, vector>(n, vector(k + 1))); for(int i = 0; i < n; i++)dp[0][i][0] = 1; for(int i = 0; i < n - 1; i++) { for(int j = 0; j < n; j++) { for(auto p : a[j]) { for(int t = 0; t <= k; t++) { if(p.second + t > k)break; dp[i + 1][p.first][t + p.second] += dp[i][j][t]; dp[i + 1][p.first][t + p.second] %= mod; } } } } ll sum = 0; for(int i = 0; i < n; i++)sum += dp[n - 1][i][k]; cout << sum % mod << endl; }