姬哥来到了大鸟转转转游乐园，他知道这个游乐园可以用一张 n 个点， m 条边的有向图表示，每条边都有一个互不相同的边权。姬哥还知道，每个顶点的出度不超过 k。
为了更好的感受大鸟转转转游乐园的温暖，姬哥希望设计若干游园方案。每个游园方案可以用一个长度为 k 的正整数序列 (c1,c2,...,ck) 表示，且对于任意 1≤i≤k，都有 1≤ci≤i。
游园方案的具体含义如下：假设姬哥当前位于出度为 i 的点 x 时，他总会走向 x 的所有出边中第 ci 小的那条边。因为所有边的边权互不相同，所以对于任意一个固定的序列 (c1,c2,...,ck)，姬哥的行动方案总是唯一的。
为了永远迷失在游乐园的温暖之中，姬哥希望你帮忙计算，有多少个序列 (c1,c2,...,ck) ，使得对于任意点 u(1≤u≤n)，姬哥都能根据上述行动规则重新回到 u 点。因为答案可能很大，快来帮帮姬哥！
第一行包含三个整数 n、m、k（1≤n≤1×105，1≤m≤min(6×105,(n−1)×n), 1≤k≤14），分别表示有向图的定点数、边数和每个点的出度上限。
接下来 m 行，每行三个正整数 u,v,w (1≤u,v≤n, 1≤w≤1×109)，表示一条从点 u 连到点 v 边权为 w 的有向边，输入数据保证所有边的边权互不相同，有向图中没有重边和自环，每个顶点的出度至少为 1。
一行一个正整数，代表可能的序列个数。
3 4 3
1 2 5
1 3 4
2 3 1
3 1 10
3
注意到这里不存在出度为3的点， c3 可以取 {1,2,3} 中的任意一值。所有可能的序列有(1,2,1)、(1,2,2)、(1,2,3)。