有很多关于“三角恋”的动漫:爱丽丝爱鲍勃,查理也爱鲍勃,但爱丽丝讨厌查理。您正在考虑一部有 n 个角色的动漫。字符从 1 到 n 进行标记。每对两个角色都可以彼此相爱或互相憎恨(没有中立状态)。
你讨厌三角恋(A-B相爱,B-C相爱,但A-C互相讨厌),你也讨厌没有人相爱。因此,考虑任意三个角色,如果恰好一对相爱(A 和 B 彼此相爱,C 讨厌 A 和 B),或者如果所有三对都相爱(A 爱 B,B 爱 C,C 爱 A),那么您会很高兴。
您将获得动画中 m 个已知关系的列表。你肯定知道有些人彼此相爱,有些人则彼此憎恨。您想知道可以用多少种方式来填补剩余的关系,以便您对每个三角形感到满意。如果两个角色在一种方面相爱,但在另一种方面彼此憎恨,则两种方式被认为是不同的。打印此计数以 1 000 000 007 为模。
输入
输入的第一行将包含两个整数 n, m (3 ≤ n ≤ 100 000, 0 ≤ m ≤ 100 000)。
接下来的 m 行将包含已知关系的描述。第 i 行将包含三个整数 ai、bi、ci。如果 ci 为 1,则 ai 和 bi 相爱,否则,他们互相讨厌(1 ≤ ai, bi ≤ n, ai ≠ bi, $$c_i \in \{0, 1\}$$)。
每对人只会被描述一次。
输出
打印一个整数,该整数等于填充剩余对的方法数,以便您对每个三角形模 1 000 000 007 感到满意。
示例
输入 #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
注意
在第一个示例中,四种方法是:
- 让每个人都彼此相爱
- 让 1 和 2 彼此相爱,而 3 讨厌 1 和 2(对称地,我们从中得到 3 种方式)。
在第二个示例中,唯一可能的解决方案是让 1 和 3 彼此相爱,而 2 和 4 彼此仇恨。