古堡机关

题目描述

33DAI 闯进了一座古堡，墙角有 $n$ 个机关，每个机关只有「按下」和「不按」两种状态。 Tom 在墙上留下了 $m$ 句提示，每句提示都由三个条件用「或者」连接而成，例如 「第 $1$ 个机关按下，或者第 $3$ 个机关不按，或者第 $5$ 个机关按下」。

33DAI 发现，只要机关的状态同时满足这 $m$ 句提示，石门就会打开。 他想知道，一共有多少种状态方案能让石门打开。

输入格式

第一行两个整数 $n, m$。

接下来 $m$ 行，每行六个整数 $i, s, j, t, k, u$，表示一句提示： 第 $i$ 个机关的状态必须是 $s$，或者第 $j$ 个机关的状态必须是 $t$，或者第 $k$ 个机关的状态必须是 $u$。 其中 $1 \le i, j, k \le n$，$s, t, u \in \{0, 1\}$，$0$ 表示不按、$1$ 表示按下。

输出格式

输出一个整数，表示满足全部提示的方案数。

3 1
1 1 2 1 3 1

7

样例 1 解释

唯一的提示要求三个机关里至少有一个按下。全部 $2^3 = 8$ 种状态里，只有「三个都不按」不满足，所以答案是 $7$。

2 1
1 0 2 0 2 0

3

样例 2 解释

提示是「第 $1$ 个不按，或第 $2$ 个不按，或第 $2$ 个不按」，等价于「第 $1$、$2$ 个至少有一个不按」。 只有「两个都按下」不满足，所以答案是 $2^2 - 1 = 3$。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 30$；
• $0 \le m \le 60$；
• $1 \le i, j, k \le n$，$s, t, u \in \{0, 1\}$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。