#include <bits/stdc++.h>
using namespace std;
int na[9][9] = {0};
long long ba[9][9] = {0};
long long ans = 0;
long long fun(long long x, long long y) { return x * (x + 1) / 2 + y; }
void fun2(int i, int k, long long store) {
  if (i >= k) {
    ans++;
    return;
  }
  for (int j = 0; j <= i; j++) {
    if (na[i][j] || ba[i][j] & store)
      continue;
    else {
      fun2(i + 1, k, store | (1LL << fun(i, j)));
    }
  }
}
int main() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<pair<int, int>> out[n], in[n];
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    out[a].push_back({c, b});
  }
  for (int i = 0; i < n; i++) {
    sort(out[i].begin(), out[i].end());
    for (int j = 0; j < out[i].size(); j++) {
      int b = out[i][j].second;
      in[b].push_back({(int)out[i].size() - 1, j});
    }
  }
  for (int i = 0; i < n; i++) {
    sort(in[i].begin(), in[i].end());
    vector<pair<int, int>> p;
    long long store = 0;
    for (auto u : in[i]) {
      if (p.size() && p[p.size() - 1] == u)
        na[u.first][u.second] = 1;
      else {
        p.push_back(u);
      }
    }
    for (auto u : in[i]) {
      store |= (1LL << fun(u.first, u.second));
      ba[u.first][u.second] |= store;
    }
  }
  fun2(0, k, 0LL);
  cout << ans;
}
