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;
using i64 = long long;
using f64 = double;
using f80 = long double;
using pii = pair<int, int>;
using ptx = pair<f64, f64>;
template <int MOD>
class Num {
 private:
  int expow(long base, int e) const {
    long long ans = 1;
    for (; e > 0; e /= 2) {
      if (e % 2) ans = ans * base % MOD;
      base = base * base % MOD;
    }
    return ans;
  }

 public:
  int val;
  Num(long long _val) {
    val = _val % MOD;
    val = val < 0 ? val + MOD : val;
  }
  Num() : val(0) {}
  inline bool operator==(const Num &arg) const { return val == arg.val; }
  inline Num operator+(const Num &arg) const {
    Num res;
    res.val = val + arg.val;
    res.val = res.val >= MOD ? res.val - MOD : res.val;
    return res;
  }
  inline Num operator-(const Num &arg) const {
    Num res;
    res.val = val - arg.val;
    res.val = res.val < 0 ? res.val + MOD : res.val;
    return res;
  }
  inline Num operator-() const {
    Num res;
    res.val = MOD - res.val;
    res.val = res.val == MOD ? 0 : res.val;
    return res;
  }
  inline Num operator^(const int &arg) const { return Num(expow(val, arg)); }
  inline Num operator*(const Num &arg) const {
    return Num(1LL * val * arg.val);
  }
  inline Num operator/(const Num &arg) const {
    return Num(1LL * val * expow(arg.val, MOD - 2));
  }
  inline void operator+=(const Num &arg) { (*this) = (*this) + arg; }
  inline void operator-=(const Num &arg) { (*this) = (*this) - arg; }
  inline void operator*=(const Num &arg) { (*this) = (*this) * arg; }
  inline void operator/=(const Num &arg) { (*this) = (*this) / arg; }
  inline void operator^=(const long long &arg) { val = expow(val, arg); }
};
template <int MOD>
ostream &operator<<(ostream &fo, const Num<MOD> &c) {
  fo << c.val;
  return fo;
}
template <int MOD>
istream &operator>>(istream &fi, Num<MOD> &c) {
  fi >> c.val;
  c = Num<MOD>(c.val);
  return fi;
}
const int MOD1 = 1e9 + 7, MOD2 = (1LL << 31) - 1;
const int N = 2e5 + 5, K = 11;
using hsh = pair<Num<MOD1>, Num<MOD2>>;
hsh hash_tab[K][K], pwn[N];
vector<pii> ig[N];
vector<int> g[N];
vector<int> prm;
int n, m, k, ant;
hsh good;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n >> m >> k;
  for (int i = 0; i < m; ++i) {
    int u, v, c;
    cin >> u >> v >> c;
    ig[u].emplace_back(v, c);
  }
  for (int i = 1; i <= n; ++i) {
    sort(begin(ig[i]), end(ig[i]), [&](const pii &a, const pii &b) -> bool {
      return a.second < b.second;
    });
    for (auto &t : ig[i]) g[i].push_back(t.first);
  }
  pwn[0] = {1, 1};
  for (int i = 1; i < N; ++i) {
    pwn[i].first = pwn[i - 1].first * (n + 5);
    pwn[i].second = pwn[i - 1].second * (n + 5);
  }
  for (int i = 1; i <= n; ++i) {
    good.first += pwn[i].first;
    good.second += pwn[i].second;
    for (int j = 0; j < g[i].size(); ++j) {
      hash_tab[g[i].size()][j + 1].first += pwn[g[i][j]].first;
      hash_tab[g[i].size()][j + 1].second += pwn[g[i][j]].second;
    }
  }
  function<void(int, hsh)> bkt = [&](int pos, hsh sofar) {
    if (pos == k + 1) {
      ant += int(sofar == good);
      return;
    }
    for (int i = 1; i <= pos; ++i)
      bkt(pos + 1, hsh(sofar.first + hash_tab[pos][i].first,
                       sofar.second + hash_tab[pos][i].second));
  };
  bkt(1, hsh(0, 0));
  cout << ant << endl;
  return 0;
}
