시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 37 10 9 40.909%

문제

많은 드라마나 영화에서는 “삼각 관계”가 등장한다. 이는 등장인물 A와 등장인물 B가 서로를 좋아하고, 등장인물 B와 등장인물 C가 서로를 좋아하지만, 등장인물 A와 등장인물 C가 서로를 싫어하는 관계를 의미한다. 편의상, 모든 등장인물끼리는 서로를 좋아하거나, 서로를 싫어한다고 가정하자. (중립적인 관계는 없으며, 관계가 존재하지 않는 경우 역시 없으며, A는 B를 좋아하지만 B는 A를 싫어하는 관계 역시 없다. 따라서, 모든 nC2개의 관계에 대해 좋아하는지 싫어하는지는 명확하게 결정된다.)

n명의 등장인물이 등장하는 어떤 드라마를 생각해 보자. Alice는 지금까지의 드라마 진행을 통해 m쌍의 등장인물에 대해, 그 쌍의 관계를 알고 있다. Alice는 드라마들의 지나치게 진부한 삼각 관계에 지친 나머지, 이번 드라마에서는 삼각 관계가 존재하지 않기를 원한다. 하지만, Alice는 등장인물들끼리 모두 서로를 싫어하는 것 역시 원치 않기 때문에, 세 명에 대해 적어도 한 쌍은 서로를 좋아하기를 원한다. 즉, 임의의 세 등장인물 A, B, C에 대해, A-B, B-C, C-A 중 한 쌍만이 서로를 좋아하는 관계이거나, 세 쌍 모두가 서로를 좋아하는 관계이기를 원한다.

Alice는 남은 등장인물 쌍에 대해 예상 관계도를 그려보고 있다. 하지만, 위의 조건을 만족하도록 하는 관계도가 너무 많았기 때문에, Alice는 그것을 모두 그리는 것을 포기하였다. 대신, Alice는 위의 조건을 만족하는 관계도의 개수를 세고 싶어한다. 현재 알고 있는 m쌍의 인물 관계가 주어질 때, 남은 인물 관계를 채울 수 있는 방법의 수를 출력하시오.

입력

첫 번째 줄에는 등장인물의 수 n과 현재 알려진 인물 관계의 수 m이 주어진다. (3 ≤ n ≤ 100,000; 0 ≤ m ≤ 100,000; m ≤ n*(n-1)/2)

다음 m개의 줄에는 한 줄에 하나씩 등장인물의 관계가 주어진다. i번째 줄에는 세 자연수 ai, bi, ci가 주어진다. ci가 1인 경우, ai와 bi가 서로 좋아하는 관계임을 의미한다. ci가 0인 경우, ai와 bi가 서로 싫어하는 관계임을 의미한다. (1 ≤ ai ≠ bi ≤ n, ci = 0 or 1) 하나의 (ai, bi)쌍은 최대 한 번씩만 주어지며, (ai, bi)쌍이 주어졌다면 (bi, ai)쌍은 입력으로 주어지지 않는다.

출력

남은 인물 관계를 채울 수 있는 경우의 수를 1,000,000,007(109+7)로 나눈 나머지를 출력한다.

예제 입력 1

3 0

예제 출력 1

4

예제 입력 2

4 4
1 2 1
2 3 1
3 4 0
4 1 0

예제 출력 2

1

예제 입력 3

4 4
1 2 1
2 3 1
3 4 0
4 1 1

예제 출력 3

0