题目描述

现在有 $n$ 个点，每个点需要被染成红蓝绿三种颜色之一。

然而存在 $m$ 条限制。第 $i$ 条限制形如：

点 $a_i$ 的颜色不是 $x_i$ 或 点 $b_i$ 的颜色不是 $y_i$ 。

请求出染色的方案数。

输入格式

第一行包含两个整数 $n,m$ ，表示限制的个数。

接下来 $m$ 行，每行四个整数 $a_i,x_i,b_i,y_i$ ，含义如上文所示。

其中 $0$ 代表红色，$1$ 代表蓝色，$2$ 代表绿色。

输出格式

输出一行一个整数，表示合法的染色方案数。

样例

样例输入

2 3
1 0 2 0
1 1 2 0
1 2 2 1

样例输出

6

数据范围

对于所有数据，$n\le 22,m\le 9\tbinom{n}{2}$ ，保证对于 $1\le i\le m$ ， $1\le a_i<b_i\le n$ ，$0\le x_i,y_i<3$ ，不存在两组限制完全相同。

子任务 1 ( 20% ) : $n\le 13$ 。

子任务 2 ( 20% ) ：$x_i,y_i=0$ 。

子任务 3 ( 20% ) ： $x_i,y_i<2$ 。

子任务 4 ( 20% ) ：$n\le 20$ 。

子任务 5 ( 20% ) ：无特殊限制。