#line 1 "main.cpp" #include #line 2 "/home/user/Library/utils/macros.hpp" #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) #line 4 "/home/user/Library/modulus/modpow.hpp" inline int32_t modpow(uint_fast64_t x, uint64_t k, int32_t MOD) { assert (/* 0 <= x and */ x < (uint_fast64_t)MOD); uint_fast64_t y = 1; for (; k; k >>= 1) { if (k & 1) (y *= x) %= MOD; (x *= x) %= MOD; } assert (/* 0 <= y and */ y < (uint_fast64_t)MOD); return y; } #line 5 "/home/user/Library/modulus/modinv.hpp" inline int32_t modinv_nocheck(int32_t value, int32_t MOD) { assert (0 <= value and value < MOD); if (value == 0) return -1; int64_t a = value, b = MOD; int64_t x = 0, y = 1; for (int64_t u = 1, v = 0; a; ) { int64_t q = b / a; x -= q * u; std::swap(x, u); y -= q * v; std::swap(y, v); b -= q * a; std::swap(b, a); } if (not (value * x + MOD * y == b and b == 1)) return -1; if (x < 0) x += MOD; assert (0 <= x and x < MOD); return x; } inline int32_t modinv(int32_t x, int32_t MOD) { int32_t y = modinv_nocheck(x, MOD); assert (y != -1); return y; } #line 4 "/home/user/Library/modulus/mint_core.hpp" /** * @brief quotient ring / 剰余環 $\mathbb{Z}/n\mathbb{Z}$ */ template struct mint { int32_t value; mint() : value() {} mint(int64_t value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD : value_) {} mint(int32_t value_, std::nullptr_t) : value(value_) {} explicit operator bool() const { return value; } inline mint operator + (mint other) const { return mint(*this) += other; } inline mint operator - (mint other) const { return mint(*this) -= other; } inline mint operator * (mint other) const { return mint(*this) *= other; } inline mint & operator += (mint other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; } inline mint & operator -= (mint other) { this->value -= other.value; if (this->value < 0) this->value += MOD; return *this; } inline mint & operator *= (mint other) { this->value = (uint_fast64_t)this->value * other.value % MOD; return *this; } inline mint operator - () const { return mint(this->value ? MOD - this->value : 0, nullptr); } inline bool operator == (mint other) const { return value == other.value; } inline bool operator != (mint other) const { return value != other.value; } inline mint pow(uint64_t k) const { return mint(modpow(value, k, MOD), nullptr); } inline mint inv() const { return mint(modinv(value, MOD), nullptr); } inline mint operator / (mint other) const { return *this * other.inv(); } inline mint & operator /= (mint other) { return *this *= other.inv(); } }; template mint operator + (int64_t value, mint n) { return mint(value) + n; } template mint operator - (int64_t value, mint n) { return mint(value) - n; } template mint operator * (int64_t value, mint n) { return mint(value) * n; } template mint operator / (int64_t value, mint n) { return mint(value) / n; } template std::istream & operator >> (std::istream & in, mint & n) { int64_t value; in >> value; n = value; return in; } template std::ostream & operator << (std::ostream & out, mint n) { return out << n.value; } #line 4 "main.cpp" using namespace std; constexpr int MOD = 1000000007; mint solve(int n, int m, int k, const vector & p, const vector & q, const vector & c) { constexpr int V = 300; vector, V> > cur, prv; cur.assign(k + 1, array, V>()); REP (i, V) { cur[0][i] += 1; } REP (i, n - 1) { cur.swap(prv); cur.assign(k + 1, array, V>()); REP (cost, k + 1) { REP (j, m) if (cost + c[j] < k + 1) { cur[cost + c[j]][q[j]] += prv[cost][p[j]]; } } } return accumulate(ALL(cur[k]), mint()); } // generated by online-judge-template-generator v4.4.0 (https://github.com/kmyk/online-judge-template-generator) int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); constexpr char endl = '\n'; int N; int M; int K; cin >> N >> M >> K; vector P(M), Q(M), C(M); REP (i, M) { cin >> P[i] >> Q[i] >> C[i]; -- P[i]; -- Q[i]; } auto ans = solve(N, M, K, P, Q, C); cout << ans << endl; return 0; }