← 返回题目列表

AtCoder · arc093_c

E. 双色生成树

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

我们有一个无向加权图 N 顶点和 M 边缘。 的 i图中的第一条边连接顶点 U_i 和顶点 V_i,重量为 W_i。 另外,你会得到一个整数 X.

求出将图中每条边绘制为白色或黑色以满足以下条件的方法的数量,取模 10^9 + 7:

  • 该图有一个生成树,其中包含涂成白色的边和涂成黑色的边。此外,在这些生成树中,权重最小的一棵树的权重为 X.

这里,生成树的权重是生成树中包含的边的权重之和。

约束

  • 1 \leq N \leq 1 000
  • 1 \leq M \leq 2 000
  • 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq M)
  • If i \neq j,那么 (U_i, V_i) \neq (U_j, V_j) 和 (U_i, V_i) \neq (V_j, U_j).
  • U_i \neq V_i (1 \leq i \leq M)
  • 给定的图形已连接。
  • 1 \leq X \leq 10^{12}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
X
U_1 V_1 W_1
U_2 V_2 W_2
:
U_M V_M W_M

输出

打印答案。


示例输入 1

3 3
2
1 2 1
2 3 1
3 1 1

示例输出 1

6

示例输入 2

3 3
3
1 2 1
2 3 1
3 1 2

示例输出 2

2

示例输入 3

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

示例输出 3

0

示例输入 4

8 10
49
4 6 10
8 4 11
5 8 9
1 8 10
3 8 128773450
7 8 10
4 2 4
3 4 1
3 1 13
5 2 2

示例输出 4

4