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.math.*;
import java.util.*;
 
public class Main {
	static final long MOD = 1000000009L;
	static long[][] hashes;
	static long T;
	static long[] pows;
	
	static int ans;
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		
		int N = sc.ni();
		int M = sc.ni();
		int K = sc.ni();
		ArrayList<Edge>[] graph = new ArrayList[N];
		for (int i = 0; i < N; i++)
			graph[i] = new ArrayList<Edge>();
		for (int i = 0; i < M; i++) {
			int u = sc.ni()-1;
			int v = sc.ni()-1;
			int w = sc.ni();
			graph[u].add(new Edge(v,w));
		}
		for (int i = 0; i < N; i++)
			Collections.sort(graph[i]);
		hashes = new long[K][K];
		pows = new long[N];
		pows[0] = 1L;
		for (int i = 1; i < N; i++) {
			pows[i] = (pows[i-1]*2)%MOD;
		}
		T = (pows[N-1]*2-1)%MOD;
		
		for (int i = 0; i < N; i++) {
			int k = graph[i].size()-1;
			if (graph[i].isEmpty())continue;
			for (int j = 0; j <= k; j++) {
				hashes[k][j] += pows[graph[i].get(j).to];
				hashes[k][j] %= MOD;
			}
		}
		
		ans = 0;
		//iterate over all K! possibilities
		ArrayDeque<Current> q = new ArrayDeque<Current>();
		q.add(new Current(0L,0));
		
		while (!q.isEmpty()) {
			Current c = q.pollFirst();
			if (c.i==K) {
				if (c.h==T)
					ans++;
			} else {
				for (int k = 0; k <= c.i; k++) {
					q.add(new Current((c.h+hashes[c.i][k])%MOD,c.i+1));
				}
			}
		}
		pw.println(ans);
		pw.close();
	}
	
	static class Current {
		long h;
		int i;
		
		public Current(long h, int i) {
			this.h=h;
			this.i=i;
		}
	}
	
	static class Edge implements Comparable<Edge> {
		int to;
		int weight;
		public Edge(int t, int w) {
			to = t;
			weight = w;
		}
		
		public int compareTo(Edge e) {
			return (weight-e.weight);
		}
	}
	
    static class FastScanner { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastScanner() { 
            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 ni() { 
            return Integer.parseInt(next()); 
        }
  
        long nl() { 
            return Long.parseLong(next()); 
        } 
  
        double nd() { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() {
            String str = ""; 
            try { 
                str = br.readLine(); 
            } catch (IOException e) {
                e.printStackTrace(); 
            } 
            return str;
        }
    }
}