TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

64.7% (11/17)

Submission's AC Ratio

12.3% (20/162)

Description

傳說,從前有一個人,他姓「羅」,但是又冠母姓「龔」(可能是i度空間的習俗),全名是:

你沒看錯,他的全名寫起來總共有153劃!因為實在是太難寫了,每次考試他還沒寫完姓名,別人就已經交卷了。
他覺得很不高興,恰好他聽說有一種樂器叫做「環保革胡」。這種樂器非常環保,不像每次考試寫名字一樣浪費墨水,所以他決定去欣賞這種樂器的演奏會。

到了演奏會,才發現原來環保革胡源自於一種中國傳統樂器叫做革胡。中國政府為了讓13億人都驚呆,籌組了一個13億人的樂團,可是龔羅Biángbiáng眼睛不好、數學也不好,他把總人數數成了G人。
(註:以上「13億」是一個虛數。)

因為他覺得G人樂團實在是太壯觀了,他決定認真聽這場演奏會,其中有一個樂段吸引了它的注意。
他發現在這個樂段當中,對於任兩個樂團成員的旋律,都會有「和諧」或「不和諧」其中一種關係。

龔羅Biángbiáng決定用演奏會發的問卷把每兩個樂團成員旋律的關係記下來。但是他的聽寫能力很弱,一次只能判斷一對旋律的關係。(事實上,他並沒有通過「瘋狂聽寫考試」。)
很不幸的,在他還沒有記錄完樂段中所有的關係時,這個樂段已經結束了。

不幸中的大幸是,他的樂理還不弱,知道「國樂基本定理」的表述:
一、考慮任兩個樂團成員的旋律A, B,A, B和諧若且唯若B, A和諧。(又稱國樂交換律)
二、考慮任三個樂團成員的旋律A, B, C,那麼A, B、B, C、C, A三對關係中,不和諧的對數必須是零對或兩對。

龔羅Biángbiáng對自己聽寫的結果非常有信心,因此他相信如果他記錄的結果違反了「國樂基本定理」,那創作這首「環保革胡協奏曲」的人一定是濫竽充數,連這麼基本的定理都不知道。
但是如果記錄的結果沒有違反「國樂基本定理」,他也想要知道,對於他沒有記錄下來的關係當中,有幾種不同的安排方法(也就是對每一對未知的關係都安排「和諧」或「不和諧」),使得最後的結果會滿足「國樂基本定理」。

Input Format

第一行有兩個正整數$N, M \leq 10^ 6$,分別代表實際上樂團中有幾個人(編號為0~N-1),以及龔羅Biángbiáng總共記錄了幾對結果。

接下來有$M$行,每一行有三個非負整數$A_i, B_i, D_i$。
如果$D_i=0$,代表編號$A_i, B_i$的人的旋律互相不和諧;
如果$D_i=1$,代表編號$A_i, B_i$的人的旋律互相和諧。
保證$A_i<B_i$且紀錄不會重複。

子任務(測資) 額外限制 分數
1 (0~3) $N, M \leq 15$ 13
2 (0~7) $N, M \leq 500$ 30
3 (9~10) $M \leq 5\times 10^ 5$ 21
4 (0~11) 無限制 36

Output Format

如果龔羅Biángbiáng記錄的結果違反了「國樂基本定理」,請輸出一行0;
否則請輸出一行非負整數,代表不違反「國樂基本定理」的關係安排方法總數。因為答案可能很大,你只要輸出答案$\mod 10^ 9+7$的結果就可以了。

Sample Input

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

Sample Output

1

Hints

範例測資的唯一解是1, 3和諧、0, 2不和諧。

Problem Source

Problem set / Description by Yihda Yol
建國中學105學年度校內第二次模擬賽 pB

Subtasks

For Testdata: 0 ~ 3, Score: 13
For Testdata: 0 ~ 7, Score: 30
For Testdata: 9 ~ 10, Score: 21
For Testdata: 0 ~ 11, Score: 36
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1200 40960 65536
9 600 65536 65536
10 600 65536 65536
11 600 40960 65536