Boboniu has a directed graph with n vertices and m edges.

The out-degree of each vertex is at most k.

Each edge has an integer weight between 1 and m. No two edges have equal weights.

Boboniu likes to walk on the graph with some specific rules, which is represented by a tuple (c_1,c_2,…,c_k). If he now stands on a vertex u with out-degree i, then he will go to the next vertex by the edge with the c_i-th (1≤ c_i≤ i) smallest weight among all edges outgoing from u.

Now Boboniu asks you to calculate the number of tuples (c_1,c_2,…,c_k) such that

  * 1≤ c_i≤ i for all i (1≤ i≤ k). 
  * Starting from any vertex u, it is possible to go back to u in finite time by walking on the graph under the described rules. 

Input

The first line contains three integers n, m and k (2≤ n≤ 2⋅ 10^5, 2≤ m≤ min(2⋅ 10^5,n(n-1) ), 1≤ k≤ 9).

Each of the next m lines contains three integers u, v and w (1≤ u,v≤ n,u≠ v,1≤ w≤ m), denoting an edge from u to v with weight w. It is guaranteed that there are no self-loops or multiple edges and each vertex has at least one edge starting from itself.

It is guaranteed that the out-degree of each vertex is at most k and no two edges have equal weight.

Output

Print one integer: the number of tuples.

Examples

Input


4 6 3
4 2 1
1 2 2
2 4 3
4 1 4
4 3 5
3 1 6


Output


2


Input


5 5 1
1 4 1
5 1 2
2 5 3
4 3 4
3 2 5


Output


1


Input


6 13 4
3 5 1
2 5 2
6 3 3
1 4 4
2 6 5
5 3 6
4 1 7
4 3 8
5 2 9
4 2 10
2 1 11
6 1 12
4 6 13


Output


1

Note

For the first example, there are two tuples: (1,1,3) and (1,2,3). The blue edges in the picture denote the c_i-th smallest edges for each vertex, which Boboniu chooses to go through.

<image>

For the third example, there's only one tuple: (1,2,2,2).

<image>

The out-degree of vertex u means the number of edges outgoing from u.
#include <bits/stdc++.h>
using namespace std;
template <class T>
bool ckmin(T& a, const T& b) {
  return a > b ? a = b, true : false;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, true : false;
}
template <typename T>
struct IsC {
  template <typename C>
  static char test(typename C::const_iterator*);
  template <typename C>
  static int test(...);
  static const bool value = sizeof(test<T>(0)) == sizeof(char);
};
template <>
struct IsC<string> {
  static const bool value = false;
};
template <typename C>
typename enable_if<IsC<C>::value, ostream&>::type operator<<(ostream&,
                                                             const C&);
