완전하게 순찰하기

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

포도청은 도성 내외의 위험 장소를 조사하여, 각 장소에 $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 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$은 소수이다.