완전하게 순찰하기

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

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

포졸은 지정된 순찰 경로를 따라 움직이며 순찰한다. 한 장소에서 다른 장소로 이동할 때는 주어진 길을 따라가야 하며, 이동하는 도중에 방향을 바꿀 수 없다. 포졸이 순찰 경로를 따라 움직이며 방문한 장소 $L$개의 번호를 순서대로 $v_1, \dots, v_L$, 지나간 길 $L$개를 순서대로 $e_1, \dots, e_L$이라 하자. 길이가 $2L$인 순찰 경로는 다음 조건을 만족하는 순열 $(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$을 연결한다.

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

• 첫 번째 원소와 두 번째 원소를 뒤로 옮긴다. 즉 $(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 100000$, $1 \leq M \leq 200000$)

이후 $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$은 소수이다.