32341번 - 완전하게 순찰하기

문제

최근 조선의 수도 한양에서 범죄 사건이 급증하자, 임금은 도성 내외의 순찰을 강화하라는 어명을 내렸다. 이 중대한 임무를 맡게 된 포도대장은 미래에서 온 여러분에게 도움을 요청했다.

포도청은 도성 내외의 위험 장소를 조사하여, 각 장소에 0ドル$부터 $N - 1$까지의 정수로 고유 번호를 하나씩 매겼다. 모든 장소는 양방향 통행이 가능한 길로 서로 연결되어 있으며, 각 장소에 연결된 길의 수는 짝수라고 한다. 각 길은 양 끝의 두 장소만 연결한다.

포졸들은 지정된 순찰 경로를 따라 움직이며 순찰을 돌게 된다. 이때, 한 장소에서 다른 장소로 이동할 때 주어진 길을 따라가야 하며, 이동하는 중간에 방향을 바꿀 수 없다. 포졸이 어떤 순찰 경로를 따라 움직이면서 방문한 장소 $L$개의 번호를 순서대로 $v_1, \dots, v_L,ドル 지나간 $L$개의 길을 순서대로 $e_1, \dots, e_L$이라 하자. 길이가 2ドルL$인 순찰 경로는 다음 조건을 만족하는 순열 $(v_1, e_1, v_2, e_2, \dots, v_L, e_L)$을 의미한다. 순찰 경로의 각 홀수 번째 원소는 장소의 번호이고, 각 짝수 번째 원소는 길이다.

• 순찰 경로는 출발한 장소로 다시 돌아오는 경로이다. 이때, 동일한 장소를 여러 번 지나갈 수 있다.
• 순찰 경로에서 한 번 지나간 길은 다시 지나갈 수 없다.
• 출발한 장소에서 다른 장소로 움직이지 않는 경로는 순찰 경로가 아니다.
• 모든 1ドル \leq i \leq L - 1$인 정수 $i$에 대하여 길 $e_i$는 두 장소 $v_i$번과 $v_{i+1}$번을 연결한다. 길 $e_L$은 두 장소 $v_L$번과 $v_1$번을 연결한다.

이때, 길이가 2ドルL$인 순찰 경로에 다음 연산을 한 번 이상 사용하여 만들 수 있는 모든 순찰 경로는 서로 동일하다.

• 순찰 경로의 첫 번째 원소와 두 번째 원소를 뒤로 옮긴다. 즉, $(v_1, e_1, v_2, e_2, \dots, v_L, e_L)$를 $(v_2, e_2, \dots, v_L, e_L, v_1, e_1)$로 만든다.
• 순찰 경로를 뒤집고, 첫 번째 원소를 뒤로 옮긴다. 즉, $(v_1, e_1, v_2, e_2, \dots, v_L, e_L)$를 $(v_L, e_{L-1}, v_{L-1}, e_{L-2}, \dots, v_1, e_L)$로 만든다.

예를 들어, $(0, a, 1, b)$는 $(0, b, 1, a),ドル $(1, a, 0, b),ドル $(1, b, 0, a)$와 모두 동일하다.

포도청은 도성 내외의 모든 길을 순찰하기 위해 완전한 순찰을 설계하려 한다. 완전한 순찰은 순찰 경로를 원소로 갖는 집합으로, 도성 내외의 모든 길이 완전한 순찰의 한 원소에만 포함되어야 한다. 이때, 각 포졸이 어떤 순찰 경로를 맡는지는 고려하지 않으며, 포졸의 인원수에도 제한이 없다고 가정한다. 설계할 수 있는 완전한 순찰의 경우의 수를 10ドル^9+7$로 나눈 나머지를 구해보자.

입력

첫 번째 줄에 장소의 수 $N$과 양의 정수 $M$이 공백으로 구분되어 주어진다. $(2 \leq N \leq 100,000円;$ 1ドル \leq M \leq 200,000円)$

이후 $M$개의 줄에 걸쳐 $i+1$번째 줄에 세 정수 $u_i,ドル $v_i,ドル $w_i$가 공백으로 구분되어 주어진다. 이는 두 장소 $u_i$번, $v_i$번을 연결하는 길이 $w_i$개가 있다는 것을 의미한다. $(u_i \neq v_i;$ 0ドル \leq u_i, v_i \leq N-1;$ 1ドル \leq w_i \leq 100)$

두 장소를 연결하는 길에 대한 정보는 한 번만 주어진다. 즉, 0ドル \leq i < j \leq N - 1$인 두 정수 $i,ドル $j$에 대하여 $\{u_i, v_i\} \neq \{u_j, v_j\}$이다.

출력

설계할 수 있는 완전한 순찰의 경우의 수를 10ドル^9+7$로 나눈 나머지를 출력한다. 이때, 10ドル^9+7$은 소수이다.

제한

힌트