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.util.*;
import java.util.stream.*;
import java.io.*;
import java.math.*;

public class Main { 
    
    static boolean FROM_FILE = false;
    
    static boolean LOCAL = System.getProperty("ONLINE_JUDGE") == null;

    static class FastReader { 
        BufferedReader br; 
        StringTokenizer st; 
        public FastReader() { 
            if (FROM_FILE) {
                try {
                    br = new BufferedReader(new FileReader("input.txt")); 
                } catch (IOException error) {
                }   
            } else {
                br = new BufferedReader(new InputStreamReader(System.in));    
            }
        }
        String next() { 
            while (st == null || !st.hasMoreElements()) { 
                try { 
                    st = new StringTokenizer(br.readLine()); 
                } catch (IOException  e) { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        }
        int nextInt() { 
            return Integer.parseInt(next()); 
        }
        long nextLong() { 
            return Long.parseLong(next()); 
        }
  
        double nextDouble() { 
            return Double.parseDouble(next()); 
        } 
        String nextLine() { 
            String str = ""; 
            try { 
                str = br.readLine(); 
            } catch (IOException e) { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }
    static int max(int... nums) {
        int res = Integer.MIN_VALUE;
        for (int num: nums) res = Math.max(res, num);
        return res;
    }
    static int min(int... nums) {
        int res = Integer.MAX_VALUE;
        for (int num: nums) res = Math.min(res, num);
        return res;
    }
    static long max(long... nums) {
        long res = Long.MIN_VALUE;
        for (long num: nums) res = Math.max(res, num);
        return res;
    }
    static long min(long... nums) {
        long res = Long.MAX_VALUE;
        for (long num: nums) res = Math.min(res, num);
        return res;
    }
    
    static FastReader fr = new FastReader();
    static PrintWriter out;
    
    public static void main(String[] args) { 
        if (FROM_FILE) {
            try {
                out = new PrintWriter(new FileWriter("output.txt"));
            } catch (IOException error) {
                
            }
        } else {
            out = new PrintWriter(new OutputStreamWriter(System.out));
        }
        new Main().run();
        out.flush();
        out.close();
    } 
    
    class Graph {
        int n, k;
        ArrayList<int[]>[] adj;
        Graph(int n, int k) { 
            this.n = n; this.k = k;
            adj = new ArrayList[n + 1];
            for (int i = 1; i <= n; i += 1) adj[i] = new ArrayList<int[]>();
        }
        void addEdge(int u, int v, int w) {
            adj[u].add(new int[] {v, w});
        }
        void sortEdge() {
            for (int i = 1; i <= n; i += 1) {
                Collections.sort(adj[i], (e1, e2) -> Integer.compare(e1[1], e2[1]));
            }
        }
        ArrayList<Integer>[] degreeCache;
        void setDegreeCache() {
            degreeCache = new ArrayList[k + 1];
            for (int i = 1; i <= k; i += 1) degreeCache[i] = new ArrayList<Integer>();
            for (int i = 1; i <= n; i += 1) degreeCache[adj[i].size()].add(i);
        }
    }
    Graph g;
    int[] hashKey;
    long[][] cache;
    long target, res;
    
    void dfs(int idx, long val) {
        if (idx > g.k) {
            if (val == target) res += 1;
            return;
        }
        for (int c = 1; c <= idx; c += 1) {
            dfs(idx + 1, val + cache[idx][c]);
        }
    }
    
    
    void run() {
        int n = fr.nextInt(), m = fr.nextInt(), k = fr.nextInt();
        g = new Graph(n, k);
        for (int i = 0; i < m; i += 1) {
            int u = fr.nextInt(), v = fr.nextInt(), w = fr.nextInt();
            g.addEdge(u, v, w);
        }
        g.sortEdge();
        g.setDegreeCache();
        hashKey = new int[n + 1]; cache = new long[k + 1][k + 1];
        target = 0;
        for (int i = 1; i <= n; i += 1) {
            hashKey[i] = (int)(10000000 * Math.random());
            target += hashKey[i];
        }
        // out.println(Arrays.toString(hashKey));
        for (int idx = 1; idx <= k; idx += 1) {
            for (int c = 1; c <= idx; c += 1) {
                long item = 0;
                for (int u : g.degreeCache[idx]) {
                    int v = g.adj[u].get(c - 1)[0];
                    item += hashKey[v];
                }
                cache[idx][c] = item;
                // out.println(idx + " " + c + " " + item);
            }
        }
        res = 0;
        dfs(1, 0);
        out.println(res);
    }
}