Tri-Color Puzzle

Time limit1sMemory limit1024 MB

Summary

Count the ways to color a triangular grid of hexagon cells, with some cells fixed, so every upward triple is all one color or all three colors.

Level: Medium6 of 10
Topics: Math, Matrix
Solved: No attempts yet

Problem

A Tri-Color Puzzle is a triangular array of hexagon cells with $S$ cells on each side, for a total of $N = \frac{S(S+1)}{2}$ cells. For example, the following is a puzzle with side 4 and 10 cells.

To solve the puzzle, each cell must be colored red, green, or blue so that for each triplet of cells with one cell above and two cells below, either all three cells are the same color or each of the three cells is a different color. For clarity, this statement uses hash patterns as well as colors:

Red = Green = Blue =

In a particular puzzle, some cells are initially specified, and the remaining cells must be filled in as described above. The following example has three solutions:

This example has no solutions:

This example has exactly one solution:

Write a program that takes as input a description of a Tri-Color Puzzle and outputs the number of solutions to the puzzle.

Input

The first line contains two space-separated decimal integers, $S$ and $I$ ( $3 \le S \le 19$ , $0 \le I \le N = \frac{S(S+1)}{2}$ ). The first line is followed by $I$ lines, each with three decimal integers: the row $r$ , the position $c$ of the cell within that row, and the color code $cc$ of one initial cell ( $1 \le r \le S$ , $1 \le c \le r$ , $0 \le cc \le 2$ ). Code 0 means red, 1 means green, and 2 means blue.

Output

The output is a single line containing the number of solutions to the Tri-Color Puzzle specified by the input.

Examples3

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