B"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, ldots,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, ldots,c_k) such that The first line contains three integers n , m and k ( 2 <= n <= 2 cdot 10^5 , 2 <= m <= min(2 cdot 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 ne 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. Print one integer: the number of tuples. 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. For the third example, there's only one tuple: (1,2,2,2) . The out-degree of vertex u means the number of edges outgoing from u . "...