题目描述

给定一个带权连通图，包含 N 个点和 M 条边。这个图有一个特殊性质：对于任意一种可能的边权，具有该权值的边最多只有 R 条。

你需要计算这个图的最小生成树共有多少棵。

图的生成树是边集的一个子集，它构成一棵包含所有顶点的树。
最小生成树是所有生成树中边权总和最小的生成树。
如果两棵生成树所使用的边集不同，则认为它们不同。

输入格式

标准输入第一行包含两个正整数 N 和 M，分别表示点数和边数。

接下来 M 行，每行包含三个正整数 A_i、B_i 和 C_i，表示第 i 条边连接顶点 A_i 与 B_i，边权为 C_i。

输出格式

输出最小生成树的数量，答案对 10^9 + 7 取模。

限制

• 2 ≤ N ≤ 10^5
• 1 ≤ M ≤ 2 × 10^5
• 1 ≤ R ≤ 16
• 1 ≤ A_i < B_i ≤ N
• 0 ≤ C_i ≤ 10^6
• 当 i ≠ j 时，(A_i, B_i) ≠ (A_j, B_j)

子任务

某个子任务的分数，只有在该子任务及其包含的所有更弱限制子任务全部通过时才能获得。

样例 1

输入

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

输出

3

说明

共有 3 棵最小生成树（总权值均为 4）：

{(1, 2), (2, 3), (1, 4)}
{(1, 2), (1, 3), (1, 4)}
{(2, 3), (1, 3), (1, 4)}

样例 2

输入

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

输出

24

说明

共有 24 棵最小生成树（总权值均为 8）。