Boboniu 有一个有向图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。
每个顶点的出度最多为$$$k$$$。
每条边的权重介于 $$$1$$$ 和 $$$m$$$ 之间。没有两条边具有相同的权重。
Boboniu 喜欢在有一些特定规则的图上行走,这些规则由元组 $$$(c_1,c_2,\ldots,c_k)$$$ 表示。如果他现在站在出度为 $$$i$$$ 的顶点 $$$u$$$ 上,那么他将沿着从 $$$u$$$ 发出的所有边中权值最小的 $$$c_i$$$-th $$$(1\le c_i\le i)$$$ 到下一个顶点。
现在 Boboniu 要求您计算元组 $$$(c_1,c_2,\ldots,c_k)$$$ 的数量,使得
- $$$1\le c_i\le i$$$ 对于所有 $$$i$$$ ($$$1\le i\le k$$$)。
- 从任何顶点 $$$u$$$ 开始,通过在所描述的规则下在图上行走,可以在有限时间内返回到 $$$u$$$。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2\le n\le 2\cdot 10^5$$$、$$$2\le m\le \min(2\cdot 10^5,n(n-1) )$$$、$$$1\le k\le 9$$$)。
接下来的 $$$m$$$ 行包含三个整数 $$$u$$$、$$$v$$$ 和 $$$w$$$ $$$(1\le u,v\le n,u\ne v,1\le w\le m)$$$,表示从 $$$u$$$ 到 $$$v$$$ 的边,权重为 $$$w$$$。保证不存在自环或多条边,并且每个顶点至少有一条从自身开始的边。
保证每个顶点的出度至多为$$$k$$$,并且没有两条边具有相等的权重。
输出
打印一个整数:元组的数量。
示例
输入 #1
4 6 3 4 2 1 1 2 2 2 4 3 4 1 4 4 3 5 3 1 6
输出 #1
2
输入 #2
5 5 1 1 4 1 5 1 2 2 5 3 4 3 4 3 2 5
输出 #2
1
输入 #3
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
输出 #3
1
注意
对于第一个示例,有两个元组:$$$(1,1,3)$$$ 和 $$$(1,2,3)$$$。图片中的蓝色边表示每个顶点的第 $$$c_i$$$ 个最小边,Boboniu 选择经过这些边。
对于第三个示例,只有一个元组:$$$(1,2,2,2)$$$。
顶点$$$u$$$的出度表示从$$$u$$$出的边的条数。