// #pragma GCC optimize ("O3") // #pragma GCC target("avx512f") // #pragma GCC optimize("unroll-loops") #ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG #endif #include // #include using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/ #define pb push_back #define pf push_front #define fi first #define se second #define eb emplace_back #define endl '\n' #define SZ(x) ((ll)(x).size()) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define debug(v) cout<<#v<<":";for(auto x:v){cout< Point; // Point typedef long long ll; typedef vector vl; typedef vectorvvl; typedef vectorvvvl; typedef vectorvvvvl; typedef vectorvvvvvl; typedef pair P; typedef tuple T; template using minpq=priority_queue,greater>; const ll MOD=1000000007LL; // const ll MOD=998244353LL; const ll mod=MOD; string abc="abcdefghijklmnopqrstuvwxyz"; string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; vl dx={0,0,1,-1,1,1,-1,-1}; vl dy={1,-1,0,0,-1,1,-1,1}; template vector make_vec(size_t a) { return vector(a); } template auto make_vec(size_t a, Ts... ts) { return vector(ts...))>(a, make_vec(ts...)); } templatebool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(bprime_factor(ll n){ mapres; for(ll i=2;i*i<=n;i++){ while(n%i==0){ res[i]++; n/=i; } } if(n!=1)res[n]=1; return res; } const ll MAX = 5000010; long long fac[MAX], finv[MAX], inv[MAX]; //finvが階乗の逆元 // テーブルを作る前処理 void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (ll i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } // 二項係数計算 long long COM(ll n, ll k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } ll modpow(ll a, ll n,ll mod=MOD) { ll res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } /*Eratosthenes() ll N=2000010; vl arr(N); void Eratosthenes(){ for(ll i = 0; i < N; i++){ arr[i] = 1; } arr[1]=0; for(ll i = 2; i < sqrt(N); i++){ if(arr[i]){ for(ll j = 0; i * (j + 2) < N; j++){ arr[i *(j + 2)] = 0; } } } }*/ //素数判定O(√n) bool is_prime(ll n){ for(ll i=2;i*i<=n;i++){ if(n%i==0)return false; } return n!=1; } //約数の列挙O(√n) vectordivisor(ll n){ vectorres; for(ll i=1;i*i<=n;i++){ if(n%i==0){ res.push_back(i); if(i != n/i) res.push_back(n/i); } } return res; } /* Trie 木: 文字の種類(char_size)、int型で0に対応する文字(base) insert(word): 単語 word を Trie 木に挿入する search(word): 単語 word が Trie 木にあるか判定する start_with(prefix): prefix が一致する単語が Trie 木にあるか判定する count(): 挿入した単語の数を返す size(): Trie 木の頂点数を返す 計算量:insert, search ともに O(M)(Mは単語の長さ) */ template struct Trie { struct Node { // 頂点を表す構造体 vector next; // 子の頂点番号を格納。存在しなければ-1 vector accept; // 末端がこの頂点になる単語の word_id を保存 int c; // base からの間隔をint型で表現したもの int common; // いくつの単語がこの頂点を共有しているか Node(int c_) : c(c_), common(0) { next.assign(char_size, -1); } }; vector nodes; // trie 木本体 int root; Trie() : root(0) { nodes.push_back(Node(root)); } // 単語の挿入 void insert(const string &word, int word_id) { int node_id = 0; for (int i = 0; i < (int)word.size(); i++) { int c = (int)(word[i] - base); int &next_id = nodes[node_id].next[c]; if (next_id == -1) { // 次の頂点が存在しなければ追加 next_id = (int)nodes.size(); nodes.push_back(Node(c)); } ++nodes[node_id].common; node_id = next_id; } ++nodes[node_id].common; nodes[node_id].accept.push_back(word_id); } void insert(const string &word) { insert(word, nodes[0].common); } // 単語とprefixの検索 bool search(const string &word, bool prefix = false) { int node_id = 0; for (int i = 0; i < (int)word.size(); i++) { int c = (int)(word[i] - base); int &next_id = nodes[node_id].next[c]; if (next_id == -1) { // 次の頂点が存在しなければ終了 return false; } node_id = next_id; } return (prefix) ? true : nodes[node_id].accept.size() > 0; } // prefix を持つ単語が存在するかの検索 bool start_with(const string &prefix) { return search(prefix, true); } // 挿入した単語の数 int count() const { return (nodes[0].common); } // Trie木のノード数 int size() const { return ((int)nodes.size()); } }; // //Lowest Common Ancestor // struct Edge{ // int to; // Edge(int to):to(to){} // }; // using Graph = vector>; // class lca { // public: // const int n = 0; // const int log2_n = 0; // vector> parent; // vector depth; // lca() {} // //g:グラフ root:根 // lca(const Graph &g, int root) // : n(g.size()), log2_n(log2(n) + 1), parent(log2_n, vector(n)), depth(n) { // dfs(g, root, -1, 0); // for (int k = 0; k + 1 < log2_n; k++) { // for (int v = 0; v < (int)g.size(); v++) { // if (parent[k][v] < 0) // parent[k + 1][v] = -1; // else // parent[k + 1][v] = parent[k][parent[k][v]]; // } // } // } // void dfs(const Graph &g, int v, int p, int d) { // parent[0][v] = p; // depth[v] = d; // for (auto &e : g[v]) { // if (e.to != p) dfs(g, e.to, v, d + 1); // } // } // //uとvのlcaを取得 // int get(int u, int v) { // if (depth[u] > depth[v]) swap(u, v); // for (int k = 0; k < log2_n; k++) { // if ((depth[v] - depth[u]) >> k & 1) { // v = parent[k][v]; // } // } // if (u == v) return u; // for (int k = log2_n - 1; k >= 0; k--) { // if (parent[k][u] != parent[k][v]) { // u = parent[k][u]; // v = parent[k][v]; // } // } // return parent[0][u]; // } // int dep(int i) { // return depth[i]; // } // int dist(int u,int v){ // return depth[u]+depth[v]-depth[get(u,v)]*2; // } // }; // union by size + path having class UnionFind { public: vector par; // 各元の親を表す配列 vector siz; // 素集合のサイズを表す配列(1 で初期化) // Constructor UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) { for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身 } void init(ll sz_) { par.resize(sz_); siz.assign(sz_, 1LL); // resize だとなぜか初期化されなかった for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身 } // Member Function // Find ll root(ll x) { // 根の検索 while (par[x] != x) { x = par[x] = par[par[x]]; // x の親の親を x の親とする } return x; } // Union(Unite, Merge) bool merge(ll x, ll y) { x = root(x); y = root(y); if (x == y) return false; // merge technique(データ構造をマージするテク.小を大にくっつける) if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; par[y] = x; return true; } bool issame(ll x, ll y) { // 連結判定 return root(x) == root(y); } ll size(ll x) { // 素集合のサイズ return siz[root(x)]; } }; // 0-indexed parmutation only vvl cycle_partition(const vl &p){ ll n=p.size(); vvl ret; vector check(n,false); rep(i,n)if(!check[p[i]]){ vl v; ll pos=p[i]; v.pb(i); check[i]=true; while(pos!=i){ v.pb(pos); check[pos]=true; pos=p[pos]; } ret.pb(v); } return ret; } vl Z_algorithm(vl s){ ll c=0,n=s.size(); vl Z(n,0); for(ll i=1;i=0 && i+j T pow(T a, long long n, T e = 1) { T ret = e; while (n) { if (n & 1) ret *= a; a *= a; n >>= 1; } return ret; } template struct ModInt { int x; ModInt() : x(0) {} ModInt(long long x_) { if ((x = x_ % mod + mod) >= mod) x -= mod; } ModInt& operator+=(ModInt rhs) { if ((x += rhs.x) >= mod) x -= mod; return *this; } ModInt& operator-=(ModInt rhs) { if ((x -= rhs.x) < 0) x += mod; return *this; } ModInt& operator*=(ModInt rhs) { x = (unsigned long long)x * rhs.x % mod; return *this; } ModInt& operator/=(ModInt rhs) { x = (unsigned long long)x * rhs.inv().x % mod; return *this; } ModInt operator-() const { return -x < 0 ? mod - x : -x; } ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; } ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; } ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; } ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; } bool operator==(ModInt rhs) const { return x == rhs.x; } bool operator!=(ModInt rhs) const { return x != rhs.x; } ModInt inv() const { return pow(*this, mod - 2); } friend ostream& operator<<(ostream& s, ModInt a) { s << a.x; return s; } friend istream& operator>>(istream& s, ModInt& a) { s >> a.x; return s; } }; using mint = ModInt; typedef vector vm; typedef vector >vvm; typedef vector > >vvvm; template struct segment_tree_beats{ int N; vector max1, max2, min1, min2, add, sum; vector maxc, minc, len; void update_max(int i, T x){ sum[i] += (x - max1[i]) * maxc[i]; if (max1[i] == min1[i]){ min1[i] = x; } else if (max1[i] == min2[i]){ min2[i] = x; } max1[i] = x; } void update_min(int i, T x){ sum[i] += (x - min1[i]) * minc[i]; if (min1[i] == max1[i]){ max1[i] = x; } else if (min1[i] == max2[i]){ max2[i] = x; } min1[i] = x; } void update_add(int i, T x){ max1[i] += x; if (max2[i] != -INF){ max2[i] += x; } min1[i] += x; if (min2[i] != INF){ min2[i] += x; } sum[i] += x * len[i]; add[i] += x; } void push(int i){ if (i >= N - 1){ return; } int l = i * 2 + 1; int r = i * 2 + 2; if (add[i] != 0){ update_add(l, add[i]); update_add(r, add[i]); add[i] = 0; } if (max1[i] < max1[l]){ update_max(l, max1[i]); } if (min1[i] > min1[l]){ update_min(l, min1[i]); } if (max1[i] < max1[r]){ update_max(r, max1[i]); } if (min1[i] > min1[r]){ update_min(r, min1[i]); } } void update(int i){ int l = i * 2 + 1; int r = i * 2 + 2; sum[i] = sum[l] + sum[r]; if (max1[l] > max1[r]){ max1[i] = max1[l]; max2[i] = max(max2[l], max1[r]); maxc[i] = maxc[l]; } else if (max1[l] < max1[r]){ max1[i] = max1[r]; max2[i] = max(max1[l], max2[r]); maxc[i] = maxc[r]; } else { max1[i] = max1[l]; max2[i] = max(max2[l], max2[r]); maxc[i] = maxc[l] + maxc[r]; } if (min1[l] < min1[r]){ min1[i] = min1[l]; min2[i] = min(min2[l], min1[r]); minc[i] = minc[l]; } else if (min1[l] > min1[r]){ min1[i] = min1[r]; min2[i] = min(min1[l], min2[r]); minc[i] = minc[r]; } else { min1[i] = min1[l]; min2[i] = min(min2[l], min2[r]); minc[i] = minc[l] + minc[r]; } } segment_tree_beats(vector A){ int n = A.size(); N = 1; while (N < n){ N *= 2; } max1 = vector(N * 2 - 1, -INF); max2 = vector(N * 2 - 1, -INF); min1 = vector(N * 2 - 1, INF); min2 = vector(N * 2 - 1, INF); add = vector(N * 2 - 1, 0); sum = vector(N * 2 - 1, 0); maxc = vector(N * 2 - 1, 1); minc = vector(N * 2 - 1, 1); len = vector(N * 2 - 1, 1); for (int i = 0; i < n; i++){ max1[N - 1 + i] = A[i]; min1[N - 1 + i] = A[i]; sum[N - 1 + i] = A[i]; } for (int i = N - 2; i >= 0; i--){ len[i] = len[i * 2 + 1] + len[i * 2 + 2]; update(i); } } void range_chmin(int L, int R, T x, int i, int l, int r){ if (r <= L || R <= l || x >= max1[i]){ return; } else if (L <= l && r <= R && x > max2[i]){ update_max(i, x); return; } push(i); int m = (l + r) / 2; range_chmin(L, R, x, i * 2 + 1, l, m); range_chmin(L, R, x, i * 2 + 2, m, r); update(i); } void range_chmax(int L, int R, T x, int i, int l, int r){ if (r <= L || R <= l || x <= min1[i]){ return; } else if (L <= l && r <= R && x < min2[i]){ update_min(i, x); return; } push(i); int m = (l + r) / 2; range_chmax(L, R, x, i * 2 + 1, l, m); range_chmax(L, R, x, i * 2 + 2, m, r); update(i); } void range_add(int L, int R, T x, int i, int l, int r){ if (r <= L || R <= l){ return; } else if (L <= l && r <= R){ update_add(i, x); return; } push(i); int m = (l + r) / 2; range_add(L, R, x, i * 2 + 1, l, m); range_add(L, R, x, i * 2 + 2, m, r); update(i); } T range_sum(int L, int R, int i, int l, int r){ if (r <= L || R <= l){ return 0; } else if (L <= l && r <= R){ return sum[i]; } push(i); int m = (l + r) / 2; return range_sum(L, R, i * 2 + 1, l, m) + range_sum(L, R, i * 2 + 2, m, r); } void range_chmin(int L, int R, T x){ range_chmin(L, R, x, 0, 0, N); } void range_chmax(int L, int R, T x){ range_chmax(L, R, x, 0, 0, N); } void range_add(int L, int R, T x){ range_add(L, R, x, 0, 0, N); } T range_sum(int L, int R){ return range_sum(L, R, 0, 0, N); } }; struct PartiallyPersistentUnionFind { vector par, last; vector > history; PartiallyPersistentUnionFind(ll n) : par(n, -1), last(n, -1), history(n) { for (auto &vec : history) vec.emplace_back(-1, -1); } void init(ll n) { par.assign(n, -1); last.assign(n, -1); history.assign(n, vector

