최소 스패닝 트리 다시 그리기 놀이

하늘이는 최근 입대하였다. 하늘이의 선임은 하늘이가 사회에서 코딩하다 온 것을 알고, 하늘이에게 다음과 같이 ”최소 스패닝 트리 다시 그리기 놀이”를 알려 주었다.

• 먼저 선임이 후임에게 무향 연결 그래프 $G$를 준다. 이때, $G$를 구성하는 간선의 가중치는 모두 $10^6$이하의 양의 정수이다.
• 후임은 $G$에서 그릴 수 있는 서로 다른 최소 스패닝 트리 중 동일한 확률로 최소 스패닝 트리 $T$를 하나 고른다.
• 선임은 $1$부터 $10^6$까지 차례대로 각각 독립적으로, 정수 $x$를 $\frac{1}{x}$의 확률로 후임에게 말한다. 즉, $1$은 반드시 말하므로, 최소 $1$개 이상 $10^6$개 이하의 수를 말한다.
• 후임은 선임이 $x$를 말하면 $T$에서 가중치가 $x$인 간선을 모두 지운다. $T$에서 간선들이 지워진 상태를 $T^\prime$이라고 하자.
• 후임은 $T^\prime$에, 원래 그래프 $G$에 있는 간선을 $0$개 이상 추가하여 다시 $G$의 최소 스패닝 트리를 만든다.

하늘이는 이 놀이를 듣고, 새로 그릴 수 있는 최소 스패닝 트리의 개수가 몇 개인지 궁금해졌다. 선임이 후임에게 주는 그래프 $G$가 주어졌을 때, ”최소 스패닝 트리 다시 그리기 놀이”를 통해 그릴 수 있는 최소 스패닝 트리의 개수의 기댓값을 구해보자.

첫 번째 줄에 $G$의 정점의 개수 $V$과 간선의 개수 $E$가 공백으로 구분되어 주어진다. $(2\le V\le 500;$ $V-1\le E\le\frac{V(V-1)}{2})$

두 번째 줄부터 $E$개의 줄에 걸쳐 $G$의 간선의 정보를 나타내는 정수 $u_i$, $v_i$, $w_i$가 공백으로 구분되어 주어진다. 이는 $u_i$번 정점과 $v_i$번 정점을 연결하는 가중치 $w_i$의 간선이 존재한다는 의미이다. $(1\le u_i, v_i\le V;$ $u_i \ne v_i;$ $1\le w_i\le 10^6)$

주어지는 그래프는 연결 그래프이며, 임의의 두 정점 사이의 간선은 최대 한 개 존재함이 보장된다.

$G$에 대해 “최소 스패닝 트리 다시 그리기 놀이”를 통해 그릴 수 있는 최소 스패닝 트리의 개수의 기댓값을 $10^9+7$로 나눈 나머지를 출력한다.

기약 분수 $\frac{p}{q}(p\ge 0,q>0,\gcd(p,q) =1)$를 $M$으로 나눈 나머지는 $q^{-1}$가 $q\cdot q^{-1}\equiv 1\pmod M$을 만족하는 정수, 즉 $q$의 $M$에 대한 모듈로 곱셈 역원일 때, $p\cdot q^{-1}\pmod M$로 정의한다. 만약 정수일 경우 $q=q^{-1}=1$이므로 $p\pmod M$를 의미한다.

만약 정답의 분모가 $10^9+7$의 배수인 경우 기댓값 대신 -1을 출력한다.