#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++) #define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++) #define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--) #define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) ((ll)(x).size()) #define len(x) ((ll)(x).length()) #define endl "\n" struct mint { constexpr static int mod = 1000000007; long long x; mint(long long x = 0) : x((x % mod + mod) % mod) {} mint operator-() const { return mint(-x); } mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint a) { if ((x += mod - a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; } mint operator+(const mint a) const { return mint(*this) += a; } mint operator-(const mint a) const { return mint(*this) -= a; } mint operator*(const mint a) const { return mint(*this) *= a; } mint pow(long long t) const { if (!t) return 1; mint a = pow(t >> 1); a *= a; if (t & 1) a *= *this; return a; } mint inv() const { return pow(mod - 2); } mint& operator/=(const mint a) { return *this *= a.inv(); } mint operator/(const mint a) const { return mint(*this) /= a; } }; const ll inf = LONG_LONG_MAX / 2 - 1; ll n, m, k; int main() { cin.tie(0); ios::sync_with_stdio(false); // ifstream in("input.txt"); // cin.rdbuf(in.rdbuf()); cin >> n >> m >> k; vector<vector<ll>> g(300, vector<ll>(300, inf)); rep(i, m) { ll p, q, c; cin >> p >> q >> c; p--; q--; g[p][q] = c; } vector<vector<vector<mint>>> dp(n, vector<vector<mint>>(300, vector<mint>(k + 1, 0))); rep(i, 300) dp[0][i][0] = 1; rep(i, n - 1) { rep(j, 300) { rep(o, 300) { if (g[j][o] == inf) continue; rep(p, k + 1 - g[j][o]) { dp[i + 1][o][p + g[j][o]] += dp[i][j][p]; } } } } mint ans = 0; rep(i, 300) ans += dp[n - 1][i][k]; cout << ans.x << endl; return 0; }