CF553C Love Triangles

有许多动漫作品描述了“爱情三角”：爱丽丝喜欢鲍勃，查理也喜欢鲍勃，但爱丽丝讨厌查理。你正在考虑一部有 $n$ 个角色的动漫。角色编号为 $1$ 到 $n$。每对角色之间只能互相相爱，或互相仇恨（没有中立关系）。 你讨厌爱情三角（即 $A-B$ 相爱且 $B-C$ 相爱，但 $A-C$ 互相仇恨），也讨厌所有人都互相仇恨的情况。因此，对于任意三个角色来说，只有恰好一对相爱（如 $A$ 和 $B$ 相爱，而 $C$ 仇恨 $A$ 和 $B$），或者三对都相爱（$A$、$B$、$C$ 互相相爱）时，你才会满意。 现在给你动漫中 $m$ 对已知的关系。有些角色之间已知相爱，有些已知仇恨。请你计算有多少种方式可以补全剩下的关系，使所有三人组都让你满意。如果有两个人在某种方案中相爱，而在另一种方案中仇恨，则两种方案视为不同。请将最终方案数对 $1000000007$ 取模后输出。

输入的第一行为两个整数 $n$ 和 $m$，表示角色人数和已知关系数（$3\le n\le 100000$，$0\le m\le 100000$）。 接下来的 $m$ 行，每行包含三个整数 $a_{i},b_{i},c_{i}$。如果 $c_{i}=1$，则 $a_{i}$ 和 $b_{i}$ 相爱，否则他们互相仇恨（$1\le a_{i},b_{i}\le n$，$a_{i}\ne b_{i}$）。 每一对角色最多出现一次。

输出一个整数，表示满足条件的方案数，对 $1000000007$ 取模。

第一个样例中的四种方式如下： - 所有人互相相爱； - 1 和 2 相爱，3 仇恨 1 和 2（对称地，共 3 种）。 第二个样例中，唯一可行的方案是 1 和 3 相爱，2 和 4 仇恨。 由 ChatGPT 5 翻译