유한 걷기

무향 그래프 $G$가 주어진다. 정점은 $n$개, 간선은 $m$개이다. 루프와 다중 간선이 허용된다. 각 간선에는 양의 정수 $a_i$가 할당되어 있고, 처음에는 0인 카운터 $b_i$가 있다.

이 그래프에서 다음 과정을 생각한다. 시작 정점 $v_1$을 임의로 고르고, $v_1$에서 출발하는 간선 $e_1$을 따라 $v_2$로 이동한다. 그다음 $v_2$에서 출발하는 간선 $e_2$를 따라 $v_3$로 이동하고, 이를 계속한다. 즉 그래프 위의 경로를 하나 따라가는 것이며, 간선과 정점은 여러 번 지나도 된다. 간선 $i$를 어느 방향으로든 한 번 지날 때마다 그 카운터 $b_i$는 $(b_i + 1) \bmod a_i$가 된다. 과정은 몇 번의 이동 뒤에도 멈출 수 있다(0번도 가능하다).

이 과정이 끝난 뒤의 배열 $(b_1, b_2, \ldots, b_m)$을 설정 배열이라고 부르자. $G$의 가능한 모든 유한 경로에 대응하는 모든 과정을 생각한다. 이들이 만들어 낼 수 있는 서로 다른 설정 배열은 몇 개인가? 두 설정 배열은 적어도 한 원소가 다르면 서로 다른 것으로 본다. 답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 구한다.

입력의 첫 줄에 공백으로 구분된 정수 두 개 $n$, $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 4 \cdot 10^5$)이 주어진다. 각각 그래프의 정점 수와 간선 수이다.

이어서 $m$개의 줄에 간선이 한 줄에 하나씩 주어진다. $i$번째 간선은 정수 세 개 $u_i$, $v_i$, $a_i$ ($1 \le u_i, v_i \le n$, $1 \le a_i \le 10^9$)로 표현되며, 각각 간선의 양 끝점과 간선에 할당된 수이다. 정점 번호는 1부터 시작한다.

루프와 다중 간선은 허용된다.

출력은 한 줄이며, 서로 다른 설정 배열의 개수를 $10^9 + 7$로 나눈 나머지를 출력한다.