题目描述

有一个 $n$ 个点 $m$ 条边的有向图，图中每个点的出度不小于 $1$ 不大于 $k$ ，边有互不相同的边权。 小Z喜欢在图上以特定的规则行走，这个规则可以用 $k$ 元组 $c_1,c_2,...,c_k(c_i \in [1,i] \cap Z)$ 描述。如果他现在所在的点 $u$ 出度为 $i$ ，那么他会从 $u$ 的出边中权值第 $c_i$ 小的走出去。 问有多少个这样的 $k$ 元组，使得对于任意的点 $u$ ，可以按上述规则从 $u$ 出发走回 $u$。

输入格式

第一行三个整数 $n,m,k$ ,表示图的点数、边数和度数范围。 接下来 $m$ 行，每行三个正整数 $u,v,w$ 描述一条从 $u$ 向 $v$ ，边权为 $w$ 的边。

输出格式

一行一个整数，表示这样的 $k$ 元组的个数。

测试样例

4 6 3 
4 2 1 
1 2 2 
2 4 3 
4 1 4 
4 3 5 
3 1 6

2

样例解释 1

满足条件的3元组有且只有 $(1,1,3)$ 和 $(1,2,3)$ ，共 $2$ 种。

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

1

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

1

样例解释 3

满足条件的4元组有且只有 $(1,2,2,2)$ ，共 $1$ 种。

数据规模与约定

对于$30\%$的数据，$2\le n \le1300 , 2\le m \le 1300，1 \le k \le 3$。

对于$60\%$的数据，$2\le n \le 45000,2 \le m \le 45000，1 \le k \le 6$。

对于$100\%$的数据，$2\le n \le200000,2 \le m \le 200000，1 \le k \le 9$。

保证输入的图中不存在重边，不存在自环，每个点的出度不小于 $1$ 不大于 $k$ ，边权互不相同且不超过 $m$