template <typename T1, typename T2>
ostream& operator<<(ostream&, const pair<T1, T2>&);
template <typename... T>
using TS = tuple_size<tuple<T...>>;
template <size_t idx, typename... T>
typename enable_if<TS<T...>::value == idx + 1, ostream&>::type operator<<(
    ostream& o, const tuple<T...>& t) {
  return o << ", " << get<idx>(t) << ')';
}
template <size_t idx, typename... T>
typename enable_if<0 < idx && idx + 1 < TS<T...>::value, ostream&>::type
operator<<(ostream& o, const tuple<T...>& t) {
  return operator<<<idx + 1>(o << ", " << get<idx>(t), t);
}
template <size_t idx = 0, typename... T>
typename enable_if<1 < TS<T...>::value && !idx, ostream&>::type operator<<(
    ostream& o, const tuple<T...>& t) {
  return operator<<<idx + 1>(o << '(' << get<idx>(t), t);
}
template <typename T>
ostream& operator<<(ostream& o, const tuple<T>& t) {
  return o << get<0>(t);
}
template <typename T1, typename T2>
ostream& operator<<(ostream& o, const pair<T1, T2>& p) {
  return o << make_tuple(p.first, p.second);
}
template <typename C>
typename enable_if<IsC<C>::value, ostream&>::type operator<<(ostream& o,
                                                             const C& c) {
  o << '[';
  for (auto it = c.cbegin(); it != c.cend(); ++it)
    o << *it << (next(it) != c.cend() ? ", " : "");
  return o << ']';
}
template <typename T>
void tprint(vector<vector<T>>& v, size_t width = 0, ostream& o = cerr) {
  if (!0) return;
  for (const auto& vv : v) {
    for (const auto& i : vv) o << setw(width) << i;
    o << '\n';
  }
}
struct mod {
  static const long long p = 1e9 + 7;
  long long val;
  mod() : val(0) {}
  mod(long long val) : val(val % p) {
    if (this->val < 0) this->val += p;
  }
  mod& operator+=(const mod& o) {
    val = (val + o.val) % p;
    return *this;
  }
  mod& operator-=(const mod& o) {
    val = (val - o.val + p) % p;
    return *this;
  }
  mod& operator*=(const mod& o) {
    val = val * o.val % p;
    return *this;
  }
  mod& operator/=(mod o) { return (*this) *= pow(o, p - 2); }
  mod& operator++() { return (*this) += 1; }
  mod operator++(int) { return ++(*this) - 1; }
  mod& operator--() { return (*this) -= 1; }
  mod operator--(int) { return --(*this) + 1; }
  mod friend operator+(mod a, const mod& b) { return a += b; }
  mod friend operator-(mod a, const mod& b) { return a -= b; }
  mod friend operator*(mod a, const mod& b) { return a *= b; }
  mod friend operator/(mod a, const mod& b) { return a /= b; }
  static mod pow(mod a, mod b) {
    mod res = 1;
    for (; b.val; b.val >>= 1, a = a * a)
      if (b.val & 1) res = res * a;
    return res;
  }
  friend istream& operator>>(istream& i, mod& m) {
    i >> m.val;
    m.val %= mod::p;
    if (m.val < 0) m.val += mod::p;
    return i;
  }
  friend ostream& operator<<(ostream& o, const mod& m) { return o << m.val; }
};
mt19937 gen((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<long long> dst(0, mod::p - 1);
int main() {
  ios_base::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  vector<tuple<int, int, int>> es;
  vector<int> ks(n + 1);
  vector<int> in(n + 1);
  for (auto i = (0); (i) < ((m)); ++(i)) {
    int u, v, w;
    cin >> u >> v >> w;
    es.emplace_back(u, w, v);
    ++in[v];
    ++ks[u];
  }
  for (auto i = (1); (i) < (n + 1); ++(i)) {
    if (in[i] == 0) {
      cout << 0 << '\n';
      return 0;
    }
  }
  int up = 1;
  vector<vector<long long>> r(2, vector<long long>(n + 1));
  for (auto i = (0); (i) < ((2)); ++(i))
    generate((r[i]).begin(), (r[i]).end(), []() { return dst(gen); });
  if (0)
    std::cerr << " ["
              << "r[0], r[1]"
                 ": "
              << make_tuple(r[0], r[1]) << "] " << '\n';
  vector<mod> c(2, 1);
  for (auto i = (1); (i) < (n + 1); ++(i))
    for (auto j = (0); (j) < ((up)); ++(j)) c[j] *= r[j][i];
  sort((es).begin(), (es).end());
  vector<vector<vector<mod>>> S(
      2, vector<vector<mod>>(k + 1, vector<mod>(k + 1, 1)));
  int last = 0, l = 0;
  for (auto [u, w, v] : es) {
    if (last != u) {
      last = u;
      l = 0;
    }
    ++l;
    for (auto i = (0); (i) < ((up)); ++(i)) S[i][ks[u]][l] *= r[i][v];
  }
  if (0)
    std::cerr << " ["
              << "S"
                 ": "
              << make_tuple(S) << "] " << '\n';
  vector<int> num(k + 1, 1);
  int cnt = 0;
  do {
    vector<mod> cc(2, 1);
    for (auto i = (1); (i) < (k + 1); ++(i)) {
      for (auto j = (0); (j) < ((up)); ++(j)) {
        cc[j] *= S[j][i][num[i]];
      }
    }
    if (0)
      std::cerr << " ["
                << "c, cc"
                   ": "
                << make_tuple(c, cc) << "] " << '\n';
    cnt += c[0].val == cc[0].val && c[1].val == cc[1].val;
    for (int i = k; i; --i) {
      if (++num[i] == i + 1) {
        if (i > 1) num[i] = 1;
      } else {
        break;
      }
    }
  } while (num[1] == 1);
  cout << cnt << '\n';
  return 0;
}
