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.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.StringTokenizer;

public class TaskE {
    static FastIO io = new FastIO("in.txt");

    static int N, M, K;
    static ArrayList<Integer> g[];
    static int[] ods;
    static long ans = 0;
    static Edge[] ES;
    static ArrayList<Integer>[][] ks;
    static HashCode hs[][];
    static HashCode TH;

    static class HashCode {
        static long[] MODS = {998244353L, 1000000007L, 1000000007L};
        long h1, h2, h3;
        public HashCode(long h1, long h2, long h3){
            this.h1 = h1;
            this.h2 = h2;
            this.h3 = h3;
        }
        public HashCode(ArrayList<Integer> as){
            for(long a : as){
                h1 = (h1 + a) % MODS[0];
                h2 = (h2 + (a * a) % MODS[1]) % MODS[1];
                h3 = (h3 + (a * a) % MODS[2] * a) % MODS[2];
            }
        }

        public HashCode add(HashCode code){
            long nh1 = (h1 + code.h1) % MODS[0];
            long nh2 = (h2 + code.h2) % MODS[1];
            long nh3 = (h3 + code.h3) % MODS[2];
            return new HashCode(nh1, nh2, nh3);
        }

        @Override
        public boolean equals(Object obj) {
            HashCode ho = (HashCode) obj;
            return ho.h1 == h1 && ho.h2 == h2 && ho.h3 == h3;
        }
    }

    static void dfs(int od, HashCode h){
        if(od > K){
            if(h.equals(TH)) ans++;
            return;
        }
        for(int i=1; i<=od; i++){
            dfs(od + 1, h.add(hs[od][i]));
        }
    }

    static long solve(){
        ks = new ArrayList[K+1][K+1];
        hs = new HashCode[K+1][K+1];
        for(int i=0; i<=K; i++){
            for(int j=0; j<=K; j++){
                ks[i][j] = new ArrayList<>();
            }
        }
        for(int u=1; u<=N; u++){
            g[u].sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return ES[o1].w - ES[o2].w;
                }
            });

            int od = ods[u];
            for(int i=0; i<g[u].size(); i++){
                ks[od][i+1].add(g[u].get(i));
            }
        }

        for(int o=1; o<=K; o++){
            for(int k=1; k<=o; k++){
                ArrayList<Integer> vs = new ArrayList<>();
                for(int ei : ks[o][k]){
                    int v = ES[ei].v;
                    vs.add(v);
                }
                hs[o][k] = new HashCode(vs);
            }
        }

        ArrayList<Integer> vs = new ArrayList<>();
        for(int v=1; v<=N; v++){
            vs.add(v);
        }
        TH = new HashCode(vs);

        ans = 0;
        dfs(1, new HashCode(0,0,0));
        return ans;
    }


    public static void main(String[] args) throws Exception {
        N = io.nextInt();
        M = io.nextInt();
        K = io.nextInt();

        g = new ArrayList[N + 1];
        for(int u=1; u<=N; u++){
            g[u] = new ArrayList<>();
        }
        ods = new int[N+1];
        ES = new Edge[M + 1];
        for(int i=0; i<M; i++){
            int u, v, w;
            u = io.nextInt(); v = io.nextInt(); w = io.nextInt();
            ods[u]++;
            ES[i] = new Edge(u, v, w);
            if(g[u].add(i));
        }

        io.println(solve());

        io.close();
    }

    static class Edge {
        public int u,v,w,d,idx;
        public Edge(int u, int v, int w){
            this.u = u; this.v = v; this.w = w;
        }
    }

    static class FastIO {
        static BufferedReader br;
        static StringTokenizer st;
        static PrintStream ps = new PrintStream(System.out);

        public FastIO(String fname) {
            try {
                File input = new File(fname);
                if (input.exists()) {
                    System.setIn(new FileInputStream(fname));
                }
            }catch (Exception e){
                e.printStackTrace();
            }

            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());
        }

        void flush(){
            ps.flush();
        }

        void close(){
            ps.close();
        }

        void print(Object o){
            ps.print(o);
        }

        void println(Object o){
            ps.println(o);
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}
