给定一个无向连通图,其中任意两个不同的简单循环没有公共顶点。由于图可能非常大,因此它以压缩形式提供给您:对于每条边,您还会获得一个数字 $$$d$$$,它表示该边上还有 $$$d$$$ 个附加顶点。
您需要为图的每个顶点和每条边分配一个权重 - 一个从 $$$1$$$ 到 $$$3$$$ 的整数。
如果图的相邻顶点权重的按位异或不等于 $$$0$$$ 并且不等于该边的权重,则该图的边被称为良好边。
类似地,如果图的相邻边的权重按位异或不等于 $$$0$$$ 并且不等于该顶点的权重,则该图的顶点被称为良好。
您需要确定有多少种方法为图的顶点和边分配权重,以便所有顶点和边都是好的。由于答案可能非常大,因此您需要计算答案除以 $$$998\,244\,353$$$ 的余数。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ - 图中的顶点数和边数 ($$$2 \le n \le 5 \cdot 10^5$$$, $$$n - 1 \le m \le 10^6$$$)。
接下来的 $$$m$$$ 行包含三个整数 $$$a_i、b_i$$$ 和 $$$d_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$, $$$0 \le d_i \le 10^9$$$),表明在连接顶点 $$$a_i$$$ 和 $$$b_i$$$ 的图。此外,在这条边上,还有 $$$d_i$$$ 个额外顶点。保证给定的图是连通的,不存在重边、环,并且该图的任何两个不同的简单循环没有公共顶点。
输出
输出一个整数——问题的答案以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
3 3 1 2 0 2 3 0 3 1 0
输出 #1
12
输入 #2
6 7 1 2 0 2 3 0 3 1 0 4 5 0 5 6 0 6 4 0 4 3 0
输出 #2
0
输入 #3
2 1 2 1 777
输出 #3
0
输入#4
3 3 1 2 0 2 3 110850709 3 1 1000000000
输出#4
179179178
注意
在第一个测试中,该图是 $$$3$$$ 个顶点的简单循环。可以证明,正好有 $$$12$$$ 方法来分配权重,以使所有顶点和边都良好。
在第二个测试中,图具有由边连接的 $$$3$$$ 顶点的两个简单循环的形式。可以证明,对于这样的图,没有办法安排权重以使所有顶点和边都是好的。