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>
#pragma GCC optimize("Ofast", "unroll-loops", "omit-frame-pointer", "inline")
#pragma GCC option("arch=native", "tune=native", "no-zero-upper")
#pragma GCC target("avx2")
using namespace std;
template <typename T>
void maxtt(T &t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T &t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
const long long MOD2 = (long long)1000000007 * (long long)1000000007;
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int &x, int y, int mod = 1000000007) {
  x += y;
  if (x >= mod) x -= mod;
  if (x < 0) x += mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
const int SZ = 3;
int mod[SZ];
struct mb {
  int a[SZ] = {0};
  void init(long long x) {
    for (int(i) = 0; (i) < (int)(SZ); (i)++)
      a[i] = (x % mod[i] + mod[i]) % mod[i];
  }
  mb operator+(mb &x) {
    mb res;
    res.a[0] = (a[0] + x.a[0]) % mod[0];
    res.a[1] = (long long)a[1] * x.a[1] % mod[1];
    res.a[2] = (a[2] + x.a[2]) % mod[2];
    return res;
  }
  bool operator==(const mb &o) const {
    for (int(i) = 0; (i) < (int)(SZ); (i)++)
      if (a[i] != o.a[i]) return 0;
    return 1;
  }
} all, num[(200135)], val[10][10];
vector<pair<int, int> > mp[(200135)];
int hid[(200135)], Ans;
void dfs(int i, mb x) {
  if (i == k + 1) {
    if (x == all) Ans++;
    return;
  }
  for (int(j) = 1; (j) <= (int)(i); (j)++) {
    dfs(i + 1, x + val[i][j]);
  }
}
void fmain(int tid) {
  scanf("%d%d%d", &n, &m, &k);
  for (int(i) = 1; (i) <= (int)(m); (i)++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    mp[u].push_back({w, v});
  }
  mod[0] = 1000000007;
  mod[1] = 1000000007 + 2;
  mt19937 ttrand((int)time(0));
  mod[2] = uniform_int_distribution<int>(1e8, 1e9)(ttrand);
  all.init(0);
  for (int(i) = 0; (i) < (int)(10); (i)++)
    for (int(j) = 0; (j) < (int)(10); (j)++) val[i][j].init(0);
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    hid[i] = uniform_int_distribution<int>(1, (1000000000))(ttrand);
    num[i].init(hid[i]);
    all = all + num[i];
  }
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    sort(mp[i].begin(), mp[i].end());
    int N = mp[i].size();
    for (int(j) = 0; (j) < (int)(N); (j)++) {
      val[N][j + 1] = val[N][j + 1] + num[mp[i][j].second];
    }
  }
  mb tt;
  tt.init(0);
  dfs(1, tt);
  printf("%d\n", Ans);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}
