ICPC Teams

Time limit3sMemory limit256 MB

Summary

Count ways to split 3N students into teams of three so all M same-team and different-team pairs hold, modulo 1e9+9.

Level: Hard8 of 10
Topics: Combinatorics, Union-find, Backtracking
Solved: No attempts yet

Problem

You coach the ICPC club at your university. The club has $3N$ students, and you have to build $N$ teams for the next ICPC. Every ICPC team has exactly 3 members, and each student belongs to exactly one team.

When you build the teams you have to account for several relationships among the students. Two students who get along extremely well perform much better when they share a team. The opposite happens for a pair that gets along badly. So two students with a good relationship must be placed on the same team, and two students with a bad relationship must be placed on different teams. As the coach you know all $M$ relationships among the students.

Write a program that counts the team assignments satisfying every condition. Two assignments are different if and only if there is a pair of students who share a team in one assignment and do not share a team in the other.

Input

The first line contains two integers $N$ and $M$ ( $1 \le N \le 10^6$ , $1 \le M \le 18$ ). The $i$ -th of the next $M$ lines contains three integers $A_i$ , $B_i$ ( $1 \le A_i, B_i \le 3N$ , $A_i \ne B_i$ ) and $C_i$ ( $C_i \in \{0, 1\}$ ). $A_i$ and $B_i$ are student numbers and $C_i$ is the relationship type. If $C_i$ is 0, student $A_i$ and student $B_i$ have a good relationship. If $C_i$ is 1, they have a bad relationship. For all $1 \le i, j \le M$ with $i \ne j$ , $\{A_i, B_i\} \ne \{A_j, B_j\}$ holds.

Output

Print the number of valid team assignments modulo $10^9 + 9$ on one line.

Examples3

Example 1
Input
```
2 2
1 2 0
3 4 1
```
Expected output
```
2
```
Example 2
Input
```
1 1
1 2 0
```
Expected output
```
1
```
Example 3
Input
```
2 3
1 2 1
3 4 1
5 6 1
```
Expected output
```
4
```