三色拼图（Tri-Color Puzzle）是一个由六边形单元组成的三角形阵列，每条边有 $S$ 个单元，总计 $N = (S \times (S+1))/2$ 个单元。例如，下图是一个边长为 4、总计 10 个单元的拼图。

为了解决这个拼图，每个单元必须被涂成红色、绿色或蓝色，使得对于每一组由上方一个单元和下方两个单元组成的三个单元，这三个单元要么颜色全部相同，要么颜色各不相同。为了清晰起见，在本题中，我们除了使用颜色外，还将使用阴影图案，如下所示：

红色 = 绿色 = 蓝色 =

在特定的拼图中，部分单元的颜色是预先指定的，其余单元需要按照上述规则进行填充。以下示例有三种解法：

该示例无解：

该示例恰好有一种解法：

编写一个程序，输入三色拼图的描述，并输出该拼图的解的数量。

输入格式

输入包含多行。第一行包含两个空格分隔的十进制整数 $S$ 和 $I$，其中 $3 \le S \le 19$ 且 $0 \le I \le N = (S \times (S+1))/2$。

第一行之后是 $I$ 行，每行包含三个十进制整数，分别表示行号 $r$、该行中的单元编号 $c$ 以及初始单元颜色代码 $cc$（$1 \le r \le S$，$1 \le c \le r$，$0 \le cc \le 2$），其中 $0$ 代表红色，$1$ 代表绿色，$2$ 代表蓝色。

输出格式

输出一行，包含指定三色拼图的解的数量。

样例

样例输入 1

4 4
1 1 0
2 1 2
4 1 2
4 4 2

样例输出 1

0

样例输入 2

4 4
1 1 1
2 1 2
4 1 2
3 3 2

样例输出 2

1

样例输入 3

4 4
1 1 0
2 1 1
4 1 0
4 4 0

样例输出 3

3