()); for (auto &vec : history) vec.emplace_back(-1, -1); } ll root(ll t, ll x) { if (last[x] == -1 || t < last[x]) return x; return root(t, par[x]); } bool issame(ll t, ll x, ll y) { return root(t, x) == root(t, y); } bool merge(ll t, ll x, ll y) { x = root(t, x); y = root(t, y); if (x == y) return false; if (par[x] > par[y]) swap(x, y); // merge technique par[x] += par[y]; par[y] = x; last[y] = t; history[x].emplace_back(t, par[x]); return true; } ll size(ll t, ll x) { x = root(t, x); return -prev(lower_bound(history[x].begin(), history[x].end(), make_pair(t, 0LL)))->second; } }; // matrix template struct Matrix { vector > val; Matrix(int n = 1, int m = 1, T v = 0) : val(n, vector(m, v)) {} void init(int n, int m, T v = 0) {val.assign(n, vector(m, v));} void resize(int n, int m) { val.resize(n); for (int i = 0; i < n; ++i) val[i].resize(m); } Matrix& operator = (const Matrix &A) { val = A.val; return *this; } size_t size() const {return val.size();} vector& operator [] (int i) {return val[i];} const vector& operator [] (int i) const {return val[i];} friend ostream& operator << (ostream& s, const Matrix& M) { s << endl; for (int i = 0; i < (int)M.size(); ++i) s << M[i] << endl; return s; } }; template Matrix operator * (const Matrix &A, const Matrix &B) { Matrix R(A.size(), B[0].size()); for (int i = 0; i < A.size(); ++i) for (int j = 0; j < B[0].size(); ++j) for (int k = 0; k < B.size(); ++k) R[i][j] += A[i][k] * B[k][j]; return R; } template Matrix pow(const Matrix &A, long long n) { Matrix R(A.size(), A.size()); auto B = A; for (int i = 0; i < A.size(); ++i) R[i][i] = 1; while (n > 0) { if (n & 1) R = R * B; B = B * B; n >>= 1; } return R; } template vector operator * (const Matrix &A, const vector &B) { vector v(A.size()); for (int i = 0; i < A.size(); ++i) for (int k = 0; k < B.size(); ++k) v[i] += A[i][k] * B[k]; return v; } template Matrix operator + (const Matrix &A, const Matrix &B) { Matrix R(A.size(), A[0].size()); for (int i = 0; i < A.size(); ++i) for (int j = 0; j < A[0].size(); ++j) R[i][j] = A[i][j] + B[i][j]; return R; } template Matrix operator - (const Matrix &A, const Matrix &B) { Matrix R(A.size(), A[0].size()); for (int i = 0; i < A.size(); ++i) for (int j = 0; j < A[0].size(); ++j) R[i][j] = A[i][j] - B[i][j]; return R; } const int MAX_ROW = 510; // to be set appropriately const int MAX_COL = 510; // to be set appropriately struct BitMatrix { int H, W; bitset val[MAX_ROW]; BitMatrix(int m = 1, int n = 1) : H(m), W(n) {} inline bitset& operator [] (int i) {return val[i];} }; int GaussJordan(BitMatrix &A, bool is_extended = false) { int rank = 0; for (int col = 0; col < A.W; ++col) { if (is_extended && col == A.W - 1) break; int pivot = -1; for (int row = rank; row < A.H; ++row) { if (A[row][col]) { pivot = row; break; } } if (pivot == -1) continue; swap(A[pivot], A[rank]); for (int row = 0; row < A.H; ++row) { if (row != rank && A[row][col]) A[row] ^= A[rank]; } ++rank; } return rank; } int linear_equation(BitMatrix A, vector b, vector &res) { int m = A.H, n = A.W; BitMatrix M(m, n + 1); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) M[i][j] = A[i][j]; M[i][n] = b[i]; } int rank = GaussJordan(M, true); // check if it has no solution for (int row = rank; row < m; ++row) if (M[row][n]) return -1; // answer res.assign(n, 0); for (int i = 0; i < rank; ++i) res[i] = M[i][n]; return rank; } // struct edge{ // ll to; // ll cost; // }; // using graph = vector >; // const ll MAX_V=200200; // graph G(MAX_V); // vl d(MAX_V); // void dijkstra(ll n,ll s) { // minpq

q; // rep(i,n)d[i]=INF; // d[s]= 0LL; // q.push({0LL, s}); // while (!q.empty()) { // auto p = q.top(); // q.pop(); // ll cur = p.second; // //d[cur]が二度以上更新されている場合に、初期のものをskipする // //これがないと一つの頂点につき高々一回更新されるという前提が破滅 // if(d[cur] d[cur]+e.cost) { // d[e.to]=d[cur]+e.cost; // q.push({d[e.to], e.to}); // } // } // } // } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(12); /*--------------------------------*/ ll n,m;cin>>n>>m; ll K;cin>>K; vl p(m),q(m),c(m); rep(i,m)cin>>p[i]>>q[i]>>c[i],p[i]--,q[i]--; // vvm dp(n,vm(k+1)); auto dp=make_vec(n,300,K+1); rep(i,300)dp[0][i][0]=1; rep(i,n-1){ rep(j,m){ rep(k,K+1){ if(k>=c[j])dp[i+1][q[j]][k]+=dp[i][p[j]][k-c[j]]; } } } // rep(i,n){ // rep(j,3){ // rep(k,3){ // cout<