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.

import java.io.*;
import java.util.*;


/**
 * Created by Katushka on 11.03.2020.
 */
public class C {

    public static final Comparator<int[]> COMPARATOR = Comparator.comparingInt(o -> o[0]);

    static int[] readArray(int size, InputReader in) {
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = in.nextInt();
        }
        return a;
    }

    static long[] readLongArray(int size, InputReader in) {
        long[] a = new long[size];
        for (int i = 0; i < size; i++) {
            a[i] = in.nextLong();
        }
        return a;
    }

    static HashMap<Integer, Long> hash = new HashMap<>();
    static void fillHashes(int n) {
        for (int i = 1; i <= n; i++) {
            hash.put(i, (long) (Math.random() * 1000000));
        }
    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();

        fillHashes(n);

        Set<Integer>[][] cc = new Set[k + 1][k + 1];
        long[][] hashes = new long[k + 1][k + 1];
        for (long[] hash : hashes) {
            Arrays.fill(hash, 1);
        }
        boolean[][] blocked = new boolean[k + 1][k + 1];

        List<int[]>[] edges = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            edges[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            int w = in.nextInt();
            edges[u].add(new int[]{w, v});
        }

        boolean[] usedC = new boolean[k + 1];
        long sum = 1;
        for (int i = 1; i <= n; i++) {
            sum = sum * hash.get(i) % 1000000009;
        }

        for (int i = 1; i < edges.length; i++) {
            List<int[]> edge = edges[i];
            edge.sort(COMPARATOR);

            int t = 1;
            int kk = edge.size();
            usedC[kk] = true;
            for (int[] entry : edge) {
                if (!blocked[kk][t]) {
                    if (cc[kk][t] == null) {
                        cc[kk][t] = new HashSet<>();
                    }
                    if (cc[kk][t].contains(entry[1])) {
                        blocked[kk][t] = true;
                    } else {
                        cc[kk][t].add(entry[1]);
                        hashes[kk][t] = hashes[kk][t] * hash.get(entry[1]) % 1000000009;
                    }
                }
                t++;
            }
        }


        long res = 1;
        for (int i1 = 1; i1 < usedC.length; i1++) {
            if (!usedC[i1]) {
                res *= i1;
            }
        }

        out.println(res * solve(1, cc, hashes, blocked, new int[k + 1], n, k, usedC, sum, 1, n));
        out.close();
    }

    private static long solve(int i, Set<Integer>[][] cc, long[][] hashes, boolean[][] blocked, int[] c, int usedCnt,
                              int k, boolean[] usedC, long sum, long hash, int n) {
        if (i == k + 1) {
            if (usedCnt == 0 && hash == sum /*&& checkUsed(cc, c, usedC, n)*/) {
                return 1;
            } else {
                return 0;
            }
        }

        long res = 0;

        if (!usedC[i]) {
            return solve(i + 1, cc, hashes, blocked, c, usedCnt, k, usedC, sum, hash, n);
        }

        if (usedCnt == 0) {
            return 0;
        }

        for (int j = 1; j <= i; j++) {
            if (!blocked[i][j] && cc[i][j] != null) {
                int newUsed = cc[i][j].size();

                if (usedCnt - newUsed < 0) {
                    continue;
                }
                c[i] = j;
                usedCnt -= newUsed;
                res += solve(i + 1, cc, hashes, blocked, c, usedCnt, k, usedC, sum, hash * hashes[i][j] % 1000000009, n);
                c[i] = 0;

                usedCnt += newUsed;
            }
        }
        return res;
    }

    private static boolean checkUsed(Set<Integer>[][] cc, int[] c, boolean[] usedC, int n) {
        boolean[] used = new boolean[n + 1];
        for (int j = 1; j < c.length; j++) {
            if (!usedC[j]) {
                continue;
            }
            for (Integer v : cc[j][c[j]]) {
                if (used[v]) {
                    return false;
                }
                used[v] = true;
            }
        }
        return true;
    }

    private static long calcResult(int[] c) {
        long res = 1;
        for (int i1 = 1; i1 < c.length; i1++) {
            if (c[i1] == 0) {
                res *= i1;
            }
        }
        return res;
    }


    private static void outputArray(int[] ans, PrintWriter out) {
        StringBuilder str = new StringBuilder();
        for (int an : ans) {
            str.append(an).append(" ");
        }
        out.println(str);
    }

    private static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextString() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public char nextChar() {
            return next().charAt(0);
        }
    }
}