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;
const int N = 2e5 + 5;
const unsigned long long p1 = 13, p2 = 17, mod1 = 998244353, mod2 = 1e9 + 7;
map<unsigned long long, int> m1, m2;
vector<unsigned long long> V1[10], V2[10];
struct node {
  int x, y;
  node(int x = 0, int y = 0) : x(x), y(y) {}
};
bool cmp(const node &a, const node &b) { return a.y < b.y; }
vector<node> G[N];
vector<int> E[10][10];
unsigned long long pw1[N], pw2[N], h1[N], h2[N], n1, n2, c1[N], c2[N];
bool vis[N];
int deg[N], sta[N], nxt[N], prv[N], cnt[N], mid;
unsigned long long ksm(unsigned long long a, unsigned long long b,
                       unsigned long long mod) {
  unsigned long long ans = 1;
  for (; b; b >>= 1, a = a * a % mod)
    if (b & 1) ans = ans * a % mod;
  return ans;
}
void dfs1(int i, unsigned long long w1, unsigned long long w2) {
  if (i == mid) {
    ++m1[w1];
    ++m2[w2];
    return;
  }
  i = prv[i];
  int siz = V1[i].size();
  for (int j = 0; j < siz; ++j)
    dfs1(i, (w1 + V1[i][j]) % mod1, (w2 + V2[i][j]) % mod2);
}
unsigned long long ans;
void dfs2(int i, unsigned long long w1, unsigned long long w2) {
  if (i == prv[mid]) {
    unsigned long long sub1 = ((n1 - w1 + (mod1 << 5)) % mod1 + mod1) % mod1;
    unsigned long long sub2 = ((n2 - w2 + (mod2 << 5)) % mod2 + mod2) % mod2;
    ans += min(m1[sub1], m2[sub2]);
    return;
  }
  i = nxt[i];
  int siz = V1[i].size();
  for (int j = 0; j < siz; ++j)
    dfs2(i, (w1 + V1[i][j]) % mod1, (w2 + V2[i][j]) % mod2);
}
int main() {
  memset(deg, 0, sizeof deg);
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  pw1[1] = pw2[1] = 1;
  for (int i = 2; i <= n; ++i) {
    pw1[i] = pw1[i - 1] * p1 % mod1;
    pw2[i] = pw2[i - 1] * p2 % mod2;
  }
  h1[1] = h2[1] = c1[1] = c2[1] = 1;
  for (int i = 2; i <= n; ++i) {
    c1[i] = i * pw1[i] % mod1;
    c2[i] = i * pw2[i] % mod2;
    h1[i] = (h1[i - 1] + c1[i]) % mod1;
    h2[i] = (h2[i - 1] + c2[i]) % mod2;
  }
  n1 = h1[n], n2 = h2[n];
  for (int i = 1; i <= m; ++i) {
    int x, y, w;
    scanf("%d%d%d", &x, &y, &w);
    G[x].push_back(node(y, w));
    ++deg[x];
  }
  for (int i = 1; i <= n; ++i) ++cnt[deg[i]];
  int top = 0;
  for (int i = 1; i <= k; ++i)
    if (cnt[i]) sta[++top] = i;
  mid = sta[top / 2 + 1];
  nxt[0] = sta[1];
  prv[10] = sta[top];
  for (int i = 1; i <= top; ++i)
    nxt[sta[i]] = i == top ? 10 : sta[i + 1],
    prv[sta[i]] = i == 1 ? 0 : sta[i - 1];
  for (int i = 1; i <= n; ++i) {
    int id = deg[i];
    sort(G[i].begin(), G[i].end(), cmp);
    int siz = G[i].size();
    for (int j = 0; j < siz; ++j) {
      E[id][j + 1].push_back(G[i][j].x);
    }
  }
  for (int i = 1; i <= k; ++i)
    if (cnt[i])
      for (int j = 1; j <= k; ++j) {
        for (int z = 1; z <= n; ++z) vis[z] = 0;
        sort(E[i][j].begin(), E[i][j].end());
        bool flag = 1;
        int siz = E[i][j].size();
        if (!siz) continue;
        for (int z = 0; z < siz; ++z) {
          if (vis[E[i][j][z]]) {
            flag = 0;
            break;
          }
          vis[E[i][j][z]] = 1;
        }
        if (!flag) continue;
        unsigned long long w1 = 0, w2 = 0;
        for (int z = 0; z < siz; ++z) {
          w1 = (w1 + c1[E[i][j][z]]) % mod1;
          w2 = (w2 + c2[E[i][j][z]]) % mod2;
        }
        V1[i].push_back(w1);
        V2[i].push_back(w2);
      }
  ans = 0ull;
  dfs1(10, 0ull, 0ull);
  dfs2(0, 0ull, 0ull);
  for (int i = 1; i <= k; ++i)
    if (!cnt[i]) ans *= i;
  printf("%llu\n", ans);
  return 0;
}
