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.*;

public class B {
	public static void main (String[] args) { new B(); }

	int n, m, k, res = 0;
	BitSet[][] adds;
	int[][] idx;
	int[] add;
	boolean[][] conflict;
	
	BitSet cur;
	
	public B() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");

		n = fs.nextInt();
		m = fs.nextInt();
		k = fs.nextInt();
		
		int[] deg = new int[n];
		int[][] edges = new int[m][3];
		for(int i = 0; i < m; i++) {
			int u = fs.nextInt()-1, v = fs.nextInt()-1;
			int we = fs.nextInt();
			deg[u]++;
			edges[i] = new int[] {u, v, we};
		}
		
		Arrays.sort(edges, (x, y) -> Integer.compare(x[2], y[2]));
		int[][] adj = new int[n][];
		for(int i = 0; i < n; i++) {
			adj[i] = new int[deg[i]];
			deg[i] = 0;
		}
		
		for(int i = 0; i < m; i++) {
			int u = edges[i][0], v = edges[i][1];
			adj[u][deg[u]++] = v;
		}
		
		adds = new BitSet[k + 1][];
		idx = new int[k + 1][k + 1];
		int curIdx = 0;
		for(int i = 1; i <= k; i++) {
			adds[i] = new BitSet[i];
			
			for(int j = 0; j < i; j++) {
				idx[i][j] = curIdx++;
				adds[i][j] = new BitSet(n);
			}
		}
		for(int i = 0; i < n; i++) {
			int degree = adj[i].length;
			for(int j = 0; j < degree; j++) {
				int to = adj[i][j];
				adds[degree][j].flip(to);
			}
		}
		
		conflict = new boolean[curIdx][curIdx];
		add = new int[curIdx];
		for(int i = 1; i <= k; i++) {
			for(int j = 0; j < i; j++) {
				int id1 = idx[i][j];
				add[id1] = adds[i][j].bitCount();
				
				for(int ii = i+1; ii <= k; ii++) {
					for(int jj = 0; jj < ii; jj++) {
						int id2 = idx[ii][jj];
						
						int cnt = adds[i][j].andCount(adds[ii][jj]);
						if(cnt > 0) {
							conflict[id1][id2] = conflict[id2][id1] = true;
						}
					}
				}
			}
		}
		
		rec(0, new int[k], 0);
		out.println(res);
		
		out.close();
	}
	
	void rec(int idx, int[] ids, int sum) {
		if(idx == k) {
			if(sum == n) {
				res++;
			}
			return;
		}
		for(int i = 0; i <= idx; i++) {
			int id = this.idx[idx + 1][i];
			boolean bad = false;
			for(int j = 0; j < idx; j++) {
				if(conflict[id][ this.idx[j + 1][ids[j]] ]) {
					bad = true;
					break;
				}
			}
			if(bad) continue;
			
			ids[idx] = i;
			rec(idx+1, ids, sum+add[id]);
			ids[idx] = 0;
		}
	}
	
	class BitSet {
		long[] a;
		int n, size;
		BitSet(int x) {
			n = x;
			size = n/60 + (n % 60 > 0 ? 1 : 0);
			a = new long[size];
		}
		void flip(int idx) {
			int block = idx/60;
			idx -= block*60;
			a[block] ^= (1L << idx);
		}
		int bitCount() {
			int res = 0;
			for(int i = 0; i < size; i++)
				res += Long.bitCount(a[i]);
			return res;
		}
		int andCount(BitSet b) {
			int res = 0;
			for(int i = 0; i < a.length; i++)
				res += Long.bitCount(a[i] & b.a[i]);
			return res;
		}
		void xor(BitSet b) {
			for(int i = 0; i < a.length; i++) {
				a[i] ^= b.a[i];
			}
		}
	}

	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			}
			catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}