K. 迷失游乐园

姬哥来到了大鸟转转转游乐园，他知道这个游乐园可以用一张 $n$ 个点， $m$ 条边的有向图表示，每条边都有一个互不相同的边权。姬哥还知道，每个顶点的出度不超过 $k$。

为了更好的感受大鸟转转转游乐园的温暖，姬哥希望设计若干游园方案。每个游园方案可以用一个长度为 $k$ 的正整数序列 $(c_1,c_2,...,c_k)$ 表示，且对于任意 $1 \leq i \leq k$，都有 $1 \leq c_i \leq i$。

游园方案的具体含义如下：假设姬哥当前位于出度为 $i$ 的点 $x$ 时，他总会走向 $x$ 的所有出边中第 $c_i$ 小的那条边。因为所有边的边权互不相同，所以对于任意一个固定的序列 $(c_1,c_2,...,c_k)$，姬哥的行动方案总是唯一的。

为了永远迷失在游乐园的温暖之中，姬哥希望你帮忙计算，有多少个序列 $(c_1,c_2,...,c_k)$ ，使得对于任意点 $u(1 \leq u \leq n)$，姬哥都能根据上述行动规则重新回到 $u$ 点。因为答案可能很大，快来帮帮姬哥！

第一行包含三个整数 $n$、$m$、$k$（$1\leq n \leq 1 \times 10^5$，$1\leq m \leq min(6 \times 10^5,(n-1)\times n)$, $1\leq k\leq 14$），分别表示有向图的定点数、边数和每个点的出度上限。

接下来 $m$ 行，每行三个正整数 $u,v,w$ ($1\leq u,v \leq n$, $1\leq w \leq 1 \times 10^9$)，表示一条从点 $u$ 连到点 $v$ 边权为 $w$ 的有向边，输入数据保证所有边的边权互不相同，有向图中没有重边和自环，每个顶点的出度至少为 $1$。

一行一个正整数，代表可能的序列个数。

输入样例

3 4 3
1 2 5
1 3 4
2 3 1
3 1 10

输出样例

3

输出解释

注意到这里不存在出度为3的点， $c_3$ 可以取 {1,2,3} 中的任意一值。所有可能的序列有(1,2,1)、(1,2,2)、(1,2,3)。