你是你大学国际大学生程序设计竞赛（ICPC）俱乐部的教练。俱乐部里共有 $3N$ 名学生，你希望为下一届 ICPC 组建 $N$ 支队伍。ICPC 中的每支队伍都由 3 名成员组成。每名学生恰好属于一支队伍。

在组建队伍时，你需要考虑学生之间的几种关系。有些学生与其他学生的关系非常好。如果他们属于同一支队伍，他们的表现会有惊人的提升。相反的情况也可能发生，即一对学生关系不好。简而言之，关系好的学生必须在同一支队伍中，而关系不好的学生必须在不同的队伍中。作为一名称职的教练，你了解学生之间的所有 $M$ 种关系。

你的任务是编写一个程序，计算可能的队伍分配方案数。当且仅当存在一对学生，在一种分配方案中他们处于同一支队伍，而在另一种分配方案中他们不在同一支队伍时，这两种分配方案被视为不同。

输入格式

输入包含一组测试数据。第一行包含两个整数 $N$ ($1 \le N \le 10^6$) 和 $M$ ($1 \le M \le 18$)。接下来的 $M$ 行中，第 $i$ 行包含三个整数 $A_i, B_i$ ($1 \le A_i, B_i \le 3N, A_i \neq B_i$) 和 $C_i$ ($C_i \in \{0, 1\}$)。$A_i$ 和 $B_i$ 表示学生的编号，$C_i$ 表示关系类型。如果 $C_i$ 为 0，则第 $A_i$ 号学生和第 $B_i$ 号学生关系良好。如果 $C_i$ 为 1，则他们关系不好。你可以假设对于所有 $1 \le i, j \le M$，若 $i \neq j$，则 $\{A_i, B_i\} \neq \{A_j, B_j\}$。

输出格式

输出一行，包含可能的队伍分配方案数，结果对 $10^9 + 9$ 取模。

样例

样例输入 1

2 2
1 2 0
3 4 1

样例输出 1

2