Recently, Deepankur heard of Liar's Paradox and how it was used by some amazing mathematicians to prove some amazing stuff. While pondering over it, the idea of generalising Liar's Paradox to a finite number of people came upon Deepankur.

In this problem there are n people numbered from 1 to n. Each person i makes some claims. The claims are of form:-
a. The person j always lies
b. The person j always speaks the truth
Assume a black and white world where every person either speaks the truth all the time or lies all the time ( quite different from the real world).

Also, assume that every person knows the truth about every other person (also quite different from the real world).

Given each claim determine the number of ways in which all the n people can be assigned either honest or dishonest such that all claims made by honest people are true and all claims made by dishonest people are false.

Output the answer modulo 1e9+7
.

Help Deepankur Solve the Problem.

Note, it is possible that a person claims something about himself/herself.

Input:
The first line contains the number of people ( 2≤n≤100000) and the number of claims ( 1≤m≤100000).

Next m lines contain claims encoded by three numbers each i,j and k.

(1≤i≤n and 1≤j≤n and k=0/1).
k=0 means that the i-th numbered person claims that j-th numbered person always speaks lies.
k=1 means that the i-th numbered person claims that j-th numbered person always speaks the truth

Output:
Print one integer the numbers of ways of assigning honest and dishonest that is consistent with the all the claims modulo 1e9+7.

Examples
Input:
2 2
1 2 0
2 1 1
outputCopy
0
inputCopy
10 9
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
outputCopy
2
inputCopy
10 5
1 2 0
2 3 0
3 4 1
4 5 1
5 6 0
outputCopy
32
Note
In this case person 1 claims that 2 is always speaking lies and person 2 claims that person 1 always speaks the truth. Clearly, a contradictory case.

I'm trying to use graphs here and assigning values as per DFS. If a contradiction is found (say a cycle where values clash), its contribution isn't taken else it is. But I'm stuck on test case 4. I'll link it here and if you could solve it some help would be nice. (https://mirror.codeforces.com/group/ZEXri9keRR/contest/309946/problem/K) Also I'm kinda new here so it'd be nice if someone enlighten me as to why this site doesn't allow you to see failed test cases or give some valuable error messages which would help debug? Honestly debugging sums here feels like a chore as after a certain point you run out of ideas as to where your code crashes.